$$

$$

Least squares problem

Problem

Let

$$A=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\\ 1& 4\end{array}\right]\text{ and }\mathbf{b}=\left[\begin{array}{c}1\\ 1\\ 2\\ 2\end{array}\right].$$

Find

$\mathbf{x}\in {\mathbb{R}}^2$ such that

$\Vert A\mathbf{x}-\mathbf{b}\Vert$ is minimized.

Thought

Givne any

$m\times n$ matrix

$A$, we know

$$\mathrm{Col}(A)=\{A\mathbf{x}:\mathbf{x}\in {\mathbb{R}}^n\}$$

is the set of all possible

$A\mathbf{x}$. Let

$V=\mathrm{Col}(A)$. The projection

$\mathbf{w}={\mathrm{proj}}_V(\mathbf{b})$ is the unique point on

$V$ with the shortest distance to

$\mathbf{b}$. Thus, we may solve

$A\mathbf{x}=\mathbf{w}$ instead. By the projection formula, we have

$$A\mathbf{x}=\mathbf{w}=A(A^{\mathrm{\top }}A{)}^{-1}{A}^{\mathrm{\top }}\mathbf{b},$$

so we may choose

$\mathbf{x}=(A^{\mathrm{\top }}A{)}^{-1}{A}^{\mathrm{\top }}\mathbf{b}$.

Sample answer

The projection of

$\mathbf{b}$ onto the column space

$\mathrm{Col}(A)$ is

$\mathbf{w}=(A^{\mathrm{\top }}A{)}^{-1}{A}^{\mathrm{\top }}\mathbf{b}$. Since

$A\mathbf{x}=\mathbf{b}$ has no solution, we solve

$A\mathbf{x}=\mathbf{w}$ instead, which means

$\mathbf{x}=(A^{\mathrm{\top }}A{)}^{-1}{A}^{\mathrm{\top }}\mathbf{b}$.

The rest is the computation. Now we have

$$\begin{array}{rl}\mathbf{x}& =(A^{\mathrm{\top }}A{)}^{-1}{A}^{\mathrm{\top }}\mathbf{b}\\ & ={\left[\begin{array}{cc}4& 10\\ 10& 30\end{array}\right]}^{-1}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 2& 3& 4\end{array}\right]\left[\begin{array}{c}1\\ 1\\ 2\\ 2\end{array}\right]\\ & =\left[\begin{array}{c}0.5\\ 0.4\end{array}\right].\end{array}$$

We could try that

$$A\mathbf{x}=\left[\begin{array}{c}0.9\\ 1.3\\ 1.7\\ 2.1\end{array}\right]$$

and

$\Vert A\mathbf{x}-\mathbf{b}{\Vert }^2={0.1}^2+{0.3}^2+{0.3}^2+{0.1}^2=0.2$, which seems to be a promising answer.

This note can be found at Course website > Learning resources.