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:


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}.


Leave a Reply

Your email address will not be published. Required fields are marked *