{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

# Linear regression

## Problem

Consider the data:

| i | xi | yi |
| --- | --- | --- |
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 3 | 2 |
| 4 | 4 | 2 |

Find a straight line $f(x) = c_0 + c_1x$ such that $\sum_{i=1}^4 (f(x_i) - y_i)^2$ is minimized.

## Thought

For any given data set $(x_1, y_1), \ldots, (x_N, y_N)$ and the straight line $f(x) = c_0 + c_1x$, the key observation here is that

$$
\begin{bmatrix} f(x_1) \\ \vdots \\ f(x_N) \end{bmatrix} =
\begin{bmatrix} c_0 + c_1x_1 \\ \vdots \\ c_0 + c_1x_N \end{bmatrix} =
c_0\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix} +
c_1\begin{bmatrix} x_1 \\ \vdots \\ x_N \end{bmatrix} =
\begin{bmatrix}
1 & x_1 \\
\vdots & \vdots \\
1 & x_N
\end{bmatrix}
\begin{bmatrix} c_0 \\ c_1 \end{bmatrix}.
$$

With

$$
A = \begin{bmatrix}
1 & x_1 \\
\vdots & \vdots \\
1 & x_N
\end{bmatrix}, \
\bc = \begin{bmatrix} c_0 \\ c_1 \end{bmatrix}, \text{ and }
\by = \begin{bmatrix} y_1 \\ \vdots \\ y_N \end{bmatrix},
$$

we are looking for appropriate $\bc$ to minimize $\|A\bc - \by\|^2$. This is a least square problem, and we know that the answer is $\bc = (A\trans A)^{-1}A\trans\by$.

## Sample answer

Let

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

Then the answer is

$$
\begin{aligned}
\bc &= (A\trans A)^{-1}A\trans \by \\
&= \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}
$$

Thus, $f(x) = 0.5 + 0.4x$ is the straight line that best describes the data, which is also known as the **best fitting line** .

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