Why is the solution to the normal equations ATAx* = ATb considered the least-squares solution?
The solution to the normal equations is considered the least-squares solution because it satisfies the necessary and sufficient condition for minimizing the residual norm ∥b−Ax∥. The derivation shows that minimizing this norm is equivalent to requiring the residual Ax∗−b to be orthogonal to the column space C(A). This orthogonality condition translates algebraically to AT(Ax∗−b)=0, which is exactly the normal equation. Thus, any x∗ solving the normal equations yields the projection of b onto C(A), providing the best approximate solution.
Conditions
The original system Ax=b may be inconsistent
ATAx∗=ATb has a solution
Reasoning, step by step
Recall that the least-squares goal is to make Ax∗ the closest point in C(A) to b.
Identify that closeness implies the residual Ax∗−b is orthogonal to C(A).
Translate orthogonality to the condition Ax∗−b∈N(AT).
Convert null-space membership to the equation AT(Ax∗−b)=0.
Expand to ATAx∗=ATb.
Conclude that solving this equation finds the specific x∗ that achieves the minimum distance.
Example
The speaker states, 'This right here will always have a solution, and this right here is our least squares solution,' referring to the boxed normal equations.
Common misconceptions
Believing that the normal equations provide an exact solution to the original inconsistent system Ax=b.
Thinking that the normal equations are only an approximation method rather than the exact characterization of the minimizer.
The least-squares fit Ax∗ is identified with the orthogonal projection of b onto C(A) because the goal of least squares is to find the vector in the subspace C(A) that is closest to b. A fundamental geometric property of subspaces states that the unique closest point in a subspace to an external vector is its orthogonal projection.
Conditions: C(A) is a subspace of Rn; b∈Rn; Distance is measured by the Euclidean norm
Every product Ax is a member of the column space C(A) because matrix-vector multiplication is defined as a linear combination of the columns of A. Specifically, if A=[a1a2⋯ak] and x=[x1,…,xk]T, then Ax=x1a1+⋯+xkak.
Conditions: A is an n×k matrix; x∈Rk; C(A) is the span of the columns of A
The equation Ax=b has no solution because solving it is equivalent to finding weights x1,…,xk such that x1a1+⋯+xkak=b. The column space C(A) is defined as the set of all possible linear combinations of the columns of A.
Conditions: A is an n×k matrix; x∈Rk and b∈Rn; C(A) denotes the column space of A
Minimizing the Euclidean norm ∥b−Ax∗∥ is equivalent to minimizing its square, ∥b−Ax∗∥2. The squared norm expands algebraically into the sum of the squared differences of corresponding components: (b1−v1)2+(b2−v2)2+⋯+(bn−vn)2, where v=Ax∗.
Conditions: b,v∈Rn; Standard Euclidean norm is used; v=Ax∗
When Ax=b has no exact solution, the least-squares solution x∗ is defined as the vector that minimizes the Euclidean norm of the residual, ∥b−Ax∗∥. Geometrically, this means choosing x∗ such that Ax∗ is the closest possible vector to b within the column space C(A).
Conditions: The system Ax=b is inconsistent (no exact solution exists); Distance is measured by the standard Euclidean norm