An inconsistent system has no exact solution, but one can seek a vector whose image is closest to . This is a geometric question in the target space before it becomes a matrix equation. We work with finite-dimensional real or complex inner-product spaces, and use the adjoint defined by . The notation is the conjugate transpose in orthonormal coordinates.
Definition 3.6.1
(Least-squares solution, fitted vector and residual)
Let be linear and . A vector is a least-squares solution of if for every . For such , the vector is a fitted vector and is the residual. The least squared error is , and the least distance is its square root.
Why the residual is perpendicular
Since is a subspace of the finite-dimensional space , the orthogonal decomposition theorem gives a unique decomposition of into a part in the image and a part perpendicular to it. The next result shows that this decomposition solves the whole problem.
Theorem 3.6.2
(Normal equations)
Let be linear and , and write with and . For the following are equivalent:
- is a least-squares solution of ;
- ;
- ;
- .
Least-squares solutions exist, they all have the same fitted vector and the same residual , and they form the set for any one solution .
Proof
(Pythagoras, then the adjoint)
The decomposition is
Choose with . For any , the vectors and are orthogonal, because . Hence
Equality holds precisely when . Thus is a least-squares solution, and is one exactly when ; this is . Every least-squares solution then has fitted vector and residual . Moreover exactly when , so the solutions are , and uniqueness is equivalent to .
For : if , then is a decomposition of the required type, so uniqueness of the decomposition gives . The converse holds because .
For : for every ,
The left side vanishes for all exactly when . The right side vanishes for all exactly when , because a vector perpendicular to every vector of is zero. So the condition is
Proof X-ray
Where the Pythagorean step gets its power
The whole argument turns on one cross term. When is expanded, the term appears, and it is zero only because lies in while lies in its orthogonal complement. Membership of in the image is the single hypothesis consumed there; it is why the competitor is compared with the specific point and not with an arbitrary vector of . The inequality closes because with equality only for , which is positive-definiteness of the norm and also gives the characterization for free. Finite dimension is used once, silently, to know that the decomposition exists at all. In the example , below, is the floor: every other pays an additional on top of it.
The condition is a statement about the residual, and the normal equations are its restatement in the domain. They are necessary and sufficient for least squares, not merely a convenient way to find a candidate.
Quick check
(Suppose already has an exact solution. Which vectors are the least-squares solutions, and what is the residual?)
Compare with .
Solution · Answer
Now , so its decomposition is , that is and . The least-squares solutions are the with , exactly the exact solutions, and the least squared error is .
When may we invert the normal matrix?
Proposition 3.6.3
(Kernel of the normal operator)
For a linear map between finite-dimensional inner-product spaces, . In particular is invertible if and only if is injective. In matrix terms, is invertible if and only if the columns of are linearly independent.
Proof
(Norm identity for the normal operator)
For every , (or its conjugate under the opposite convention; the value is real). If then . Conversely, if then , so . Thus . An operator on a finite-dimensional space is invertible exactly when its kernel is zero, so is invertible exactly when is injective; for this says that only for , which is linear independence of the columns.
If the columns are dependent, the normal equations still have solutions by the orthogonal-decomposition proof, but one must solve them without writing .
Counterexample mode
The formula with the inverse needs independent columns
A tempting claim is that for every real matrix the least-squares solution is . Take and . Then has determinant , so no inverse exists. The normal equations reduce to the single equation , which has infinitely many solutions. Check two of them: and both give , and the residual is perpendicular to the column , as required. The formula is therefore not a statement about all matrices: it is valid exactly when the columns are linearly independent, and otherwise the solution is a whole coset .
Worked example 3.6.4
(A tall matrix with independent columns)
Take
Then and . Solving gives . The residual is
Its dot product with each column of is zero. Since the columns are independent, the solution vector is unique. The least squared error is ; the least distance is . These are different quantities.
Common mistake
(Reporting the squared error as the distance)
The normal equations minimize , and the number is the least squared error, not the distance from to . In the example above , while the distance is , not .
Worked example 3.6.5
(Fitting a line to three points)
Fit to the points , , . The unknown is , and
Then , of determinant , and . Hence
so the line is . The fitted vector is and the residual is . Check: against the column the dot product is , and against it is . The least squared error is .
Quick check
(Why does force ?)
Pair the vector with .
Solution · Answer
If , then , and a vector of norm zero is the zero vector. This is the step that shows .
Dependent columns and the minimum-norm choice
Theorem 3.6.6
(Minimum-norm least-squares solution)
Let be linear and . Among all least-squares solutions of there is exactly one of minimum norm, and it is the unique least-squares solution lying in .
Proof
(Splitting a solution along the kernel)
If , every minimizer has the form for . Decompose with and . Then , so is also a minimizer. Every minimizer is uniquely with , because , and orthogonality yields . Therefore is the unique least-squares solution of minimum norm; it is the only minimizer in , since with is not orthogonal to . If the statement is the uniqueness already proved. This second minimization takes place in the domain; the residual minimization takes place in the target.
Worked example 3.6.7
(A map with a nonzero kernel)
For and , the normal equation reduces to . All solutions give the same fitted vector and residual , but only is perpendicular to and hence has minimum norm. Indeed has squared norm , which is smallest at .
Common mistake
(Using the transpose instead of the conjugate transpose)
For complex matrices the normal equations read , not . Let and . Then and , so , with residual perpendicular to . With the plain transpose, , and the equation has no solution at all.
Exercises
Exercise 3.6.8
(Find the least-squares solution of for the data below, and verify the residual is perpendicular to both columns.)
Core
Hint(1)
Form first; the columns are independent, so it is invertible.
Solution(3)
- 1
Write the normal equations
Key step
Because: The least-squares solutions are exactly the solutions of .
- 2
Solve them
Because: The determinant is , so the inverse exists.
- 3
Check the residual
Here , so . Its dot product with the first column is , and with the second column it is . The least-squares solution is , and the least squared error is .
Quick check
(Find the least-squares solution of for and , and the least squared error.)
Here is a single column.
Solution · Answer
and , so , the mean of the entries of . The residual is , which sums to as perpendicularity to the column requires, and .