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∈ℝm× 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 (xperpoperatornamespan(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 (|BT 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.