Pong

May 25th 2015, Least Squares Fitting

← May 25th 2015 Track Denoising | ● | May 25th 2015 Weighted Least Squares →

The main assumption for least squares fitting of the GPS signal is that the device will maintain a constant acceleration during a short period of time.

This means that the path described in that time frame is parabolic leading to a quadratic function term.

In order to illustrate the least squares fitting approach, we first restrict ourselves to polynomial functions. Then we have a quadratic function $f(t)$:

$f(t) = c_0 + c_1t + c_2t^2$

The dependent variable is the positional coordinate and the independent variable is the time $t$.

Given a series of measurements $m_i, i=1..n$ at times $t_i$ we use the method of least squares to fit the above curve to the measured points so that the error becomes smallest. The error is called the residual.

Using squared error terms for the residual (hence the name least squares), we get the following formula for the residual R:

$ R = \sum_i (f(t_i)-m_i)^2 $

Minimizing the error corresponds to finding coefficients $c_0$, $c_1$ and $c_2$, where the residual gets minimal. We find the minimum but setting the gradient to zero: $\nabla R=0$.

Calculating the gradient and the corresponding partial derivatives leads to the following system of linear equations:

$ \left( \begin{array}{c c c} n & \sum_i t_i & \sum_i t_i^2 \\ \sum_i t_i & \sum_i t_i^2 & \sum_i t_i^3 \\ \sum_i t_i^2 & \sum_i t_i^3 & \sum_i t_i^4 \end{array} \right) \left( \begin{array}{c} c_0 \\ c_1 \\ c_2 \end{array} \right) = \left( \begin{array}{c} \sum_i m_i \\ \sum_i m_i t_i \\ \sum_i m_i t_i^2 \end{array} \right) $

The solution of the system is found by multiplying both sides with the inverse of the left-hand side matrix.

The left-hand side is a 3×3 matrix, which can be inverted easily at fixed computation cost. So the run time is in the order of n.


← May 25th 2015 Track Denoising | ● | May 25th 2015 Weighted Least Squares →

Options: