L12

Application of Least Squares Solution

  • Example: Find the "least squares linear fit" for the points (-1,2), (0,4), (1,1), and (2,7).


    • Given points (x_i, y_i), the least squares line is given by the equation:[ y = c_0 + c_1 x ]

    • Objective: Minimize [ n = \sum_{i=1}^{n} (y_i - (c_0 + c_1 x_i))^2 ]

Set Up the System

  • Set up the equation system as follows:

    • Coefficients [ c_0, c_1 ] are parameters to find.


    • Formulate:[ \begin{bmatrix} 1 & x_1 \ 1 & x_2 \ 1 & x_3 \ 1 & x_4 \ \end{bmatrix} \begin{bmatrix} c_0 \ c_1 \end{bmatrix} = \begin{bmatrix} y_1 \ y_2 \ y_3 \ y_4 \end{bmatrix} ]


    • Rearranged into:[ Ax = b ]

Least Squares Solution

  • Formula:

    • The least squares solution is found using: [ c = (A^TA)^{-1}A^Tb ]

    • Parameters calculated for the given example:

      • When calculated: [ c = \begin{pmatrix} -0.9 \ 2.2 \end{pmatrix} ]

    • The least squares fit line is: [ y = -0.9x + 2.2 ]

Invertibility of ATA

  • Proposition:

    • If [ A ] is a matrix, then [ A^TA ] is invertible if and only if rank(A) = n, meaning the columns of A are independent.

  • Proof:

    1. If [ x \in N(A) ], then [ A^TAx = 0 \Rightarrow x \in N(A^TA) ].

    2. Conversely, if [ x \in N(A^TA) ], then it implies that [ Ax = 0 ].

    3. Thus, [ N(ATA) = N(A) ] follows.

Example 2: Quadratic Fit

  • Find a "least squares" quadratic fit for points (-1,2), (0,4), (2,7).

    • Set the equations to minimize:

      • [ \begin{pmatrix} 1 & -1 & 1 \ 1 & 0 & 0 \ 1 & 2 & 4 \ \end{pmatrix} \begin{pmatrix} c_0 \ c_1 \ c_2 \end{pmatrix} = \begin{pmatrix} 2 \ 4 \ 7 \end{pmatrix} ]

  • Conclusion: The columns of A are independent, leading to calculations yielding:

    • Ca = [ (A^TA)^{-1}A^Tb = egin{pmatrix} -0.75 \ -0.15 \ 2.95 \end{pmatrix} ]

    • Least Squares Quadratic Fit: [ y = -0.75x^2 - 0.15x + 2.95 ]

Projection Matrices

  • Definition: A projection matrix [ P ] projects vector [ b \in \mathbb{R}^m ] onto a subspace of [ \mathbb{R}^n ].

  • For least squares solution:

    • [ P = A(A^TA)^{-1}A^T ] which minimizes [ ||b - p|| ] over all [ p \in C_A ].

  • Properties of Projection Matrices:

    1. Symmetric: [ P^T = P ]

    2. Idempotent: [ P^2 = P ]

Special Cases

  • If [ m = n ] with rank(A) = n, then [ P = I ], where [ b ] is in the range and [ Pb = b ].

  • Exact Solution:

    • When [ A ] is invertible, the exact solution is given by: [ E = (A^TA)^{-1}A^Tb = A^T(A^TA)^{-1}b = A^T ]