An efficient algorithm for the separable nonlinear least squares problem (Q1657029)

Summary: The nonlinear least squares problem \(\min_{y, z} \| A(y) z + b(y) \|\), where \(A(y)\) is a full-rank \((N + \ell) \times N\) matrix, \(y \in \mathbb R^n\), \(z \in \mathbb R^N\) and \(b(y) \in \mathbb R^{N+\ell}\) with \(\ell \geq n\), can be solved by first solving a reduced problem \(\min_y \| f(y) \|\) to find the optimal value \(y^\ast\) of \(y\), and then solving the resulting linear least squares problem \(\min_z \| A(y^\ast) z + b(y^\ast) \|\) to find the optimal value \(z^\ast\) of \(z\). We have previously justified the use of the reduced function \(f(y) = C^T(y) b(y)\), where \(C(y)\) is a matrix whose columns form an orthonormal basis for the nullspace of \(A^T(y)\), and presented a quadratically convergent Gauss-Newton type method for solving \(\min_y \| C^T(y) b(y) \|\) based on the use of QR factorization. In this note, we show how LU factorization can replace the QR factorization in those computations, halving the associated computational cost while also providing opportunities to exploit sparsity and thus further enhance computational efficiency.