Finite-Precision Gram-Schmidt Walks
TL;DR
This work analyzes the concentration of the perturbed Gram-Schmidt walk directly under bounded, potentially biased and history-dependent errors, and constructs 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.
Abstract
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.