Metraipolis › archive › dc_a3fe78f834fb
Finite-Precision Gram-Schmidt Walks — arXiv:2610.08562
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.08562
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:40:36.559Z
- SHA-256 of the archived text
a15c71771d5157680bd3262becad941163e863804810399dd0b874df819d164d- Stable URL of this page
https://metraipolis.com/documento/dc_a3fe78f834fb
How to cite
Finite-Precision Gram-Schmidt Walks — arXiv:2610.08562 — arXiv (en), https://arxiv.org/abs/2610.08562 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a3fe78f834fb (Metraipolis archive dc_a3fe78f834fb, sha256 a15c71771d5157680bd3262becad941163e863804810399dd0b874df819d164d)
BibTeX
@misc{dca3fe78f834fb,
title = {Finite-Precision Gram-Schmidt Walks — arXiv:2610.08562},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.08562},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a3fe78f834fb; sha256 a15c71771d5157680bd3262becad941163e863804810399dd0b874df819d164d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08562. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Gram-Schmidt Walk is a randomized vector-balancing algorithm whose subgaussian guarantees support applications in discrepancy, experimental design, and data compression; however, these theoretical guarantees are established in exact arithmetic, whereas implementations must approximate least-squares directions, boundary updates, and sampling probabilities in finite precision. This is important because small numerical errors can change which coordinates freeze and thereby alter the subsequent trajectory. We analyze the concentration of the perturbed Gram-Schmidt walk directly under bounded, potentially biased and history-dependent errors. For $n$ input vectors of Euclidean norm at most one, we obtain a modified MGF bound depending on key error sources which recovers the original result as the error goes to zero. We also construct a full-column-rank instance in which bounded update errors produce bias of order $\min\{n^2\varepsilon,n\}$, showing that updates accumulate error unavoidably under this model. Finally, we validate our findings in a variety of settings by ablating on the bit precision and problem size.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.08562 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:13:03.927Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).