Fitting when equations disagree
A system can have more equations than unknowns and no exact solution. For example, a straight line need not pass through every measured point. Rather than declaring the inconsistent system unsolvable, least squares asks for the vector whose predicted data are closest to the observed data in a specified norm. The choice of norm is part of the problem: minimizing the sum of squared residuals differs from minimizing the largest residual.
Throughout, , , and . The Euclidean least-squares problem is
The residual convention here is . A small residual means that the fitted vector is close to the supplied ; it does not automatically mean that the coefficients are insensitive to data error. Repeated or nearly dependent columns of can make many coefficient vectors give the same or nearly the same fitted values.
Projection and the normal equations
Theorem 4.1.1
(Least-squares minimizers and the normal equations)
A vector minimizes if and only if
A minimizer exists for every . It is unique exactly when has full column rank, that is, .
Proof
(Projection argument and uniqueness)
The column space is a finite-dimensional subspace of and is closed. Let be the orthogonal projection of onto it, and choose with . Then is orthogonal to every column of , so . Conversely, if , then is orthogonal to the column space. For every ,
because the cross term vanishes. Thus is a minimizer. Any other minimizer has the form ; equality of its objective with the projection minimum forces , so it has the same residual and satisfies the normal equations. If , the second term is positive for nonzero , giving uniqueness. If the kernel contains nonzero , then gives the same fitted vector and is another minimizer.
Proof X-ray
Where each hypothesis enters the projection proof
Three separate facts carry the proof, and each is used once. Existence needs only that is a finite-dimensional subspace, so the projection exists; no rank condition is involved. The decisive move is the Pythagorean identity: the cross term in is , and it vanishes for every at once precisely because . That is the only place the normal equations are used, and it turns "minimizer" into "perpendicular residual" for all competitors simultaneously. Full column rank enters only in the last step, to make for . Dropping it leaves the first two steps intact, so the fitted vector and residual stay unique, but the coefficients do not.
The fitted vector is unique even if is not: it is the unique projection of onto the column space. The normal equations are always consistent, but is invertible only under full column rank. Indeed, implies . Conversely, if , then , so . Hence .
Counterexample mode
Unique fit, nonunique coefficients
A tempting claim is that for every and the least-squares solution is . Take and . Then has determinant zero, so the formula does not exist. Every with gives the same fitted vector and the same residual , and , so each such vector is a minimizer and there is no unique . The repaired statement is the theorem above: the formula holds exactly when has full column rank, and without that hypothesis only the fitted vector is unique.
QR gives the same projection without forming normal equations
Suppose now that has full column rank, the case in which the minimizer is unique.
Definition 4.1.2
(Thin QR factorization)
Let have full column rank. A thin QR factorization of is a factorization in which has orthonormal columns () and is invertible and upper triangular.
Applying Gram–Schmidt to the independent columns gives such a factorization: at step the component of column orthogonal to the preceding span is nonzero, so it can be normalized to form . Its coefficients in the preceding orthonormal vectors and the new vector form column of . The diagonal entries can be chosen positive.
Proposition 4.1.3
(Least squares by QR)
Let be a thin QR factorization of a full-column-rank matrix . Then has a unique minimizer , determined by the triangular system
and the minimum value is .
Proof
(Splitting the residual along and across the columns of Q)
For any write
The first term lies in the column space of . The second is orthogonal to that space, because . By Pythagoras, and because when ,
The second term does not depend on . The first is zero exactly when , and since is invertible this triangular system has exactly one solution.
There is no need to form as a dense matrix when a practical factorization can apply the orthogonal transformations directly. Householder QR uses reflections; modified Gram–Schmidt is another construction, but the exact-arithmetic derivation alone does not guarantee that every implementation has the same floating-point behavior.
Worked example 4.1.4
(Fitting a line through three points)
Fit to data in the least-squares sense. With
choose and . Then
Back substitution gives and . The residual is , whose entries sum to zero and whose inner product with is zero. These are exactly the two normal equations. The minimum squared residual is . A zero residual was not required: the residual must be perpendicular to the fitted space, not necessarily zero.
Worked example 4.1.5
(A rank-deficient fit with a nonzero residual)
Let and . The column space is the line spanned by , and is not on it. The projection is , so every minimizer satisfies . The normal equations agree: and , so both rows read , a single equation. The residual is ; as a check, , and . Nonuniqueness persists even though the residual is nonzero: and are both minimizers, and the second has the smaller Euclidean length.
Conditioning and loss of rank information
Definition 4.1.6
(Two-norm condition number)
Let have full column rank with largest and smallest singular values . Its two-norm condition number is .
Singular values measure the largest and smallest stretching of unit vectors.
Proposition 4.1.7
(Squaring of the condition number by the Gram matrix)
For a full-column-rank matrix ,
Proof
(Eigenvalues of the Gram matrix)
The singular values of are the square roots of the eigenvalues of . For full column rank the matrix is symmetric positive definite, so its singular values are its eigenvalues, namely . Hence .
Thus forming the normal-equations matrix squares the two-norm condition number. This identity is about the Gram matrix and is not, by itself, a complete condition number for the least-squares problem. In particular, sensitivity to perturbations of can include terms involving and the residual. The identity concerns exact matrices; floating-point formation can additionally round its entries. QR uses orthogonal transformations, which preserve Euclidean lengths in exact arithmetic, and avoids explicitly forming . It cannot remove sensitivity inherent in the original least-squares problem.
Concept lensGeometric
Level sets are ellipsoids whose elongation is the condition number
By the identity , the level sets of the objective are ellipsoids centered at . In the right singular vectors of their semi-axes are proportional to , so the longest axis exceeds the shortest by the factor . The Hessian has eigenvalues , with ratio .
Worked example 4.1.8
(Normal equations lose a nearly dependent pair)
For example, let
Its columns are independent, but nearly parallel for small , and
In separately rounded binary64 arithmetic with , the sum rounds to 1. The formed matrix is then , which is singular, even though the original columns are independent. This specific calculation illustrates loss of information when forming products; it does not assert that every QR algorithm can recover arbitrary information below the precision of its inputs.
Worked example 4.1.9
(Condition numbers of the nearly dependent pair)
For above, the eigenvalues of are the roots of , by trace and determinant. Both roots are positive, with sum and product . The larger root exceeds half the sum, so and ; therefore , while . Because ,
For this gives , far above , the reciprocal of the binary64 unit roundoff, while itself is only about . This is why the previous example loses the matrix entirely after one rounding.
Common mistake
(A small residual does not certify the coefficients)
It is tempting to accept once is small. For the coefficient vectors and give fitted vectors and , which differ by , although the coefficient vectors differ by . A fit that is good to within cannot tell them apart. Judge the coefficients through and the sensitivity bound below, not through the residual alone.
Exact rank is an algebraic property. In finite precision, numerical rank is a tolerance-dependent judgment about which singular values are distinguishable from zero at the chosen scale and accuracy. For example, the full-rank matrix is within in spectral norm of the rank-one matrix . If uncertainties of that size are meaningful in the data, treating the second direction as resolved requires justification. Rescaling variables, data uncertainty and the goal of the computation all affect a sensible tolerance; a small entry alone is not a universal rank test. A singular-value decomposition or rank-revealing factorization can help expose weak directions, but the threshold is still a modeling choice.
Definition 4.1.10
(Numerical rank)
For a tolerance , the numerical rank of with respect to is the number of singular values of that exceed . The tolerance is not a property of the matrix: it must be chosen from the scale of the variables and the size of the uncertainty in the data.
Common mistake
(A tiny singular value is not automatically zero)
Declaring the rank of to be one because looks small ignores units. Multiplying the second variable by , that is, passing to , gives the identity matrix, whose singular values are both . The number has no meaning until the units and the uncertainty of the data are fixed.
Sensitivity to the data
Theorem 4.1.11
(Sensitivity of the minimizer to the data)
Let have full column rank with extreme singular values . Let minimize and let minimize . Then . If also and , and , then
Proof
(Applying the pseudoinverse and bounding the denominator)
By the normal equations the minimizer is unique and equals , where . This formula defines the mathematical map; a program need not compute it this way. Since is linear, . If is a thin singular value decomposition, then , whose largest singular value is . Therefore
For the relative form, gives . Dividing the first bound by this lower bound yields the second.
The angle factor matters when the fitted component is small compared with the data. If , relative coefficient error is undefined and the absolute estimate remains meaningful. This calculation perturbs with fixed; changing is a separate perturbation problem and cannot be inferred from this bound alone.
Practice with solutions
Quick check
(Find the least-squares constant fitting the data , and the residual. Why is the residual orthogonal to the column of ones?)
Project the data onto the column of ones.
Solution · Answer
The column of ones has squared norm three, so projection gives and . Its entries sum to zero, so it is perpendicular to the column.
Quick check
(Give a thin QR factorization, the minimizer and the minimum residual norm for the matrix and vector below.)
Solution · Answer
Take and . Solving gives ; the residual has norm five.
Quick check
(Describe all least-squares minimizers for the matrix and vector below. Is the fitted vector unique?)
Solution · Answer
The data already lie in the column space: every pair with has zero residual and is a minimizer. The coefficients are not unique, but the fitted vector is always .
Quick check
(A full-column-rank matrix has singular values and . Compute and .)
Singular values of are squares of those of .
Solution · Answer
and . Forming normal equations therefore changes the sensitivity scale even before rounding errors in forming the product are considered.