Least-squares problem

Least-squares problem

Lessons

In linear algebra, we have dealt with questions in which Ax=bAx=b does not have a solution. When a solution does not exist, the best thing we can do is to approximate xx. In this section, we will learn how to find a xx such that it makes AxAx as close as possible to bb.

If AA is an m×nm \times n matrix and bb is a vector in Rn\Bbb{R}^n, then a least-squares solution of Ax=bAx=b is a x^\hat{x} in Rn\Bbb{R}^n where
bAx^bAx\lVert b-A \hat{x}\rVert \leq \lVert b-Ax\rVert

For all xx in Rn\Bbb{R}^n.

The smaller the distance, the smaller the error. Thus, the better the approximation. So the smallest distance gives the best approximation for xx. So we call the best approximation for xx to be x^\hat{x}.

The Least-Squares Solution

The set of least-square solutions of Ax=bAx=b matches with the non-empty set of solutions of the matrix equation ATAx^=ATbA^T A \hat{x}=A^T b.

In other words,
ATAx^=ATbA^T A \hat{x}=A^T b
x^=(ATA)1ATb \hat{x} = (A^TA)^{-1}A^Tb

Where xx is the least square solutions of Ax=bAx=b.

Keep in mind that xx is not always a unique solution. However, it is unique if one of the conditions hold:
1. The equation Ax=bAx=b has unique least-squares solution for each b in Rm\Bbb{R}^m.
2. The columns of AA are linearly independent.
3. The matrix ATAA^T A is invertible.

The Least-Squares Error
To find the least-squares error of the least-squares solution of Ax=bAx=b, we compute

bAx^\lVert b - A \hat{x} \rVert

Alternative Calculations to Least-Squares Solutions
Let AA be a m×nm \times n matrix where a1,,ana_1,\cdots,a_n are the columns of AA. If Col(A)=Col(A)={a1,,ana_1,\cdots,a_n } form an orthogonal set, then we can find the least-squares solutions using the equation
Ax^=b^A \hat{x}=\hat{b}

where b^=projCol(A)b.\hat{b}=proj_{Col(A)}b.

Let AA be a m×nm \times n matrix with linearly independent columns, and let A=QRA=QR be the QRQR factorization of AA . Then for each bb in Rm\Bbb{R}^m, the equation Ax=bAx=b has a unique least-squares solution where
x^=R1QTb\hat{x}=R^{-1} Q^T b
Rx^=QTb R\hat{x}=Q^T b
  • Introduction
    Least Squares Problem Overview:
    a)
    The Least Squares Solution
    Ax=bAx=b give no solution
    • Approximate closest solution x^\hat{x}
    • The least Squares Solution x^=(ATA)1ATb\hat{x} =(A^T A)^{-1} A^T b
    • Not always a unique solution

    b)
    The Least Squares Error
    • Finding the error of the solution x^\hat{x}
    • Use the formula bAx^\lVert b-A\hat{x}\rVert

    c)
    Alternative Calculation to Least-Squares Solutions
    • Orthogonal columns of AA Ax^=b^ A\hat{x} =\hat{b}
    • QR factorization A=QRA=QR Rx^=QTb R\hat{x} =Q^T b


  • 1.
    Finding the Least Squares Solutions with ATAx^=ATbA^T A\hat{x} =A^T b
    Find a least-squares solution of Ax=bAx=b if
    Find a least-squares solution

  • 2.
    Describe all least-squares solutions of equation Ax=bAx=b if
    Describe all least-squares solutions of equation Ax=b

  • 3.
    Finding the Least Squares Error
    You are given that the least-squares solution of Ax=bAx=b is least-squares solution of Ax=b. Compute the least-square error if
    Find the Least Squares Error

  • 4.
    Finding the Least Squares Solutions with Alternative Ways
    Find the orthogonal projections of bb onto the columns of AA and find a least-squares solution of Ax=bAx=b.
    Finding the Least Squares Solutions with Alternative Ways

  • 5.
    Use the factorization A=QRA=QR to find the least-squares solution of Ax=bAx=b
    Use the factorization A=QR to find the least-squares solution of Ax=b