Deterministic error bound for a randomized range finder ($\Vert (I-Q{Q}^T)A{\Vert }_2\le {\sigma }_{\ell +1}\sqrt{1+\Vert {\Omega }_b{\Omega }_a^{†}{\Vert }_2^2}$)

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.