= Deterministic error bound for a randomized range finder
{title2=$\|(I-QQ^T)A\|_2\leq\sigma_{\ell+1}\sqrt{1+\|\Omega_b\Omega_a^\dagger\|_2^2}$}
Split a thin <singular value decomposition> at $\ell$, writing $A=U_aD_aV_a^T+U_bD_bV_b^T$ and $\Omega_i=V_i^TX$. Suppose $\Omega_a$ has <full row rank> and the <column space> of $Q$ contains that of $AX$. With $P=QQ^T$, the identity $(I-P)AX=0$ and the <Moore-Penrose pseudoinverse> give
$$
(I-P)A=(I-P)U_bD_b[-\Omega_b\Omega_a^\dagger\ \ I]V^T.
$$
Since $\|D_b\|_2=\sigma_{\ell+1}$, <submultiplicativity of the operator norm> gives the displayed bound: $[-F\ I][-F\ I]^T=FF^T+I$ proves $\|[-F\ I]\|_2=\sqrt{1+\|F\|_2^2}$. This statement is deterministic. A Gaussian error estimate needs a separate <probability> bound on the two random factors.
Back to article page
