= Solution
{c}
The <Euclidean norm> is invariant under an <orthogonal matrix>, so the full <singular value decomposition> gives
$$
\begin{aligned}
\|Ax-b\|_2^2
&=\left\|\begin{pmatrix}\Sigma V^Tx-U^Tb\\-U_\perp^Tb\end{pmatrix}\right\|_2^2\\
&=\|\Sigma V^Tx-U^Tb\|_2^2+\|U_\perp^Tb\|_2^2.
\end{aligned}
$$
The 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 therefore
$$
\boxed{x_*=V\Sigma^{-1}U^Tb=A^+b,\qquad
\min_x\|Ax-b\|_2=\|U_\perp^Tb\|_2.}
$$
Here $A^+=V\Sigma^{-1}U^T$ is the <Moore-Penrose inverse>, and the fitted <vector> is the <orthogonal projection> $Ax_*=UU^Tb$ onto the <image of a linear map> defined by $A$.
With the <singular value decomposition> supplied, forming $U^Tb$ costs $O(mn)$ <arithmetic operations>, diagonal scaling costs $O(n)$, and multiplication by $V$ costs $O(n^2)$. Since $m\geq n$,
$$
\boxed{\text{Cost per right-hand side: }O(mn+n^2)=O(mn).}
$$
One need not form $U_\perp$, $A^+$ or $A^TA$ to calculate $x_*$. Computing the needed thin <singular value decomposition> first has standard dense cost $O(mn^2)$; explicitly forming an entire $m\times m$ orthogonal completion can require additional work when $m$ is much larger than $n$.
Back to article page
