Pong

## May 25th 2015, Weighted Least Squares

With ordinary least squares fitting all measurements $m_i$ are treated equally. But for example in our GPS fitting scenario older points should contribute less than newer ones. So the measurements need to be weighted differently by introducing weights $w_i$ in the sum of residuals:

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

Again, we find the minimum by setting the gradient to zero: $\nabla R=0$.

Calculating the partial derivatives of the gradient leads to the following three linear equations:

$\frac{dR}{dc_0} = \sum_i 2(w_i c_0 + w_i c_1 t_i + w_i c_2 t_i^2 - w_i m_i) w_i = 0$
$\frac{dR}{dc_1} = \sum_i 2(w_i c_0 + w_i c_1 t_i + w_i c_2 t_i^2 - w_i m_i) w_i t_i = 0$
$\frac{dR}{dc_2} = \sum_i 2(w_i c_0 + w_i c_1 t_i + w_i c_2 t_i^2 - w_i m_i) w_i t_i^2 = 0$

This corresponds to the following system of linear equations:

$\left( \begin{array}{c c c} \sum_i w_i^2 & \sum_i w_i^2 t_i & \sum_i w_i^2 t_i^2 \\ \sum_i w_i^2 t_i & \sum_i w_i^2 t_i^2 & \sum_i w_i^2 t_i^3 \\ \sum_i w_i^2 t_i^2 & \sum_i w_i^2 t_i^3 & \sum_i w_i^2 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 w_i^2 m_i \\ \sum_i w_i^2 m_i t_i \\ \sum_i w_i^2 m_i t_i^2 \end{array} \right)$

Solving for $(c_0, c_1, c_2)^T$ yields:

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

If the system of linear equations is overdetermind (e.g. if $n<3$), we use a linear polynomial $f(t)=c_0+c_1t$ instead of a quadratic polynomial function as a fallback solution:

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

So that

$\left( \begin{array}{c} c_0 \\ c_1 \end{array} \right) = \left( \begin{array}{c c} \sum_i w_i^2 & \sum_i w_i^2 t_i \\ \sum_i w_i^2 t_i & \sum_i w_i^2 t_i^2 \end{array} \right)^{-1} \left( \begin{array}{c} \sum_i w_i^2 m_i \\ \sum_i w_i^2 m_i t_i \end{array} \right)$

If this system is overdetermined, again, the solution corresponds to a constant polynomial function $f(t)=c_0$ with

$c_0 = \frac{\sum_i w_i^2 m_i}{\sum_i w_i^2 }$