# Least square linear approximation

This post explains how to make linear approximation with a simple example. Let’s assume we want to approximate a point cloud with a linear function : $y(x)=ax+b$.

The point cloud is given by $n$ points with coordinates ${x_i,y_i}$. The aim is to estimate $\hat{a}$ and $\hat{b}$ where $y(x)=\hat{a}x+\hat{b}$ will fit the point cloud as mush as possible. We want to minimize for each point $x_i$ the difference between $y_i$ and $y(x_i)$, ie. we want to minimize $\sum\limits_{i=1}^n{(y_i-y(x_i))^2}$. The matrix form of the system is given by:

$\left[ \begin{matrix} x_1 & 1 \\x_2 & 1 \\... & ... \\x_n & 1 \\\end{matrix} \right].\left[ \begin{matrix} \hat{a} \\\hat{b}\end{matrix} \right]=\left[ \begin{matrix} y_1 \\y_2 \\... \\y_n \\\end{matrix} \right]$

Let’s define $A$, $B$ and $\hat{x}$:

$\begin{matrix}A=\left[ \begin{matrix} x_1 & 1 \\ x_2 & 1 \\ ... & ... \\ x_n & 1 \\ \end{matrix} \right] &B=\left[ \begin{matrix} y_1 \\y_2 \\... \\y_n \\\end{matrix} \right] &\hat{x}=\left[ \begin{matrix} \hat{a} \\\hat{b}\end{matrix} \right] \end{matrix}$

The system is now given by:

$A.\hat{x}=B$

The optimal solution is given by:

$\hat{x}=A^{+}.B = A^{T}(A.A^{T})^{-1}.B$

Where $A^{+}$ is the pseudoinverse of $A$ given by $A^{+}=A^{T}(A.A^{T})^{-1}$.