adding weights to nonlinear least squares algorithm

Note: this uses MathML code produced by OpenOffice. It doesn't seem to work on Internet Explorer. It's also been rejected by Chrome. But it works on Safari, Chromium, and Firefox.

Nonlinear least-square fits are done with a Jacobian Matrix, which describes the linearized dependencies of the model, evaluated at each of the points, on each of the model parameters.  In this case I show two parameters, τ₁ and τ₂.  I like writing these things out, rather than using index notation, because index notation is a bit abstract.  In the following, f is a function of time t representing the model to be fit.

$A=\left[\begin{array}{cc}{\frac{\partial f}{\partial {\tau }_1}\mid }_{t_1}& {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_1}\\ {\frac{\partial f}{\partial {\tau }_1}\mid }_{t_2}& {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_2}\\ ⋮& ⋮\\ {\frac{\partial f}{\partial {\tau }_1}\mid }_{t_{N-1}}& {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_{N-1}}\\ {\frac{\partial f}{\partial {\tau }_1}\mid }_{t_N}& {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_N}\end{array}\right]$

 

With the unweighted nonlinear least-squares fit, the transpose of the Jocobian matrix is then taken:

$A^T=\left[\begin{array}{ccccc}{\frac{\partial f}{\partial {\tau }_1}\mid }_{t_1}& {\frac{\partial f}{\partial {\tau }_1}\mid }_{t_2}& \cdots & {\frac{\partial f}{\partial {\tau }_1}\mid }_{t_{N-1}}& {\frac{\partial f}{\partial {\tau }_1}\mid }_{t_N}\\ {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_1}& {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_2}& \cdots & {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_{N-1}}& {\frac{\partial f}{\partial {\tau }_2}\mid }_{t_N}\end{array}\right]$

 

This then creates a linear equation describing the iteration of the solution.  In the following, P_i are the points to be fit, of which there are N.  Point P_i is sampled at time t_i.

$A^{T}A\left[\begin{array}{c}\Delta {\tau }_1\\ \Delta {\tau }_2\end{array}\right]=A^T\left[\begin{array}{c}{P}_1-{f\mid }_{t_1}\\ P_1-{f\mid }_{t_1}\\ ⋮\\ P_{N-1}-{f\mid }_{t_{N-1}}\\ P_N-{f\mid }_{t_N}\end{array}\right]$

 

To weight this, I replace the A^T matrix with the following:

$A_W^T=\left[\begin{array}{ccccc}{w_1\frac{\partial f}{\partial {\tau }_1}\mid }_{t_1}& {w_2\frac{\partial f}{\partial {\tau }_1}\mid }_{t_2}& \cdots & {w_{N-1}\frac{\partial f}{\partial {\tau }_1}\mid }_{t_{N-1}}& {w_N\frac{\partial f}{\partial {\tau }_1}\mid }_{t_N}\\ {w_1\frac{\partial f}{\partial {\tau }_2}\mid }_{t_1}& {w_2\frac{\partial f}{\partial {\tau }_2}\mid }_{t_2}& \cdots & {w_{N-1}\frac{\partial f}{\partial {\tau }_2}\mid }_{t_{N-1}}& {w_N\frac{\partial f}{\partial {\tau }_2}\mid }_{t_N}\end{array}\right]$

 

Then I solve the following modified equation for Δτ₁ and Δτ₂:

$A_w^{T}A\left[\begin{array}{c}\Delta {\tau }_1\\ \Delta {\tau }_2\end{array}\right]=A_w^T\left[\begin{array}{c}{P}_1-{f\mid }_{t_1}\\ P_1-{f\mid }_{t_1}\\ ⋮\\ P_{N-1}-{f\mid }_{t_{N-1}}\\ P_N-{f\mid }_{t_N}\end{array}\right]$

 

On the right side of this equation, each P_i − f|_ti are multiplied by a weighting factor w_i, consistent with points being duplicated.  Similarly, on the left side of the equation, the normalization term is weighted, as it must be since all that matters is the relative weights, not the absolute weights.

It's good to check this with simple cases.  One is to reduce the number of parameters to one: τ.  Then additionally I'll reduce the number of data points to a single point: t₁.

Then the above equation becomes:

$w_1{\left(\frac{\partial f}{\partial \tau }\right)}^2\Delta \tau =w_1\frac{\partial f}{\partial \tau }\left(P_1-{f\mid }_{t_1}\right)$

Note the weights cancel, as they must, since there's only one point. It's easy to see from the equation that this is the correct result: it's Newton's method in one dimension.

If I change back to two parameters and two points, I get:

$\begin{array}{c}\left[w_1{{\left(\frac{\partial f}{\partial {\tau }_1}\right)}^2\mid }_{t_1}+w_2{{\left(\frac{\partial f}{\partial {\tau }_1}\right)}^2\mid }_{t_2}\right]\Delta {\tau }_1+\left[w_1{\left(\frac{\partial f}{\partial {\tau }_1}\frac{\partial f}{\partial {\tau }_2}\right)\mid }_{t_1}+w_2{\left(\frac{\partial f}{\partial {\tau }_1}\frac{\partial f}{\partial {\tau }_2}\right)\mid }_{t_2}\right]\Delta {\tau }_2=\\ w_1{\frac{\partial f}{\partial {\tau }_1}\mid }_{t_1}\left(P_1-{f\mid }_{t_1}\right)+w_2{\frac{\partial f}{\partial {\tau }_1}\mid }_{t_2}\left(P_2-{f\mid }_{t_2}\right)\end{array}$

and:

$\begin{array}{c}\left[w_1{{\left(\frac{\partial f}{\partial {\tau }_2}\right)}^2\mid }_{t_1}+w_2{{\left(\frac{\partial f}{\partial {\tau }_2}\right)}^2\mid }_{t_2}\right]\Delta {\tau }_2+\left[w_1{\left(\frac{\partial f}{\partial {\tau }_1}\frac{\partial f}{\partial {\tau }_2}\right)\mid }_{t_1}+w_2{\left(\frac{\partial f}{\partial {\tau }_1}\frac{\partial f}{\partial {\tau }_2}\right)\mid }_{t_2}\right]\Delta {\tau }_1=\\ w_1{\frac{\partial f}{\partial {\tau }_2}\mid }_{t_1}\left(P_1-{f\mid }_{t_1}\right)+w_2{\frac{\partial f}{\partial {\tau }_2}\mid }_{t_2}\left(P_2-{f\mid }_{t_2}\right)\end{array}$

Every term is multiplied by a single weight and so only the ratios of weights matters, as expected.

If I set w₂ to zero while w₁ remains positive, the above two equations collapse into the following simplified equation:

${\frac{\partial f}{\partial {\tau }_1}\mid }_{t_1}\Delta {\tau }_1+{\frac{\partial f}{\partial {\tau }_2}\mid }_{t_1}\Delta {\tau }_2=\left(P_1-{f\mid }_{t_1}\right)$

This is clearly correct yet it is underconstrained: two unknowns for a single condition. But it shows the weights are working as expected: putting the emphasis on the points with the higher weighting coefficients.

Appendix: the weights can be represented as a diagonal square matrix, the weights on the diagonal. Then I can map A^TA to A^T W A, where W is the weight matrix, A is the Jacobian matrix described by Wolfram, and A^T is the transpose. Then I simply use W A^T where in the unweighted case I'd used A^T.