Notes on Least Squares Solution

Introduction to Matrix Equation

• Consider the equation: ( Ax = b )
  • ( A ) is an ( n \times k ) matrix
  • ( x ) is in ( R^k ) (k-dimensional vector)
  • ( b ) is in ( R^n ) (n-dimensional vector)

No Solution Situation

• If ( Ax = b ) has no solution:
  • No set of weights on columns of ( A ) can equal ( b )
  • This implies: ( b ) is not in the column space of ( A )
  • Linear combinations of column vectors of ( A ) cannot equal ( b )

Column Space Visualization

• Visualizing the column space of ( A ):
  • Assume it forms a plane in ( R^n )
  • If ( b ) does not lie in this plane, it indicates no solution.

Finding a "Closest" Solution

• Although there is no exact solution, we can find an approximate solution:
  • Goal: Find ( x^* ) such that ( Ax^* ) is as close to ( b ) as possible.
  • Define "closeness" in terms of minimizing the length of the vector ( b - Ax^* ).

Minimization of Length

• To minimize:
  • ( ||b - Ax^*||^2 = (b_1 - v_1)^2 + (b_2 - v_2)^2 + ... + (b_n - v_n)^2 )

Least Squares Solution Definition

• The resulting solution is termed the least squares solution
  • When ( b ) is not in the column space of ( A ), we seek an ( x^* ) such that:
  • ( Ax^* ) equals the projection of ( b ) onto the column space of ( A )

Projection and Orthogonality

• The difference vector ( Ax^* - b ) is orthogonal to the column space of ( A ).
• It belongs to the orthogonal complement of the column space, which is the null space of ( A^T ).

Deriving the Least Squares Solution

• From previous findings:
  • ( A(x^*) - b ) is in the null space of ( A^T )
• Thus, when multiplied by ( A^T ):
  • ( A^T(Ax^* - b) = 0 )
• Rearranging gives:
  • ( A^T A x^* = A^T b )

Conclusion

• The equation ( A^T A x^* = A^T b ) helps find the least squares solution even if the direct solution to ( Ax = b ) doesn't exist.
• This method minimizes the error, resulting in the best approximation to the solution.
• The concept is foundational in many applications, particularly in data fitting and regression analysis.