Why A⁺b Is the Minimum-Norm Least-Squares Solution

Two Different Minimization Questions

For a matrix equation \(\mathbf{A}\mathbf{x}=\mathbf{b}\), an exact solution may not exist. A least-squares solution is an \(\mathbf{x}\) that makes the residual \(\mathbf{A}\mathbf{x}-\mathbf{b}\) as small as possible in the Euclidean norm. There may be more than one such \(\mathbf{x}\): changing \(\mathbf{x}\) in a direction that \(\mathbf{A}\) sends to zero does not change the residual. The pseudoinverse selects one particular least-squares solution, and this tutorial proves why it has the smallest norm among all of them.

Let \(\mathbf{A}\in\mathbb{F}^{m\times n}\), where \(\mathbb{F}=\mathbb{R}\) or \(\mathbb{C}\), and let \(\mathbf{b}\in\mathbb{F}^m\). The norm \(\|\cdot\|_2\) is the Euclidean norm, so for a vector \(\mathbf{q}\) its square is the sum of the squared absolute values of its entries. A least-squares solution minimizes \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_2\) over all \(\mathbf{x}\in\mathbb{F}^n\). Among these minimizers, a minimum-norm least-squares solution minimizes \(\|\mathbf{x}\|_2\).

Here \(\mathbf{U}^{*}\) and \(\mathbf{V}^{*}\) denote conjugate transposes; in the real case, they are transposes. The full SVD, including the singular vectors corresponding to zero singular values, lets us keep track of every possible component of \(\mathbf{x}\) and \(\mathbf{b}\). The SVD and the formula for \(\mathbf{A}^{+}\) are the starting point; the argument below establishes the claimed minimization directly from them.

Coordinates That Preserve Length

Write the columns of \(\mathbf{U}\) as \(\mathbf{u}_1,\dots,\mathbf{u}_m\), and those of \(\mathbf{V}\) as \(\mathbf{v}_1,\dots,\mathbf{v}_n\). Since these matrices are unitary, every \(\mathbf{b}\in\mathbb{F}^m\) and \(\mathbf{x}\in\mathbb{F}^n\) has coordinates \(\mathbf{y}=\mathbf{U}^{*}\mathbf{b}\) and \(\mathbf{z}=\mathbf{V}^{*}\mathbf{x}\). Equivalently, \(\mathbf{b}=\mathbf{U}\mathbf{y}\) and \(\mathbf{x}=\mathbf{V}\mathbf{z}\). The component \(y_i\) is the coordinate of \(\mathbf{b}\) along \(\mathbf{u}_i\), and \(z_j\) is the coordinate of \(\mathbf{x}\) along \(\mathbf{v}_j\).

Proof. Unitarity means \(\mathbf{Q}^{*}\mathbf{Q}=\mathbf{I}\). Therefore \[ \|\mathbf{Q}\mathbf{q}\|_2^2 =(\mathbf{Q}\mathbf{q})^{*}(\mathbf{Q}\mathbf{q}) =\mathbf{q}^{*}\mathbf{Q}^{*}\mathbf{Q}\mathbf{q} =\mathbf{q}^{*}\mathbf{q} =\sum_i |q_i|^2. \] This applies to real orthogonal matrices as well, since then \(\mathbf{Q}^{*}=\mathbf{Q}^{\top}\). \(\square\)

In these coordinates, the SVD gives \(\mathbf{U}^{*}\mathbf{A}\mathbf{x}=\boldsymbol{\Sigma}\mathbf{z}\). The first \(r\) entries of this product are \(\sigma_i z_i\); all further entries, if any, are zero. Thus each positive singular value controls one coordinate of the fitted vector, while coordinates \(z_j\) with \(j>r\) do not affect the fitted vector at all.

The first identity follows by applying the lemma to \(\mathbf{U}^{*}(\mathbf{A}\mathbf{x}-\mathbf{b})=\boldsymbol{\Sigma}\mathbf{z}-\mathbf{y}\). The second follows by applying it to \(\mathbf{x}=\mathbf{V}\mathbf{z}\). A sum with no terms is understood to be zero; this convention covers \(r=0\) and the cases in which \(r=m\) or \(r=n\).

The Minimum-Norm Least-Squares Theorem

