A linear system can fail to determine its input for two different reasons. The target may lie outside the column space, so no exact input produces it. Alternatively, different inputs may produce the same output because the kernel is nonzero. These phenomena can occur together. Least squares addresses the first by choosing a closest attainable output; minimum norm addresses the second by choosing a particular input among all inputs producing that output. Keeping those choices separate makes rank-deficient problems much easier to understand.
SVD coordinates and the least-squares family
Definition 3.2.1
(Least-squares and minimum-norm solutions)
For and , a vector is a least-squares solution if is as small as possible over all . Among all least-squares solutions, a minimum-norm solution is one with the smallest .
Theorem 3.2.2
(All least-squares solutions through the SVD)
Let be a full SVD of rank , with positive singular values and . The least-squares solutions are exactly with arbitrary , that is, . The unique minimum-norm one is , and .
Proof
(Pythagoras in singular-vector coordinates)
Let be a real matrix and let . Suppose its rank is , and take a full singular value decomposition , where and are orthogonal. Its positive singular values are , and for , while for . These equalities also cover rank zero, when there are no positive singular values.
Write and , with . Orthogonality gives
Each term in the first sum is nonnegative and can independently be made zero because . The second sum cannot be changed by any . Therefore all least-squares solutions satisfy for , with arbitrary for . The common fitted vector is : only the part of in the column space can be fitted. The remainder is orthogonal to that space, which independently certifies the minimum by Pythagoras.
In the orthonormal coordinates, . The fixed first coefficients are unavoidable; every other squared coefficient can only increase the norm. Hence the unique minimum-norm least-squares solution is
Its uniqueness follows from equality in the sum of squares, not from assuming is invertible. The complete family is , and . For the sums are empty: , every is a least-squares solution, and the unique smallest one is . We never divide by a zero singular value.
Proof X-ray
Why one orthogonal change of coordinates settles everything
The key move is to expand both and in the orthonormal bases and , which turns into a sum of independent squares. The hypothesis is used exactly once: it lets each of the first squares be driven to zero by . The remaining sum does not contain at all, so it is a certificate that nothing smaller is possible. Minimum norm needs no new idea: in the coordinates , the first coefficients are forced, and any nonzero free coefficient only increases the sum. No invertibility of is assumed, and for every sum is empty.
The full-rank QR shortcut
Proposition 3.2.3
(Least squares by thin QR)
Let and let be a thin QR factorization with having orthonormal columns and an invertible upper triangular matrix. Then for all , so the unique least-squares solution solves .
Proof
(Splitting along the columns of )
If and the columns of are independent, thin QR gives , where has orthonormal columns and is an invertible upper triangular matrix. Decompose . The second component is perpendicular to every column of , so
The first term is zero at the unique solution of ; triangular back-substitution finds it. This certificate requires both orthonormal columns and invertible . If the columns are dependent, Gram–Schmidt encounters a zero residual, and this particular inverse-based shortcut cannot be used. A rank-revealing factorization or SVD can still solve the least-squares problem.
Counterexample mode
The normal-equation inverse needs independent columns
Claim: every least-squares problem is solved by . This is false when the columns are dependent.
For example, has dependent columns. With , all pairs satisfying give the same closest output , but only has minimum coefficient norm. The normal matrix is singular, so writing is invalid. Least squares itself has not failed; the proposed inverse formula has.
Conditioning and what the comparison means
Proposition 3.2.4
(Squaring the condition number)
For a nonzero full-column-rank , define the two-norm condition number as , where the minimum is over all positive singular values. The eigenvalues of are , so
This is an exact statement about the matrices and the two-norm; it does not say every computed answer loses precisely twice as many digits. A small singular value means some unit input direction produces a small output, so recovering its coefficient is sensitive to perturbations. Forming normal equations can magnify conditioning and can introduce rounding in the product. QR avoids explicitly forming that product, although neither a stable algorithm nor a factorization removes sensitivity inherent in the data. If rank is deficient, the usual full-column-rank condition number is infinite and the inverse formula is unavailable.
A useful diagnostic is to ask which conclusion a rank statement supports. Full column rank makes the coefficient vector unique for every target, even if the target is not exactly attainable. Full row rank makes every target attainable, but if there are more columns than rows, exact coefficients can still be nonunique. These are different properties: uniqueness concerns the kernel, while attainability concerns the column space. A residual check certifies the fit, and a kernel check certifies uniqueness of its coefficients.
Concept lensGeometric
Least squares as projection onto the column space
The same solution set has a picture without coordinates. The fitted vector is the orthogonal projection of onto the column space of (the space spanned by its column vectors, that is, the range of ), which is why every least-squares solution gives the same fit. The least-squares solutions are exactly the preimage of that projection, a translate of . The minimum-norm solution is the unique point of this translate lying in , the row space of .
Worked examples
Worked example 3.2.5
(Inconsistent data and nonunique coefficients)
Let and . Find every least-squares solution and its unique minimum-norm member.
Solution. The column space is generated by . The projection coefficient of on is , so the fitted vector is . A coefficient vector fits it exactly when . Write . The two displayed vectors are perpendicular, so and the unique minimum occurs at . The residual is perpendicular to , confirming least-squares optimality. It is nonzero, so no exact solution exists.
Worked example 3.2.6
(Conditioning and an exact QR solve)
Let and . Find the solution and compare the two condition numbers.
Solution. Take and . Both diagonal entries of are nonzero, so yields , and checks the result. The singular values are and , giving . The eigenvalues of are and , giving . A perturbation of in the second component of changes the second coefficient by : a tenfold absolute amplification in that direction. This illustrates sensitivity without claiming a particular floating-point error.
Worked example 3.2.7
(The zero matrix: a rank-zero edge case)
Let be the zero matrix and . There are no positive singular values, so all sums over are empty. Every is a least-squares solution, because for all . The kernel is all of and the unique minimum-norm solution is . We never divide by a zero singular value, and the residual is not reduced by any choice of .
Common mistakes and subtle points
Common mistake
(Dividing by a zero singular value)
Writing over all is meaningless when . Only the first terms occur; the directions with are free, and the minimum-norm choice sets their coefficients to zero.
Common mistake
(Mixing up uniqueness and attainability)
Full column rank makes the coefficients unique for every , even when is not attainable. Full row rank makes every attainable, but with more columns than rows the exact solutions are still not unique. Uniqueness is a statement about the kernel; attainability is a statement about the column space.
Exercises
Quick check
(For and , find the least-squares solution and the residual.)
There is one unknown; project on the single column.
Solution · Answer
and , so . The residual is , which is perpendicular to the column because .
Quick check
(For and , find the minimum-norm least-squares solution and the norm of its residual.)
Only the positive singular value contributes to .
Solution · Answer
Here , , and , so . The residual is , of norm .
Quick check
(If is of rank , is the least-squares solution of unique? Which solution does select?)
Compare the kernel dimension with .
Solution · Answer
No. Every is attainable, so least-squares solutions are exact solutions, and they form an affine family of dimension . The vector is the one of smallest norm, the one perpendicular to .