Least Square Problems

Given $\mathit{A}\in {\mathbb{R}}^{m\times n},m⩾n;\mathit{b}\in {\mathbb{R}}^m$, the Least Square problem is defined as: Find ${\mathit{x}}^{\ast }\in {\mathbb{R}}^n$, such that:

$${\mathit{x}}^{\ast }=\arg \underset{\mathit{x}}{min}{\Vert \mathit{b}-\mathit{A}\mathit{x}\Vert }_2$$

where $\mathit{r}=\mathit{b}-\mathit{A}\mathit{x}$ is called residual. Residual $\mathit{r}\ne \mathbf{0}$.

We will introduce three different methods to solve the Least Square problem.

Normal Equation

Traditional Method

We solve ${\mathit{A}}^{\ast }\mathit{A}\mathit{x}={\mathit{A}}^{\ast }\mathit{b}$, where ${\mathit{A}}^{\ast }\mathit{A}\in {\mathbb{R}}^{n\times n}$. If $\mathit{A}$ is full rank, then ${\mathit{A}}^{\ast }\mathit{A}$ is invertible.

The Least Square solution is:

$${\mathit{x}}^{\ast }={\left({\mathit{A}}^{\ast }\mathit{A}\right)}^{-1}{\mathit{A}}^{\ast }\mathit{b}$$

Question: How about $\mathit{A}$ is not full rank?

Comment: This method is not recommended is $\kappa \left(\mathit{A}\right)$ is large.

Note: $\kappa \left({\mathit{A}}^{\ast }\mathit{A}\right)={\left(\kappa \left(\mathit{A}\right)\right)}^2$

Usually in practice, the number of matrix rows are way larger than that of columns.

Two Recommended Methods

QR Factorization

$$\mathit{A}=\mathit{Q}\mathit{R}⟺{\mathit{Q}}^{\ast }\mathit{A}=\mathit{R}$$

$${\Vert \mathit{A}\mathit{x}-\mathit{b}\Vert }_2={\Vert {\mathit{Q}}^{\ast }(\mathit{A}\mathit{x}-\mathit{b})\Vert }_2$$

$$={\Vert {\mathit{Q}}^{\ast }\mathit{A}\mathit{x}-{\mathit{Q}}^{\ast }\mathit{b}\Vert }_2={\Vert \mathit{R}\mathit{x}-{\mathit{Q}}^{\ast }\mathit{b}\Vert }_2$$

Let $\mathit{c}={\mathit{Q}}^{\ast }\mathit{b}$, then:

$${\mathit{x}}^{\ast }={\mathit{R}}^{-1}\mathit{c}={\mathit{R}}^{-1}{\mathit{Q}}^{\ast }\mathit{b}$$

SVD Method (Recommended)

Assume $\mathit{A}=\mathit{U}\mathbf{\Sigma }{\mathit{V}}^{\ast }$ as full SVD. We can get:

$$\mathit{A}=\mathit{U}\mathbf{\Sigma }{\mathit{V}}^{\ast }\iff {\mathit{U}}^{\ast }\mathit{A}\mathit{V}=\mathbf{\Sigma };$$

$${\Vert \mathit{A}\mathit{x}-\mathit{b}\Vert }_2={\Vert {\mathit{U}}^{\ast }\mathit{A}\mathit{V}{\mathit{V}}^{\ast }\mathit{x}-{\mathit{U}}^{\ast }\mathit{b}\Vert }_2={\Vert \mathbf{\Sigma }{\mathit{V}}^{\ast }\mathit{x}-{\mathit{U}}^{\ast }\mathit{b}\Vert }_2$$

Define ${\mathit{V}}^{\ast }\mathit{x}=\mathit{y},\mathit{w}={\mathit{U}}^{\ast }\mathit{b}$, then:

$${\Vert \mathit{A}\mathit{x}-\mathit{b}\Vert }_2={\Vert \mathbf{\Sigma }\mathit{y}-\mathit{w}\Vert }_2;$$

$$\arg \underset{\mathit{y}}{min}{\Vert \mathbf{\Sigma }\mathit{y}-\mathit{w}\Vert }_2$$

$$⟹{\mathit{y}}^{\ast }={\mathbf{\Sigma }}^{-1}\mathit{w}={\mathbf{\Sigma }}^{-1}{\mathit{U}}^{\ast }\mathit{b},$$

$${\mathit{x}}^{\ast }=\mathit{V}{\mathit{y}}^{\ast }=\mathit{V}{\mathbf{\Sigma }}^{-1}{\mathit{U}}^{\ast }\mathit{b}$$

We get the formula:

$${\mathit{x}}^{\ast }=\mathit{V}{\mathbf{\Sigma }}^{-1}{\mathit{U}}^{\ast }\mathit{b}$$

However, ${\mathbf{\Sigma }}^{-1}$ may not exist! Assume:

$$\mathbf{\Sigma }=\left[\begin{array}{cccccc}{\sigma }_1& & & & & \\ & \ddots & & & & \\ & & {\sigma }_r& & & \\ & & & 0& & \\ & & & & \ddots & \\ & & & & & 0\end{array}\right],{\sigma }_1⩾{\sigma }_2⩾\cdots ⩾{\sigma }_r>{\sigma }_{r+1}=\cdots ={\sigma }_m=0$$

The pseudo inverse ${\mathbf{\Sigma }}^{-1}$ is defined as:

$${\mathbf{\Sigma }}^{-1}=\left[\begin{array}{cccccc}\frac{1}{{\sigma }_1}& & & & & \\ & \ddots & & & & \\ & & \frac{1}{{\sigma }_r}& & & \\ & & & 0& & \\ & & & & \ddots & \\ & & & & & 0\end{array}\right]$$

Then ${\mathit{x}}^{\ast }=\mathit{V}{\mathbf{\Sigma }}^{-1}{\mathit{U}}^{\ast }\mathit{b}$ can be applied to the reduced SVD.

We can rewrite another formula of the result:

$${\mathit{x}}^{\ast }=\sum _{i=1}^r\frac{{{\mathit{u}}_i}^T\mathit{b}}{{\sigma }_i}{\mathit{v}}_i$$

where ${\mathit{u}}_i,{\mathit{v}}_i$ are columns of $\mathit{U},\mathit{V}$ respectively.

Comments: If ${\sigma }_i$ is small, the error is enlarged by ${\sigma }_i$.

We can compute the approximate value ("the best approximation of ${\mathit{x}}^{\ast }$ in ${\mathbb{R}}^k$ "):

$${\mathit{y}}^{\ast }=\sum _{i=1}^k\frac{{{\mathit{u}}_i}^T\mathit{b}}{{\sigma }_i}{\mathit{v}}_i,k<r$$

This is the idea behind Principal Component Analysis (where to cut off?).