Probabilistic Analysis of Least Squares, Orthogonal Projection, and QR Factorization Algorithms Subject to Gaussian Noise

arXiv:2409.18905v3 Announce Type: replace-cross Abstract: We consider the effect of Gaussian perturbations on least-squares residuals, orthogonal projections, and QR-type algorithms. The problem that motivated our investigations is as follows: suppose that a full column-rank matrix (BinR^{mimes n}) has already been computed, and suppose that a new normalized column (q=(x+y)/|x+y|_2) is to be appended to (B), where (xperpoperatorname{span}(B)) is the ideal orthogonal component and (y) represents the orthogonalization error. How large can the condition number (kappa([B,q])) of the resulting matrix ([B,q]) become? While we provide a Weyl-type bound on the singular values of ([B,q]), in terms of the extremal singular values of (B) and the quantity (|B^T y|_2/|x+y|_2), we also derive exact probability laws for norms and projection residuals under Gaussian perturbations. Finally, we use these probability laws to derive probabilistic condition-number bounds for QR-type processes with imperfect orthogonalization and exact normalization.

Source: arXiv cs.LG | 2026-06-23