Least-squares problem - Orthogonality and Least Squares

Do better in math today
Get Started Now

Least-squares problem


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
  • Intro Lesson
    Least Squares Problem Overview:
Teacher pug

Least-squares problem

Don't just watch, practice makes perfect.

We have over 70 practice questions in Linear Algebra for you to master.