Motivation
Two identical columns describe the same effect twice. A fitting problem can then determine their sum but cannot determine how the sum should be divided between the two coefficients. Returning one arbitrary division is a valid least-squares answer; calling it the unique answer is incorrect. A minimum-norm rule adds a second, explicit decision: among all best fits, choose the shortest coefficient vector in the declared coordinates.
A small singular value introduces a different difficulty. It is nonzero in exact arithmetic, so its coefficient is determined, but a tiny data change can move that coefficient enormously. Discarding the direction can be sensible when the data cannot resolve it. That step changes the model, however; it is not an algebraic proof that the original matrix has smaller rank.
We develop both decisions from the singular value decomposition, including rectangular and rank-zero cases. The earlier QR unit treated full column rank.
Definitions
Definition 15.1.1
(Singular value decomposition)
Let , with , have rank . A full singular value decomposition is
where and are orthogonal. The rectangular diagonal matrix has these positive entries and otherwise zeros. Vectors and are columns of and .
Definition 15.1.2
(Pseudoinverse and minimum-norm least-squares solution)
The Moore–Penrose pseudoinverse is
If , both sums are empty, so and . The row space is and the nullspace is . A least-squares solution minimizes over all . Its minimum-norm solution minimizes among that complete set of minimizers. This is a two-stage optimization, not the same objective as minimizing for a fixed positive .
Definition 15.1.3
(Thresholded rank and truncated solution)
For a stated absolute threshold , define
The strict inequality specifies what happens exactly at the threshold. Relative thresholds such as , and thresholds based on measurement uncertainty or a rounding budget, are choices requiring a stated interpretation. No single threshold is universally correct for all units and noise levels.
Theorem/Proposition
Theorem 15.1.4
(All least-squares solutions and the unique shortest one)
For every real rectangular and every , all least-squares solutions are
Their fitted vector and residual are unique:
The unique minimum-norm solution is . Its squared norm is
There is a unique least-squares coefficient vector without the minimum-norm qualification exactly when , equivalently when has full column rank. Existence does not require full rank or consistency.
Theorem 15.1.5
(What singular-value truncation guarantees)
Let , and extend the singular-value list by zeros where needed. Truncation gives
where if every positive value is retained. For ,
The vector is the unique minimum-norm least-squares solution for , and also the unique residual minimizer for the original restricted to . It need not minimize the residual over all original coefficient vectors. If , and .
Proof sketch or proof idea
Why an SVD exists
Proof
(Existence from the spectral theorem for )
The real symmetric spectral theorem applies to . Its eigenvalues are nonnegative because . Choose an orthonormal eigenbasis , with positive eigenvalues first. Since , exactly eigenvalues are positive: the kernel equality follows from , and rank–nullity gives the count. For each positive value set . Then
If the eigenvalue associated with is zero, , so . Extend the existing to an orthonormal basis of . Expanding an arbitrary vector in the basis now proves . This uses the symmetric spectral theorem as a prerequisite; it is an existence proof, not a recommendation to compute an SVD by forming . Forming that matrix can square conditioning and erase small directions through rounding.
Repeated singular values allow different orthonormal bases within the corresponding subspaces. Individual singular vectors may therefore be nonunique, while the maps and projections below remain the same.
Separate the directions that can and cannot be fitted
Proof
(Least-squares solutions in singular-vector coordinates)
Write and . Orthogonal invariance gives the identity
The second sum is independent of . Every term in the first sum can be set to zero by choosing . The remaining coordinates of are arbitrary and correspond exactly to . Transforming back proves the description of all minimizers and the formula for the optimal residual.
Meanwhile,
The last sum has unique minimum zero. This proves minimum-norm existence and uniqueness, including the case . Equivalently, is orthogonal to the nullspace, so for every . An arbitrary shortest-looking solution obtained from a triangular routine must still satisfy this orthogonality; setting a free variable to zero is not sufficient.
Direct multiplication shows
These are symmetric orthogonal projections onto the column and row spaces. Therefore , , and . These four identities characterize the Moore–Penrose inverse. To see uniqueness, suppose another matrix satisfies them. Then is symmetric and idempotent, has range contained in , and fixes every because . Hence is the same orthogonal projection . Similarly, is symmetric and idempotent, with : one direction is immediate, and implies . Thus projects onto the row space. Since , every lies in that row space and satisfies . The already proved uniqueness of the row-space preimage yields for every , so . This also proves independence from a chosen singular-vector basis.
For completeness, the normal equations are necessary and sufficient even in the rank-deficient case. Expand the squared residual at . If the normal equations hold, the cross term is zero and the objective increases by . Conversely, if the cross term is nonzero in some direction, taking a sufficiently small displacement with the appropriate sign reduces the objective. The normal equations characterize the whole affine family; they do not select its shortest member.
Proof X-ray
Two uniqueness statements live in different spaces
The decisive move is the orthogonal change of variables , . It is chosen so that both objectives of the two-stage problem become separable at once: orthogonality of preserves the residual norm, orthogonality of preserves the coefficient norm, and couples each to a single . No rank or consistency hypothesis is used; the positive singular values are used only to solve for .
The two uniqueness claims then come from different coordinates. The fit is unique because the coordinates are forced, which is the statement that the orthogonal projection of onto the column space is unique. The coefficients are not unique, because do not enter the residual at all; they parametrize . Only the second objective, the coefficient norm, forces these to vanish, and it does so uniquely because their contribution is the sum of squares . Keeping the column space (where the fit lives) separate from the row space and nullspace (where the coefficients live) prevents a correct projection argument from being misused as a coefficient-uniqueness argument.
Truncation and the best rank approximation
Proof
(Truncation formulas and the rank- lower bound)
In singular-vector coordinates, is diagonal on the discarded directions. Its spectral norm is the largest discarded singular value. For any retained direction, the coefficient reproduces exactly; all other residual coordinates remain . This proves the truncation formulas and the coefficient bound. It also proves the constrained residual-minimization statement without asserting that the discarded directions were exactly zero in the original data.
There is a useful optimality certificate for the matrix approximation itself. Fix and let have rank at most . The map from the -dimensional space through has a nontrivial kernel. Choose a unit vector with . Then
Truncating after singular values attains this bound. Thus it is a best rank-at-most- spectral-norm approximation. This theorem concerns matrix approximation; it does not by itself say which is justified by the uncertainty in a particular measurement problem.
Rank revelation is a numerical task, not a rank definition
An exact SVD reveals exact rank by its positive singular values. A computed SVD has rounding error. If its result is justified by a backward relation with exact orthogonal factors and , then the reported singular values describe this nearby matrix. One has
Here is a short justification rather than an unexplained appeal to stability. The singular values satisfy
For the upper bound, take the span of . For the lower bound, every admissible intersects nontrivially by the dimension formula, and a unit vector in that intersection has image norm at least . Replacing by changes every image norm by at most . Apply the minimax formula in both directions to obtain the perturbation inequality. Consequently, a threshold within this error allowance of a singular value does not establish a robust rank decision. The existence of a gap and the size of data uncertainty both matter. A concrete SVD implementation requires its own justified backward-error budget; none is implemented here.
Column-pivoted QR is another practical rank-assessment route: at each step choose the remaining column with largest residual norm and triangularize it orthogonally. In an exact rank- factorization, one obtains
With and , all minimizers satisfy . Setting produces a basic solution. Put and . The actual minimum-norm member minimizes
and therefore solves , followed by . The coefficient matrix is positive definite because for . This derivation explains the missing minimum-norm step; it is not a recommendation to form these normal equations in a demanding implementation. Complete orthogonal decompositions provide another route to the same geometry.
In floating point, a small trailing QR block and acceptable conditioning of the leading block are evidence that must be quantified. A rule on diagonal magnitudes alone is not the SVD definition of rank. Ordinary greedy column pivoting is a useful heuristic, while stronger rank-revealing bounds or singular-value estimates require additional analysis. We have defined the procedure and its exact solution geometry, not proved a universal rank guarantee for a production pivoted-QR routine.
Worked examples
Worked example 15.1.6
(Duplicate columns, a nonzero residual, and every minimizer)
Let
Use , , and . The singular values are and . Thus
All minimizers are . Their common fitted vector is and their common residual is , of norm . Their squared coefficient norm is , with unique minimum at . The basic solution fits equally well but has larger norm . The irreducible residual and coefficient nonuniqueness are separate facts.
Worked example 15.1.7
(An underdetermined exact fit still needs a selection rule)
For and , the rows are independent and
The displayed formula is valid for this full-row-rank matrix; it is not the general definition for arbitrary rank. It gives . Every solution is , whose squared norm is . Thus the minimum is unique even though the exact system has infinitely many solutions. Selecting the third variable as zero gives and squared norm five, rather than two.
Worked example 15.1.8
(A threshold buys smaller coefficients by discarding a weak direction)
Take and . The exact rank is two. Its minimum-norm least-squares solution is , with residual norm . A change of in the second datum changes its corresponding coefficient by .
With , only the first singular direction is retained. Then and . The original-data residual is , with norm , and . A much smaller coefficient vector costs a slightly larger residual. Whether that cost is acceptable depends on the data uncertainty, not on an unexplained machine constant. The threshold changes the model's rank; the original exact matrix still has rank two.
Common mistakes
Counterexample mode
The pseudoinverse is not continuous through a rank change
For with , . Yet . The matrices approach in norm while their pseudoinverses do not. With , the exact minimum-norm solution jumps from to zero at rank collapse. A stable computation cannot remove this sensitivity in the original problem.
Even with fixed and , only an absolute right-hand-side sensitivity bound is immediate:
It follows by expanding in singular vectors, and equality is attained for a change along . Relative coefficient error additionally depends on , which can be zero or tiny. There is no finite universal relative bound obtained by ignoring this denominator. Perturbing and allowing rank changes requires further hypotheses.
Common mistake
(A triangular diagonal is not a singular-value list)
A triangular diagonal is also not a singular-value list. For , both diagonal entries are one, but and , so . This example warns against inspecting an arbitrary unpivoted diagonal as if it were an SVD. It is not presented as a counterexample to every quantified column-pivoted QR theorem.
Common mistake
(Setting free variables to zero does not give the shortest solution)
An elimination or triangular solve that sets the free coordinates to zero returns a basic solution. It is a least-squares solution, but generally not the minimum-norm one. In the duplicate-column example, the basic solution has norm , while has norm . The test is orthogonality to the nullspace: the inner product of with the null vector is , so it is not the shortest member.
Concept lensStructural
Rank, resolution, and the chosen coefficient metric
Exact rank counts nonzero singular directions of fixed data. Numerical rank records which directions a stated uncertainty and threshold can resolve. Minimum Euclidean norm chooses the shortest coefficients in the stated coordinates; rescaling the unknowns changes that metric and can change the selected solution. These are three explicit modeling decisions, rather than three names for one automatic answer.
Summary
SVD separates attainable fits from irreducible residuals and separates determined coefficient directions from the nullspace. The pseudoinverse selects the unique row-space, minimum-norm solution. Truncation has a precise approximation and constrained-fit meaning, but requires an explicit resolution decision. Exact rank, a computed rank estimate, and a stable implementation are related questions with different hypotheses.
Exercises
Quick check
(Let and . Find , every least-squares solution, the minimum-norm member, and the optimal residual. Verify normal orthogonality.)
Solution · Answer
Write . Then with , so . Thus and all minimizers are . The fitted vector is , giving and norm . Multiplication gives , and proves minimum norm within the affine family.
Quick check
(Let and . The basic solution is . Derive the minimum-norm solution using in the QR discussion. Then replace by , with , minimize instead, and show that the selected physical vector changes.)
Solution · Answer
Here , and , so . The equation gives and the other coordinate . For the changed metric, ; its shortest exact coefficient vector is , hence . Both physical vectors satisfy , but they minimize different norms. The second rule minimizes , not .
Quick check
(For , and the strict rule , find , the residual norm and the matrix-approximation error for , , and .)
Solution · Answer
For and , both positive directions are retained: , residual norm one, and approximation error zero. At , equality is discarded: , residual norm , and approximation error . At , no direction is retained: , residual norm , and approximation error three. The exact rank of remains two in every case.
Quick check
(Suppose a computed SVD has an established spectral backward-error budget and reports singular values , and . With threshold , which rank statements about the original matrix are certified by this information alone? Explain what a thresholded rank of two actually describes.)
Solution · Answer
The second original singular value lies in and the third in . Both intervals cross the threshold, so the original thresholded rank could be one, two or three. The first singular value is certainly above threshold; all three are certainly positive under these particular intervals, so the original exact rank is three. The reported thresholded rank two describes the nearby matrix represented by the computed factors under the stated strict cutoff. It does not certify the same cutoff decision for the original matrix when the error intervals overlap it.