Solving separable nonlinear least squares problems using the QR factorization

We present a method for solving the separable nonlinear least squares problem miny,z‖F(y,z)‖, where F(y,z)≡A(y)z+b(y) with a full rank matrix A(y)∈R(N+ℓ)×N, y∈Rn, z∈RN and the vector b(y)∈RN+ℓ, with small ℓ≥n. We show how this problem can be reduced to a smaller equivalent problem miny‖f(y)‖ where the function f has only ℓ components. The reduction technique is based on the existence of a locally differentiable orthonormal basis for the nullspace of AT(y). We use Newton's method to solve the reduced problem. We show that successive iteration points are independent of the nullspace basis used at any particular iteration point; thus the QR factorization can be used to provide a local basis at each iteration. We show that the first and second derivative terms that arise are easily computed, so quadratic convergence is obtainable even for nonzero residual problems. For the class of problems with N much greater than n and ℓ the main cost per iteration of the method is one QR factorization of A(y). We provide a detailed algorithm and some numerical examples to illustrate the technique.