{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

$\newcommand{\proj}{\operatorname{proj}}$

# Least squares problem

## Problem

Let

$$
A = \begin{bmatrix}
1 & 1 \\
1 & 2 \\
1 & 3 \\
1 & 4
\end{bmatrix} \text{ and }
\bb = \begin{bmatrix} 1 \\ 1 \\ 2 \\ 2 \end{bmatrix}.
$$

Find $\bx\in\mathbb{R}^2$ such that $\|A\bx - \bb\|$ is minimized.

## Thought

Givne any $m\times n$ matrix $A$, we know

$$
\Col(A) = \{A\bx: \bx\in\mathbb{R}^n\}
$$

is the set of all possible $A\bx$. Let $V = \Col(A)$. The projection $\bw = \proj_V(\bb)$ is the unique point on $V$ with the shortest distance to $\bb$. Thus, we may solve $A\bx = \bw$ instead. By the projection formula, we have

$$
A\bx = \bw = A(A\trans A)^{-1}A\trans \bb,
$$

so we may choose $\bx = (A\trans A)^{-1}A\trans\bb$.

## Sample answer

The projection of $\bb$ onto the column space $\Col(A)$ is $\bw = (A\trans A)^{-1}A\trans \bb$. Since $A\bx = \bb$ has no solution, we solve $A\bx = \bw$ instead, which means $\bx = (A\trans A)^{-1}A\trans \bb$.

The rest is the computation. Now we have

$$
\begin{aligned}
\bx &= (A\trans A)^{-1}A\trans \bb \\
&= \begin{bmatrix}
4 & 10 \\
10 & 30
\end{bmatrix}^{-1}
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 3 & 4
\end{bmatrix}
\begin{bmatrix} 1 \\ 1 \\ 2 \\ 2 \end{bmatrix} \\
&= \begin{bmatrix} 0.5 \\ 0.4 \end{bmatrix}.
\end{aligned}
$$

We could try that

$$
A\bx = \begin{bmatrix} 0.9 \\ 1.3 \\ 1.7 \\ 2.1 \end{bmatrix}
$$

and $\|A\bx - \bb\|^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.*