Randomized range finder ($Y=AX,\hat{A}=Q{Q}^{T}A$)

Choose a random sampling matrix $X$, form $Y=AX$, and find an orthonormal basis $Q$ for the sampled column space by a thin QR decomposition. The low-rank approximation $\hat{A}=Q{Q}^{T}A$ keeps the component of $A$ in that space. Since $Q{Q}^{T}AX=AX$, it reproduces the sampled action exactly. If $Y$ has deficient matrix rank, one can use only a basis of its column space; alternatively an orthonormal completion must be specified.

Split a thin singular value decomposition at $\ell$, writing $A=U_a{D}_a{V}_a^T+U_b{D}_b{V}_b^T$ and ${\Omega }_i=V_i^{T}X$. Suppose ${\Omega }_a$ has full row rank and the column space of $Q$ contains that of $AX$. With $P=Q{Q}^T$, the identity $(I-P)AX=0$ and the Moore-Penrose pseudoinverse giveSince $\Vert D_b{\Vert }_2={\sigma }_{\ell +1}$, submultiplicativity of the operator norm gives the displayed bound: $[-FI][-FI{]}^T=F{F}^T+I$ proves $\Vert [-FI]{\Vert }_2=\sqrt{1+\Vert F{\Vert }_2^2}$. This statement is deterministic. A Gaussian error estimate needs a separate probability bound on the two random factors.