Past exam of the numerical analysis course of the University of Oxford / 2021 / 2

Throughout Question 2(a) and 2(b), write $U=[u_1,\dots ,u_n]$, $V=[v_1,\dots ,v_n]$, and $\Sigma =\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_n)$. Then the supplied full singular value decomposition can also be written $A=U\Sigma V^T$, with $U^{T}U=V^{T}V=I_n$ and $[U,U_{\perp }]$ an $m\times m$ orthogonal matrix.

All $n$ singular values are positive, so $\Sigma$ and $V$ are invertible matrices and $A$ has matrix rank $n$. The image of a linear map is thereforewith those columns furnishing an orthonormal basis. Also $Ax=0$ implies $\Sigma V^{T}x=0$ and hence $x=0$. ThusFinally $A^{T}z=V\Sigma U^{T}z=0$ exactly when $U^{T}z=0$. The remaining columns of the full orthogonal matrix span this orthogonal complement:If $m=n$, this last null space also equals $\{0\}$ and has the empty basis.

For $m=n$, $U$ and $V$ are square orthogonal matrices. Multiply the linear system successively by $U^T$, ${\Sigma }^{-1}$ and $V$ to obtainWith the singular value decomposition already supplied, compute $c=U^{T}b$, divide $c_j$ by ${\sigma }_j$, then form $x=Vc$. The two dense matrix-vector products each cost $O(n^2)$ arithmetic operations in Big O notation, and the diagonal scaling costs $O(n)$. ThusIf the singular value decomposition first has to be computed, its usual dense cost is $O(n^3)$; that is a separate setup cost and can be reused for further right-hand sides.

The Euclidean norm is invariant under an orthogonal matrix, so the full singular value decomposition givesThe second term is independent of $x$; the first attains its unique minimum zero because $\Sigma$ is an invertible matrix. The linear least squares solution is thereforeHere $A^{+}=V{\Sigma }^{-1}{U}^T$ is the Moore-Penrose inverse, and the fitted vector is the orthogonal projection $A{x}_{\ast }=U{U}^{T}b$ onto the image of a linear map defined by $A$.

With the singular value decomposition supplied, forming $U^{T}b$ costs $O(mn)$ arithmetic operations, diagonal scaling costs $O(n)$, and multiplication by $V$ costs $O(n^2)$. Since $m\ge n$,One need not form $U_{\perp }$, $A^{+}$ or $A^{T}A$ to calculate $x_{\ast }$. Computing the needed thin singular value decomposition first has standard dense cost $O(m{n}^2)$; explicitly forming an entire $m\times m$ orthogonal completion can require additional work when $m$ is much larger than $n$.

Retain the first $r$ terms in the singular value decomposition:The Eckart-Young-Mirsky theorem says that this truncated singular value decomposition is a best low-rank approximation in the spectral norm. The remaining singular values of the difference are ${\sigma }_{r+1},\dots ,{\sigma }_n$, together with zeros, soFor $r\ge 1$ the displayed matrix has matrix rank exactly $r$, since every retained singular value is positive. For $r=0$, the only matrix of matrix rank zero is the zero matrix, and the same formula gives error ${\sigma }_1$.

Take the identity matrixBoth $B_1$ and $B_2$ have matrix rank one, andThey are distinct and both attain the minimum spectral norm error from the preceding part. Hence a best low-rank approximation of rank one need not be unique. More generally, every orthogonal projection $u{u}^T$ with $\Vert u{\Vert }_2=1$ gives another such minimizer.

No. Distinct singular values do not force uniqueness in the spectral norm. For an explicit example takeThe singular values of $A$ are $2>1>0$. Every $B_t$ has matrix rank one, and its error in the spectral norm isThus there are infinitely many best rank-one approximations even with a strict gap between the singular values.

The same mechanism works for every $1\le r<n$ under the question's positive singular values. Starting with $A_r$, defineWhen the singular values are distinct, ${\sigma }_1+t\ge {\sigma }_1-{\sigma }_{r+1}>0$, so every $B_t$ has matrix rank $r$, whileThe spectral norm measures only the largest remaining singular value, leaving room to change retained components without increasing that maximum. This is the nonuniqueness of spectral-norm low-rank approximation. The exceptional case $r=0$ is unique for the elementary reason given above.

We use the spectral theorem to construct a sufficiently accurate approximate eigenpair. Complete $x$ to an orthonormal eigenbasis $x,x_2,\dots ,x_n$ of the symmetric matrix $B$, with corresponding eigenvalues $\lambda ,{\lambda }_2,\dots ,{\lambda }_n$. Simplicity of $\lambda$ means that every ${\lambda }_j-\lambda$ below is nonzero. PutThe orthogonal decomposition of $Ex$ shows that $x^{T}v=0$ andWith $u_{\epsilon }=x+\epsilon v$ and ${\mu }_{\epsilon }=\lambda +\epsilon a$, direct expansion cancels every first-order term:Also $\Vert u_{\epsilon }{\Vert }_2^2=1+{\epsilon }^2\Vert v{\Vert }_2^2\ge 1$. Thus its eigenpair residual has Euclidean norm $O({\epsilon }^2)$ in Big O notation.

For completeness, a real symmetric matrix $M$ always has an eigenvalue within $\Vert (M-\mu I)u{\Vert }_2/\Vert u{\Vert }_2$ of any real $\mu$ and nonzero $u$. Indeed, writing $u={\sum }_j{c}_j{q}_j$ in an orthonormal eigenbasis with eigenvalues ${\theta }_j$ givesApply this symmetric eigenvalue residual bound to $M=B+\epsilon E$. There is an eigenvalue ${\lambda }_{\epsilon }$ such thatwhich provesThis establishes the first-order perturbation of a simple symmetric eigenvalue without presupposing differentiability of the perturbed eigenvector. If $n=1$, the sum defining $v$ is empty and the displayed eigenvalue formula is exact.