Least Squares

Given

Given many data points, construct a matrix equation in the form of a linear equation (this matrix equation will be overdetermined). The matrix equation below is $A\vec{x}=\vec{b}$ This equation is linear but it doesn’t have to be, just adjust accordingly to represent the equations as a matrix equation.

$$\left[\begin{array}{cc}1& x_0\\ 1& x_1\\ 1& x_2\\ 1& x_3\\ 1& x_4\\ 1& x_5\end{array}\right]\left[\begin{array}{c}b\\ m\end{array}\right]=\left[\begin{array}{c}{y}_0\\ y_1\\ y_2\\ y_3\\ y_4\\ y_5\end{array}\right]$$

Goal

Using Best Approximation, find a vector in subspace $ColA$ closest to $\vec{b}$

$ColA$ is a subspace of ${\mathbb{R}}^n$, $\vec{b}\in {\mathbb{R}}^n$ $\forall \vec{x},\vec{a}=A\vec{x}$, i.e. $\vec{a}\in ColA$ $\hat{b}=A\hat{x}=pro{j}_{ColA}\vec{b}$ Note: Can only use Orthogonal Decomposition for $\hat{b}$ when the columns of A form an orthogonal basis, by definition $⟹$

$$\begin{array}{c}\forall \vec{a}\in ColA,\vec{a}\ne \hat{b}||\vec{b}-\hat{b}||<||\vec{b}-\vec{a}||\\ \forall A\vec{x}\in ColA,A\vec{x}\ne A\hat{x}||\vec{b}-A\hat{x}||<||\vec{b}-A\vec{x}||\end{array}$$

In other words, $\hat{b}=A\hat{x}=pro{j}_{cola}\vec{b}$ is closest vector in $ColA$ to $\vec{b}$ Note: $\hat{x}$ is a unique vector, a special $\vec{x}$ that minimizes the above equation. Note: If the columns of $A$ are orthogonal, then you can just use the scalar projection of $\vec{b}$ onto each column of $A$.

Normal Equations

The least squares solutions to $A\vec{x}=\vec{b}$ corresponds to the solution to

$$A^{T}A\vec{x}=A^T\vec{b}$$

• Turns the $A\vec{x}=\vec{b}$ equation from above and transforms it into a square matrix equation

Derivation

• $(ColA{)}^{\perp }=Null(A^T)$
• $\hat{x}$ is the Least Squares Solution to $A\vec{x}=\vec{b}$ $⟺b-A\hat{x}\perp ColA$
• $\vec{b}-A\hat{x}\perp ColA⟹\vec{b}-A\hat{x}\in (ColA{)}^{\perp }$
• $\vec{b}-A\hat{x}\in (ColA{)}^{\perp }⟹\vec{b}-A\hat{x}\in Nul{A}^T$
• $\vec{b}-A\hat{x}\in Nul{A}^T⟺A^T(\vec{b}-A\hat{x})=0$
• $A^T(b-A\hat{x})=0$
• $A^{T}b-A^{T}A\hat{x}=0$
• $A^{T}A\hat{x}=A^T\vec{b}$

Normal Equation Usage

• Use when non-square matrix
  • Over/Under determined
• Regression

Theorem (Unique Solutions for Least Squares)

If A is m x n

• Ax = b has a unique least squares solution for each b in Rm
• Cols of A are linearly independent
• The matrix A^T A is invertible If the above hold, the unique least square solution is

$$\hat{x}=(A^{T}A{)}^{-1}{A}^T\vec{b}$$

If the above conditions are not true, there may be infinitely many solutions, or some other nonunique amount of solutions, in which case you should consider $[A^{T}A{A}^T\vec{b}]$ instead.

Note: $A^{T}A$ plays the role of the “length squared” of the matrix A

Theorem (Least Squares and QR)

$$\begin{array}{c}A\in {\mathbb{R}}^{m\times n}=QR\\ ⟹\\ \text{Least Squares Solution }\hat{x}=R^{-1}{Q}^T\vec{b}\end{array}$$

Examples

$$\begin{array}{c}A=\left[\begin{array}{cc}4& 0\\ 0& 2\\ 1& 1\end{array}\right],\vec{b}=\left[\begin{array}{c}2\\ 0\\ 11\end{array}\right]\\ \\ A^{T}A=\left[\begin{array}{cc}17& 1\\ 1& 8\end{array}\right]\\ A^T\vec{b}=\left[\begin{array}{c}19\\ 11\end{array}\right]\\ \text{Now setup the Normal Equations:}\\ A^{T}A\vec{x}=A^T\vec{b}\\ \left[\begin{array}{cc}17& 1\\ 1& 8\end{array}\right]\vec{x}=\left[\begin{array}{c}19\\ 11\end{array}\right]\\ \vec{x}={\left[\begin{array}{cc}17& 1\\ 1& 8\end{array}\right]}^{-1}\left[\begin{array}{c}19\\ 11\end{array}\right]\\ \hat{x}=\left[\begin{array}{c}1\\ 2\end{array}\right]\end{array}$$

Hampton Explanation for Least Squares

Let $A\in {\mathbb{R}}^{m\times n}$. $\hat{x}$ is the unique, minimizing solution to the equation $A\vec{x}=\vec{b}$ such that

$$\forall \vec{x}\in {\mathbb{R}}^n||\vec{b}-A\hat{x}||\le ||\vec{b}-A\vec{x}||$$

• Essentially, minimize $\vec{b}-A\hat{x}$
  • $||\vec{b}-\hat{b}||$ is the minimal distance between the different solutions
• $\forall x\in {\mathbb{R}}^n,A\vec{x}\in ColA,\vec{b}{=}^{?}ColA$
• Goal: Find $\hat{x}$ s.t. $A\hat{x}\in ColA$ is closest to $\vec{b}$
• $\hat{x}$ in this context just denotes the special/unique $x$ that minimizes the distances between $\vec{b}$ and $A\hat{x}$ b is closer to Axhat than to Ax for all other x in Col A
• If b in Col A, then xhat is…
• Seek $\hat{x}$ so that $A\hat{x}$ is as close to $\vec{b}$ as possible, i.e. $\hat{x}$ should solve Axhat = bhat
  • $\hat{b}=A\hat{x}=pro{j}_{Col(A)}\vec{b}$