Least Squares in Singular-Vector Coordinates
A system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) need not have an exact solution. Least squares replaces exact equality with a minimization problem: choose \(\mathbf{x}\) so that the residual \(\mathbf{A}\mathbf{x}-\mathbf{b}\) has the smallest possible Euclidean norm. A singular value decomposition (SVD) makes the choices in this problem visible. Each positive singular value determines one coordinate of a minimizer, while coordinates corresponding to zero singular values do not affect the output and may be chosen freely.
Work over \(\mathbb{R}\), with \(\mathbf{A}\in\mathbb{R}^{m\times n}\) and \(\mathbf{b}\in\mathbb{R}^m\). The Euclidean norm of a column vector \(\mathbf{w}\) is \(\|\mathbf{w}\|_2=\sqrt{\mathbf{w}^{\top}\mathbf{w}}\). A least-squares solution is any vector \(\mathbf{x}\in\mathbb{R}^n\) that minimizes \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_2\) over all \(\mathbf{x}\in\mathbb{R}^n\). A minimizer need not make the residual zero; it does so exactly when the system is consistent.
For a full SVD, \(\mathbf{A}\mathbf{v}_j=\sigma_j\mathbf{u}_j\) when \(\sigma_j>0\), and \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\) for every remaining right singular vector. Thus, if \(\mathbf{x}=\mathbf{V}\mathbf{y}\), then \(y_j=\mathbf{v}_j^{\top}\mathbf{x}\) and \(\mathbf{A}\mathbf{x}=\sum_{j=1}^{r}\sigma_j y_j\mathbf{u}_j\). The SVD therefore separates input coordinates that change \(\mathbf{A}\mathbf{x}\) from coordinates that do not.
Deriving Every Minimizer
Because \(\mathbf{U}\) is orthogonal, it preserves Euclidean norms: \(\|\mathbf{w}\|_2=\|\mathbf{U}^{\top}\mathbf{w}\|_2\). Set \(\beta_j=\mathbf{u}_j^{\top}\mathbf{b}\) for \(1\le j\le m\), and write \(\mathbf{x}=\mathbf{V}\mathbf{y}\). In the \(\mathbf{U}\) coordinates, the residual has coordinate \(\sigma_j y_j-\beta_j\) in each positive-singular-value direction, and coordinate \(-\beta_j\) in each remaining left-singular-vector direction. Consequently, its squared norm is a sum of independent squares.
The second sum does not depend on \(\mathbf{x}\). In the first sum, each term is nonnegative and can be made zero by setting \(y_j=\beta_j/\sigma_j\), since \(\sigma_j>0\). These choices can be made independently for every \(j\le r\). Every coordinate \(y_j\) belonging to a zero singular value is absent from the expression, so none of those coordinates affects the residual.
Proof. Since \(\mathbf{V}\) is orthogonal, every \(\mathbf{x}\in\mathbb{R}^n\) has a unique coordinate vector \(\mathbf{y}=\mathbf{V}^{\top}\mathbf{x}\), and \(\mathbf{x}=\mathbf{V}\mathbf{y}\). The displayed residual identity shows that its squared norm is at least \(\sum_{j=r+1}^{m}\beta_j^2\), because every term in the first sum is nonnegative. Equality holds if and only if each of those terms is zero. For \(j\le r\), this condition is \(\sigma_j y_j-\beta_j=0\), which, because \(\sigma_j>0\), is equivalent to \(y_j=\beta_j/\sigma_j\). No condition is imposed on \(y_j\) for \(j>r\), since these coordinates do not occur in the residual expression. Therefore equality, and hence minimization of the norm, holds exactly for the vectors with \(y_j=(\mathbf{u}_j^{\top}\mathbf{b})/\sigma_j\) for \(j\le r\) and arbitrary remaining coordinates. Substituting these coordinates into \(\mathbf{x}=\mathbf{V}\mathbf{y}\) gives the stated formula and includes every minimizer. \(\square\)
The freely chosen part is exactly a null-space vector: each \(\mathbf{v}_j\) with \(j>r\) satisfies \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\), so any combination of these vectors lies in \(\operatorname{Nul}\mathbf{A}\). Conversely, in the SVD coordinates, \(\mathbf{A}\mathbf{x}=\mathbf{0}\) forces \(y_j=0\) for each \(j\le r\), because \(\sigma_j>0\), while the other coordinates are unrestricted. Thus the formula can also be written as one specified vector plus any \(\mathbf{z}\in\operatorname{Nul}\mathbf{A}\).
Proof. For any \(\mathbf{x}\), the squared residual norm is the sum of \(\sum_{j=1}^{r}(\sigma_j y_j-\beta_j)^2\) and \(\sum_{j=r+1}^{m}\beta_j^2\). The first sum can be made zero, and only zero, by the choices \(y_j=\beta_j/\sigma_j\), so the minimum squared norm is \(\sum_{j=r+1}^{m}\beta_j^2\). Taking the nonnegative square root gives the formula. This minimum is zero exactly when every \(\beta_j=0\) for \(j>r\). A zero minimum means that some \(\mathbf{x}\) has \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_2=0\), which is equivalent to \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Since \(\beta_j=\mathbf{u}_j^{\top}\mathbf{b}\), this is precisely the stated consistency condition. \(\square\)
Reading the Formula in Examples
Worked Example: A Full-Column-Rank System
Find the least-squares solution for \(\mathbf{A}=\begin{bmatrix}0&2\\1&0\\0&0\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}3\\5\\4\end{bmatrix}\), and compute its residual norm.
Take \(\mathbf{u}_1=\begin{bmatrix}1\\0\\0\end{bmatrix}\), \(\mathbf{u}_2=\begin{bmatrix}0\\1\\0\end{bmatrix}\), \(\mathbf{u}_3=\begin{bmatrix}0\\0\\1\end{bmatrix}\), and \(\mathbf{v}_1=\begin{bmatrix}0\\1\end{bmatrix}\), \(\mathbf{v}_2=\begin{bmatrix}1\\0\end{bmatrix}\). Then \(\mathbf{A}\mathbf{v}_1=2\mathbf{u}_1\) and \(\mathbf{A}\mathbf{v}_2=\mathbf{u}_2\), so the positive singular values are \(\sigma_1=2\) and \(\sigma_2=1\). The coefficients are \(\mathbf{u}_1^{\top}\mathbf{b}=3\) and \(\mathbf{u}_2^{\top}\mathbf{b}=5\). The formula gives
Check: \(\mathbf{A}\mathbf{x}=\begin{bmatrix}0&2\\1&0\\0&0\end{bmatrix}\begin{bmatrix}5\\ \frac{3}{2}\end{bmatrix}=\begin{bmatrix}3\\5\\0\end{bmatrix}\). Hence \(\mathbf{A}\mathbf{x}-\mathbf{b}=\begin{bmatrix}0\\0\\-4\end{bmatrix}\), whose norm is \(4\). The minimum-residual formula gives the same result: the only left coordinate beyond the two positive singular values is \(\mathbf{u}_3^{\top}\mathbf{b}=4\). There are no free right coordinates in this example.
Worked Example: A Consistent Rank-Deficient System
Find every least-squares solution for \(\mathbf{A}=\begin{bmatrix}1&1&0\\0&0&2\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}3\\4\end{bmatrix}\).
Choose \(\mathbf{u}_1=\begin{bmatrix}0\\1\end{bmatrix}\), \(\mathbf{u}_2=\begin{bmatrix}1\\0\end{bmatrix}\), \(\mathbf{v}_1=\begin{bmatrix}0\\0\\1\end{bmatrix}\), \(\mathbf{v}_2=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\end{bmatrix}\), and \(\mathbf{v}_3=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\\0\end{bmatrix}\). Direct multiplication gives \(\mathbf{A}\mathbf{v}_1=2\mathbf{u}_1\), \(\mathbf{A}\mathbf{v}_2=\sqrt{2}\mathbf{u}_2\), and \(\mathbf{A}\mathbf{v}_3=\mathbf{0}\). Thus \(\sigma_1=2\), \(\sigma_2=\sqrt{2}\), and \(\mathbf{v}_3\) is a null-space direction. The relevant coefficients are \(\mathbf{u}_1^{\top}\mathbf{b}=4\) and \(\mathbf{u}_2^{\top}\mathbf{b}=3\). Therefore
Check: Multiplying the particular vector gives \(\mathbf{A}\begin{bmatrix}\frac{3}{2}\\ \frac{3}{2}\\2\end{bmatrix}=\begin{bmatrix}3\\4\end{bmatrix}=\mathbf{b}\). The added vector is a multiple of \(\mathbf{v}_3\), and \(\mathbf{A}\mathbf{v}_3=\mathbf{0}\), so every displayed \(\mathbf{x}\) also maps to \(\mathbf{b}\). The residual is zero, which is the smallest possible norm.
Worked Example: An Inconsistent Rank-Deficient System
Find every least-squares solution and the minimum residual norm for \(\mathbf{A}=\begin{bmatrix}1&1\\1&1\\0&0\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\0\\2\end{bmatrix}\).
Let \(\mathbf{u}_1=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\end{bmatrix}\), \(\mathbf{u}_2=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\\0\end{bmatrix}\), \(\mathbf{u}_3=\begin{bmatrix}0\\0\\1\end{bmatrix}\), and take \(\mathbf{v}_1=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix}\), \(\mathbf{v}_2=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\-1\end{bmatrix}\). Multiplication gives \(\mathbf{A}\mathbf{v}_1=2\mathbf{u}_1\) and \(\mathbf{A}\mathbf{v}_2=\mathbf{0}\). The only positive singular value is \(2\). Since \(\mathbf{u}_1^{\top}\mathbf{b}=1/\sqrt{2}\), the specified coordinate is \((1/\sqrt{2})/2=1/(2\sqrt{2})\). Hence
Check: For the particular vector, \(\mathbf{A}\begin{bmatrix}\frac14\\ \frac14\end{bmatrix}=\begin{bmatrix}\frac12\\ \frac12\\0\end{bmatrix}\). The added vector is annihilated because its two coordinates sum to zero. Thus every minimizer has residual \(\mathbf{A}\mathbf{x}-\mathbf{b}=\begin{bmatrix}-\frac12\\ \frac12\\-2\end{bmatrix}\), with squared norm \(\frac14+\frac14+4=\frac92\). Equivalently, the unused left coordinates of \(\mathbf{b}\) are \(\mathbf{u}_2^{\top}\mathbf{b}=1/\sqrt{2}\) and \(\mathbf{u}_3^{\top}\mathbf{b}=2\), giving minimum norm \(\sqrt{\frac12+4}=\frac{3}{\sqrt{2}}\).
Common Mistakes and a Reliable Check
Forgetting to divide by the singular value changes the answer. Consider \(\mathbf{A}=\begin{bmatrix}2&0\\0&0\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}4\\3\end{bmatrix}\). Here the positive singular value is \(2\), with left and right singular vector \(\begin{bmatrix}1\\0\end{bmatrix}\); the other right direction is \(\begin{bmatrix}0\\1\end{bmatrix}\). A wrong calculation sets the first coordinate equal to \(\mathbf{u}_1^{\top}\mathbf{b}=4\), giving \(\mathbf{x}=\begin{bmatrix}4\\0\end{bmatrix}\). But \(\mathbf{A}\mathbf{x}=\begin{bmatrix}8\\0\end{bmatrix}\), so the residual is \(\begin{bmatrix}4\\-3\end{bmatrix}\), with norm \(5\). The required coordinate is instead \(4/2=2\), giving every minimizer \(\mathbf{x}=\begin{bmatrix}2\\c\end{bmatrix}\). For these vectors, \(\mathbf{A}\mathbf{x}=\begin{bmatrix}4\\0\end{bmatrix}\), and the residual norm is \(3\), independent of \(c\).
A second error is trying to divide by a zero singular value. The formula divides only for \(j\le r\), where \(\sigma_j>0\). At a zero singular value the corresponding right coordinate is free; it does not have a prescribed value obtained by division. A useful check is to substitute the proposed input into \(\mathbf{A}\mathbf{x}\), then compare its residual norm with the SVD minimum-residual formula. This checks both the determined coordinates and the part of \(\mathbf{b}\) that cannot be matched.
Check Your Understanding
Use singular-vector coordinates in each question, and verify any proposed minimizer by evaluating its residual.
- For a full SVD with one positive singular value \(\sigma_1\), what value must the coordinate \(y_1\) have in a least-squares solution?
- Why can the coordinates belonging to zero singular values be chosen freely without changing the residual?
- Suppose \(m=4\), \(r=2\), and \(\mathbf{u}_3^{\top}\mathbf{b}=1\), \(\mathbf{u}_4^{\top}\mathbf{b}=2\). What is the minimum residual norm?
- For the matrix in the inconsistent worked example, compute \(\mathbf{A}\mathbf{x}\) when \(c=1\), and verify that its residual norm is unchanged.
- State the condition, in terms of the left singular vectors for zero singular values, that is equivalent to \(\mathbf{A}\mathbf{x}=\mathbf{b}\) having a solution.
