Rank-Deficient Least-Squares Examples

What Rank Deficiency Changes

When a matrix is rank-deficient, some directions in its input space are sent to zero, and some target vectors cannot be reached at all. These two features lead to different questions: an inconsistent system has no exact solution, while an underdetermined system may have multiple exact solutions. Least squares handles the first situation by minimizing the residual; the pseudoinverse selects a particular minimizer, namely the one with smallest norm. In this tutorial, small SVD calculations will make both the residual and the entire family of minimizers explicit.

Work over \(\mathbb{R}\). For \(\mathbf{A}\in\mathbb{R}^{m\times n}\) and \(\mathbf{b}\in\mathbb{R}^m\), a least-squares minimizer is a vector \(\mathbf{x}\in\mathbb{R}^n\) that minimizes \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|\) over all \(\mathbf{x}\). The residual at \(\mathbf{x}\) is \(\mathbf{b}-\mathbf{A}\mathbf{x}\). The system is inconsistent if no \(\mathbf{x}\) satisfies \(\mathbf{A}\mathbf{x}=\mathbf{b}\). A matrix is rank-deficient when its rank is less than the smaller of its numbers of rows and columns.

Recall the SVD pseudoinverse formula. Write an SVD as \(\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\), where \(\mathbf{U}\) and \(\mathbf{V}\) are orthogonal matrices. If the rank is \(r\), the positive singular values are \(\sigma_1,\dots,\sigma_r\), and the corresponding left and right singular vectors are \(\mathbf{u}_i\) and \(\mathbf{v}_i\). Then

Only positive singular values are inverted. Zero singular values are omitted, rather than divided into. This is essential for rank-deficient matrices. The earlier results on least squares and the pseudoinverse give the candidate minimum-norm minimizer \(\mathbf{A}^{+}\mathbf{b}\); the singular-coordinate argument below explains both why it minimizes the residual and how to find all the other minimizers.

The Full Family of Least-Squares Minimizers

Proof. Set \(\mathbf{y}=\mathbf{U}^{\top}\mathbf{b}\) and \(\mathbf{z}=\mathbf{V}^{\top}\mathbf{x}\). Since \(\mathbf{U}\) and \(\mathbf{V}\) are orthogonal, they preserve norms, and \(\mathbf{x}=\mathbf{V}\mathbf{z}\). The first \(r\) diagonal entries of \(\boldsymbol{\Sigma}\) are \(\sigma_1,\dots,\sigma_r>0\); all its other entries are zero. Therefore

The second sum does not depend on \(\mathbf{x}\). Each term in the first sum is nonnegative and can be made zero by setting \(z_i=y_i/\sigma_i\). Since each \(\sigma_i\) is positive, this is the unique minimizing choice for each \(i\le r\). No term in the objective depends on \(z_{r+1},\dots,z_n\), so those coordinates are arbitrary. The SVD formula for \(\mathbf{A}^{+}\) gives \(\mathbf{A}^{+}\mathbf{b}=\mathbf{V}\mathbf{z}_0\), where \((\mathbf{z}_0)_i=y_i/\sigma_i\) for \(i\le r\) and \((\mathbf{z}_0)_j=0\) for \(j>r\). Thus all the minimizers have the stated form.

For any such minimizer, orthogonality of the columns of \(\mathbf{V}\) gives \(\|\mathbf{x}\|^2=\sum_{i=1}^{r}(y_i/\sigma_i)^2+\sum_{j=r+1}^{n}c_j^2\). This is smallest exactly when every \(c_j=0\), and that choice is unique. Finally, the residual in \(\mathbf{U}\)-coordinates has entries \(0\) for \(i\le r\) and \(y_i\) for \(i>r\). Multiplying back by \(\mathbf{U}\) gives the residual formula in the theorem. These calculations also cover \(r=0\): the first sum is empty, all input coordinates are free, and the smallest-norm choice is \(\mathbf{0}\). \(\square\)

The vectors \(\mathbf{v}_{r+1},\dots,\mathbf{v}_n\) describe the directions that do not change \(\mathbf{A}\mathbf{x}\). Indeed, for \(j>r\), the corresponding singular value is zero, so \(\mathbf{A}\mathbf{v}_j=\mathbf{0}\). The theorem therefore separates two tasks: the positive singular directions determine the best fit, while the zero singular directions account for every other minimizer.

An Inconsistent System with a Nonzero Residual

Underdetermined Systems: Exact Fits and Many Solutions

An underdetermined system has more unknowns than equations. It can have infinitely many exact solutions when the target is reachable. If the matrix is also rank-deficient, some input directions may remain free even after imposing the exact-fit condition. The next two examples use the same matrix with different right-hand sides: one is reachable, and one is not.

A Common Mistake: Treating the Pseudoinverse Output as an Exact Solution

For the last example, a tempting but incorrect calculation is to claim that \(\mathbf{A}^{+}\mathbf{b}\) solves \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Substitution shows otherwise:

The correction is to distinguish an exact solution from a least-squares minimizer. Here the pseudoinverse output minimizes the residual, but it cannot make that residual zero. A second mistake is to report only this one vector when asked for all minimizers. Adding \(\begin{bmatrix}s\\-s\\t\end{bmatrix}\) changes neither the fitted vector nor the residual. It increases the norm unless \(s=t=0\), which is why the pseudoinverse output is the minimum-norm choice rather than the only minimizer.

How to Read a Rank-Deficient Example

A reliable calculation can be organized around three questions. First, what does the SVD say about the reachable part of the target? Only the left singular-vector directions with positive singular values can be fitted. Second, which input directions are invisible to the matrix? They are the right singular-vector directions associated with zero singular values. Third, what does the requested output require: just the residual, one minimizer, the full family, or the minimum-norm member? Keeping these questions separate prevents a correct pseudoinverse calculation from being mistaken for a complete description.

The distinction matters in applications where different coefficient vectors may produce the same prediction. The residual measures the mismatch between the target and the best reachable fit. The null-space terms describe changes to the coefficients that leave that fit unchanged. Choosing the minimum-norm member gives a well-defined representative without claiming that the other minimizers do not exist.