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.