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

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$.