Proof. Set \(\mathbf{y}=\mathbf{U}^{*}\mathbf{b}\) and \(\mathbf{z}=\mathbf{V}^{*}\mathbf{x}\). By the coordinate formula for the residual, its squared norm is a sum of terms \(|\sigma_i z_i-y_i|^2\) for \(1\le i\le r\), plus the fixed term \(\sum_{i=r+1}^{m}|y_i|^2\). Each term \(|\sigma_i z_i-y_i|^2\) is nonnegative, and it equals zero exactly when \(z_i=y_i/\sigma_i\), because \(\sigma_i>0\). Consequently the residual is minimized exactly when \(z_i=y_i/\sigma_i\) for every \(1\le i\le r\). There is no restriction on \(z_j\) for \(r<j\le n\), because those coordinates do not occur in the residual.

By the definition of the pseudoinverse from the SVD, \[ \mathbf{A}^{+}\mathbf{b} =\mathbf{V}\boldsymbol{\Sigma}^{+}\mathbf{U}^{*}\mathbf{b} =\mathbf{V}\mathbf{z}^{(0)}, \] where \(z^{(0)}_i=y_i/\sigma_i\) for \(1\le i\le r\) and \(z^{(0)}_j=0\) for \(r<j\le n\). This vector meets all the conditions for minimizing the residual, so it is a least-squares solution. Any other least-squares solution has the same first \(r\) coordinates and arbitrary remaining coordinates. Transforming back with \(\mathbf{V}\), it has exactly the stated form.

Finally, for any least-squares solution with coordinates \(z_j\), its squared norm is \[ \|\mathbf{x}\|_2^2 =\sum_{i=1}^{r}\left|\frac{y_i}{\sigma_i}\right|^2 +\sum_{j=r+1}^{n}|z_j|^2. \] The second sum is nonnegative and is zero exactly when every \(z_j=0\) for \(j>r\). Hence the smallest norm is attained when all those free coordinates vanish, and it is attained only then. That solution is \(\mathbf{A}^{+}\mathbf{b}\). If \(r=0\), the same reasoning says every \(\mathbf{x}\) minimizes the constant residual \(\|\mathbf{b}\|_2\), and only \(\mathbf{x}=\mathbf{0}=\mathbf{A}^{+}\mathbf{b}\) has the smallest norm. \(\square\)

The theorem separates the two optimization tasks. The residual determines the first \(r\) coordinates of a solution, but it says nothing about the remaining \(n-r\) coordinates. The norm minimization then sets those free coordinates to zero. This is why the conclusion includes both a least-squares property and a separate, unique minimum-norm property.

Worked Examples in Singular-Vector Coordinates

Common Mistake: Least-Squares Does Not Always Mean Unique

A frequent error is to find one least-squares solution and assume it must be the only one. In the rank-one example, \((1/2,0)^{\top}\) is indeed a least-squares solution: its fitted vector is \((1/2,1/2)^{\top}\), giving the same minimum residual norm \(\sqrt{1/2}\). But it is not the minimum-norm solution, because \[ \left\|\begin{bmatrix}1/2\\0\end{bmatrix}\right\|_2^2=\frac14 \quad\text{while}\quad \left\|\begin{bmatrix}1/4\\1/4\end{bmatrix}\right\|_2^2=\frac18. \] The correction is to distinguish the residual objective from the norm of the unknown: first identify which coordinates minimize the residual, then set every unconstrained right singular-vector coordinate to zero to minimize \(\|\mathbf{x}\|_2\).

Another version of the same mistake is to try to invert every diagonal entry of \(\boldsymbol{\Sigma}\), including zeros. The definition of \(\boldsymbol{\Sigma}^{+}\) takes reciprocals only of the positive singular values; it places zero in the positions corresponding to zero singular values. Dividing by zero is not a valid way to determine a solution coordinate. Those coordinates are free for the residual minimization and are set to zero only for the minimum-norm choice.

What the Result Tells Us

The residual minimization depends on the left singular-vector coordinates of \(\mathbf{b}\): its components along the first \(r\) left singular vectors can be fitted, and the remaining components contribute an unavoidable residual. The solution norm, in turn, depends on the right singular-vector coordinates of \(\mathbf{x}\). The positive singular values force the first \(r\) coordinates of every minimizer, whereas any remaining coordinates can only increase the norm. The pseudoinverse combines these two observations in one formula: it scales the data coordinates by \(1/\sigma_i\) in the directions that can be fitted and assigns zero to the unconstrained directions.

This distinction matters whenever a system is inconsistent, underdetermined, or rank deficient. A least-squares answer alone specifies the best achievable fit; the minimum-norm requirement supplies a principled and unique choice when several unknown vectors give that same fit.