Past exam of the numerical linear algebra course of the University of Oxford / 2025 / 2

By the Eckart-Young-Mirsky theorem, truncate the singular value decomposition:The same $A_r$ minimizes the spectral norm and Frobenius norm errors over matrices of matrix rank at most $r$. This conventional meaning of rank-$r$ low-rank approximation includes the case $\mathrm{rank}A<r$, when $A_r=A$.

Choose the first $r$ left singular vectors:Their orthonormality gives $Q_{\ast }^T{Q}_{\ast }=I_r$. The orthogonal projection $Q_{\ast }{Q}_{\ast }^T$ fixes $u_j$ for $j\le r$ and annihilates $u_j$ for $j>r$. Applying it to the singular value decomposition therefore gives

Put $P=Q{Q}^T$. Since $Q$ has $r$ columns, the rank bound for a matrix product gives $\mathrm{rank}(PA)\le r$. The Eckart-Young-Mirsky theorem and part (a) then giveOne can also see the lower bound directly. The restriction of $PA$ to the $(r+1)$-dimensional linear span of $v_1,\dots ,v_{r+1}$ has a nonzero null space, because its matrix rank is at most $r$. For a unit vector $z$ in that null space, $\Vert (A-PA)z{\Vert }_2=\Vert Az{\Vert }_2\ge {\sigma }_{r+1}$ by the singular value decomposition.

The orthogonal projection $P=Q{Q}^T$ givesThe first summand has every column in the column space of $Q$, and the second has every column in its orthogonal complement. They therefore have zero Frobenius inner product. The Pythagorean identity, together with $Q^{T}Q=I_r$, gives the stronger exact formulaConsequentlywith equality exactly when $M=Q^{T}A$. Thus solving the linear least-squares problem for each column chooses the best coefficients in the prescribed column space.

The thin QR decomposition gives $AX=QR$. Its columns already belong to the column space of $Q$, so the orthogonal projection $Q{Q}^T$ leaves them fixed:This identity uses only $AX=QR$ and $Q^{T}Q=I_r$; it remains valid if $R$ is singular, provided such a factorization with orthonormal $Q$ is used.

Because $r<n$, choose a unit vector $v$ in the null space of $X^T$, so that $v^{T}X=0$. Let $J\in {\mathbb{R}}^{m\times n}$ have orthonormal columns, for example the first $n$ columns of $I_m$, and choose a real number $\alpha >1$. SetIts singular value along $v$ is $\alpha$, and its other singular values are $1$. Thus ${\sigma }_1(A)=\alpha >1={\sigma }_2(A)$. Meanwhile $AX=JX$. If $X$ has full column rank, the column space of the thin QR decomposition is exactly $\mathrm{range}(JX)$, which is orthogonal to $Jv$. Hence $PJv=0$ for $P=Q{Q}^T$, andConversely, an orthogonal projection is a contraction in the Euclidean norm, so $\Vert (I_m-P)A{\Vert }_2\le \Vert A{\Vert }_2=\alpha$. ThereforeIf $X$ is rank deficient, complete the QR decomposition within $J(v^{\perp })$: this space has dimension $n-1\ge r$ and contains all columns of $JX$, so the required orthonormal completion exists there. The same proof applies. For rank-deficient data the choice of unused columns of $Q$ matters; the construction specifies a valid choice. If $Q$ instead contains only a basis of $\mathrm{range}(AX)$, the conclusion holds without any completion. A fixed sampling matrix can thus miss the unique largest singular value completely.

Write $\ell =r/2$; the requested expression requires the positive even integer $r\ge 2$. Split the thin singular value decomposition after $\ell$ columns:Here $\Vert D_b{\Vert }_2={\sigma }_{\ell +1}=\Vert A-A_{\ell }{\Vert }_2$. Each column of a Gaussian random matrix is an orthogonally invariant random vector: its probability density function is proportional to $\exp (-\Vert z{\Vert }_2^2/2)$, and an orthogonal matrix preserves both $\Vert z{\Vert }_2$ and volume. Thus $V^{T}X$, where $V=[V_a,V_b]$, again has independent and identically distributed standard normal entries. In particular both displayed blocks have the Gaussian distributions needed below.

First prove a deterministic error bound for a randomized range finder. Put $P=Q{Q}^T$ and suppose ${\Omega }_a$ has full row rank. Its Moore-Penrose pseudoinverse is ${\Omega }_a^{†}={\Omega }_a^T({\Omega }_a{\Omega }_a^T{)}^{-1}$, so ${\Omega }_a{\Omega }_a^{†}=I_{\ell }$. The QR decomposition implies $(I_m-P)AX=0$, henceMultiplication by ${\Omega }_a^{†}$ expresses the missed leading columns in terms of the trailing columns. Substitution into $(I_m-P)A$ gives the exact identityFor any matrix $F$, the spectral norm of $[-FI]$ is $\sqrt{1+\Vert F{\Vert }_2^2}$, because its product with its transpose is $F{F}^T+I$. Using submultiplicativity of the operator norm, the orthonormality of $U_b$, and the contraction property of the orthogonal projection, we obtainThis estimate is deterministic and also covers rank-deficient $A$; if ${\sigma }_{\ell +1}=0$, its right-hand side vanishes.

Now use the paper's permitted singular value estimates. Apply the lower estimate to the tall matrix ${\Omega }_a^T$ of size $r\times \ell$, rather than to its wide transpose. It givesThe upper estimate for ${\Omega }_b$, transposing if necessary, givesThus, with $K=2/(1-1/\sqrt{2})$,Since $n/r>1$, the deterministic estimate yieldsThis proves the requested conclusion under the explicitly authorized estimates.

The probabilistic qualification is necessary. A Gaussian random matrix does not always have all its singular values between the two endpoints printed in the hint. Already a $1\times 1$ example would require $|Z|\le 2$ for every standard normal random variable $Z$, which fails with positive probability. The proof above holds on the event where the two block estimates hold. In a probabilistic formulation one supplies estimates for that event, usually allowing a positive margin in both endpoints; no failure probability is specified by the paper.

Nor can the requested inequality with one universal $C$ hold almost surely for every $A$. For example, take $n=m=3$, $r=2$, $A=\mathrm{diag}(L,1,1)$ with $L>1$, and a sampling matrixAt $X_0$, the sampled column space misses the first coordinate, so $\Vert A-\hat{A}{\Vert }_2=L$, whereas $\Vert A-A_1{\Vert }_2=1$. Choose $L>C\sqrt{3/2}$. Because $A{X}_0$ has full column rank, its orthogonal projection depends continuously on $X$ near $X_0$ through $AX(X^T{A}^{T}AX{)}^{-1}{X}^T{A}^T$. The strict violation persists in an open neighborhood of $X_0$. The joint Gaussian probability density function is positive there, so that neighborhood has positive probability. This identifies the missing qualification without weakening the conditional calculation.