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

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 $B\in\mathbb{R}^{m\times 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 $x\perp\operatorname{span}(B)$ is the ideal orthogonal component and $y$ represents the orthogonalization error. How large can the condition number $κ([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.