# An Efficient Algorithm for the Separable Nonlinear Least Squares Problem
## 2 Analysis  
We begin by presenting the relevant background results from [8]. Assume that \(A(y)\) and \(b(y)\) are twice Lipschitz continuously differentiable in a neighborhood of the least squares solution \(y^{*}\) of (1). As shown in [5; 6; 7; 8], there exists a smoothly differentiable \((N+\ell)\times\ell\) matrix \(C(y)\) whose columns form an orthonormal basis of \(Null(A^{T}(y))\) in a neighborhood of \(y^{*}\). Then, finding the least squares solution of (1) can be reduced to finding the least squares solution of (5). Our Gauss-Newton type method for solving (5) takes the form  
\[[(f^{\prime}(y^{(m)}))^{T}f^{\prime}(y^{(m)})+\Sigma_{i=1}^{\ell} f_{i}(y^{(m)})H_{i}(y^{(m)})](y^{(m+1)}-y^{(m)}) \tag{6}\] \[= -(f^{\prime}(y^{(m)}))^{T}f(y^{(m)}),\]where \(f(y)\equiv C^{T}(y)b(y)\) and \(f^{\prime}(y)\), \(f_{i}(y)\) and \(H_{i}(y)\) denote the derivative of \(f(y)\), the \(i\)-th component of \(f(y)\), and the Hessian matrix of \(f_{i}(y)\), respectively. In [8], we proved that, at any point \(y^{(m)}\) in the iteration (6), the particular matrix \(C(y^{(m)})\) whose columns form an orthonormal basis for the nullspace of \(A^{T}(y^{(m)})\) can be replaced by any other orthonormal basis \(\widetilde{C}(y^{(m)})\) for this space, without changing \(y^{(m+1)}\). Thus, instead of using the function \(f(y)\equiv C^{T}(y)b(y)\) in (6), we may use a different function \(g(y)\equiv\widetilde{C}^{T}(y)b(y)\) at each iteration point \(y^{(m)}\). This freedom to use any orthonormal basis for the nullspace of \(A^{T}(y)\) at the point \(y^{(m)}\) is key to our numerical technique. It also permits us to write simply \(C(y^{(m)})\) and \(f(y^{(m)})\) instead of \(\widetilde{C}(y^{(m)})\) and \(g(y^{(m)})\) in the rest of this note, regardless of the particular matrix \(C(y)\) being used, and for simplicity we write \(\overline{y}\) instead of \(y^{(m)}\). The analysis below centers on the efficient computation of the terms required to use (6) at the particular point \(y^{(m)}=\overline{y}\). The following results are derived and used in [5; 6; 7; 8] and are required for our analysis below. With the terms as defined above, and writing \(C_{i}(y)\) for the \(i\)-th column of the matrix \(C(y)\),  
\[C^{T}(y)A(y)=0,\quad C^{T}(y)C(y)=I, \tag{7}\]  
\[f^{\prime}(y)=C^{T}(y)b^{\prime}(y)+\left[ \begin{array}{cc}[C^{T}(y)]^{ \prime}_{1}b(y)&...&[C^{T}(y)]^{\prime}_{n}b(y)\end{array} \right], \tag{8}\]  
and the \((j,k)\)-th entry of the \(n\times n\) Hessian matrix \(H_{i}(y)\) is  
\[[C^{T}_{i}(y)]^{\prime\prime}_{j,k}b(y)+[C^{T}_{i}(y)]^{\prime}_{j}[b(y)]^{ \prime}_{k}+[C^{T}_{i}(y)]^{\prime}_{k}[b(y)]^{\prime}_{j}+C^{T}_{i}(y)[b(y)]^ {\prime\prime}_{j,k}. \tag{9}\]  
Here, we use \([C(y)]^{\prime}_{j}\) and \([C(y)]^{\prime\prime}_{j,k}\) to denote the termwise first derivative w.r.t. \(y_{j}\) and second derivative w.r.t. \(y_{j},y_{k}\), respectively, of \(C(y)\), for \(j,k=1,\ldots,\)\(n\). Define the \((N+\ell)\times(N+\ell)\) nonsingular matrix  
\[M(y)\equiv\left[ \begin{array}{cc}A(y)&C(y)\end{array} \right]. \tag{10}\]  
Then, we showed in [8] that  
\[[C(\overline{y})]^{\prime}_{j}M(\overline{y})=\left[ \begin{array}{cc}-C^{T} (\overline{y})[A(\overline{y})]^{\prime}_{j}&0_{(N+\ell)\times\ell}\end{array} \right] \tag{11}\]  
and  
\[[C^{T}(\overline{y})]^{\prime\prime}_{j,k}M(\overline{y})=\] \[\left[-[C^{T}(\overline{y})]^{\prime}_{j}[A(\overline{y})]^{ \prime}_{k}-[C^{T}(\overline{y})]^{\prime}_{k}[A(\overline{y})]^{\prime}_{j}- C^{T}(\overline{y})[A(\overline{y})]^{\prime\prime}_{j,k}\mid[K(\overline{y})]^{ \prime\prime}_{j,k}\right], \tag{12}\]  
where the \((p,q)\)-entry \(\left[K(\overline{y})]^{\prime\prime}_{j,k}\right]_{(p,q)}\) of the upper triangular matrix \(\left[K(\overline{y})]^{\prime\prime}_{j,k}\right]\) is  
\[\left[K(\overline{y})]^{\prime\prime}_{j,k}\right]_{(p,q)}=\left\{