# An Efficient Algorithm for the Separable Nonlinear Least Squares Problem
## 2 Analysis
\begin{array}[ ]{ll}0&\text{if $p>q$,}\\ -[C^{T}_{p}(\overline{y})]^{\prime}_{j}[C_{p}(\overline{y})]^{\prime}_{k}& \text{if $p=q$,}\\ -[C^{T}_{p}(\overline{y})]^{\prime}_{j}[C_{q}(\overline{y})]^{\prime}_{k}-[C^{T} _{p}(\overline{y})]^{\prime}_{k}[C_{q}(\overline{y})]^{\prime}_{j}&\text{if $p<q$.}\end{array} \right.\]  
Throughout the rest of this paper, we assume not only that \(A(y)\) has full rank \(N\), but also that it is sufficiently well-conditioned that LU factorization with partial pivoting can be performed safely. For separable nonlinear systems with a rank-deficient \(A(y)\), the technique of bordered matrices [13; 14; 15; 16] may be applied to produce a full rank matrix. The following theorem lays the foundation for our approach to using the LU factorization. Theorem 1: _Let the LU factorization of the rectangular matrix \(A(\overline{y})\) with some permutation matrix \(P(\overline{y})\) be_  
\[P(\overline{y})A(\overline{y})=L(\overline{y})U(\overline{y}), \tag{13}\]_where \(A(\overline{y})\) is \((N+\ell)\times N\), \(P(\overline{y})\) is an \((N+\ell)\times(N+\ell)\) permutation matrix, \(L(\overline{y})\) is an \((N+\ell)\times N\) unit lower triangular matrix and \(U(\overline{y})\) is an \(N\times N\) nonsingular upper triangular matrix._  
1. _The matrix_ \[\overline{M}(\overline{y})\equiv[A(\overline{y})|S(\overline{y})],\] (14) _where_ \[S(\overline{y})\equiv P^{T}(\overline{y})\left[ \begin{array}{c}0\\ I_{\ell}\end{array} \right],\] _is nonsingular._
2. _Define_ \[\Psi(\overline{y})\equiv[\overline{M}^{T}(\overline{y})]^{-1}\left[ \begin{array} []{c}0\\ I_{\ell}\end{array} \right].\] (15) _Then, the thin positive QR factorization_ \[\Psi(\overline{y})\equiv C(\overline{y})R(\overline{y})\] (16) _produces a thin orthonormal_ \((N+\ell)\times\ell\) _matrix_ \(C(\overline{y})\) _and a small_ \(\ell\times\ell\) _nonsingular upper triangular matrix_ \(R(\overline{y})\)_, and_ \[C^{T}(\overline{y})A(\overline{y})=0,\quad C^{T}(\overline{y})C(\overline{y})= I_{\ell}.\] (17)  
Proof. : (a) By direct computation, \(\overline{M}(\overline{y})\) is a product of nonsingular matrices:  
\[\overline{M}(\overline{y})=P^{T}(\overline{y})\left[\begin{array} []{c|c}L(\overline{y})U(\overline{y})&\left| \begin{array}{c}0\\ I_{\ell}\end{array} \right.\right] \tag{18}\] \[= P^{T}(\overline{y})\left[\begin{array}{c|c}L(\overline{y})& \left| \begin{array}{c}0\\ I_{\ell}\end{array} \right.\right]\left[ \begin{array}{c}U(\overline{y})&0\\ 0&I_{\ell}\end{array} \right].\]  
(b) By (15) and (16),  
\[C^{T}(\overline{y})A(\overline{y})=R^{-T}(\overline{y})\Psi^{T}( \overline{y})A(\overline{y})=R^{-T}(\overline{y})\left[ \begin{array}{cc}0&I _{\ell}\end{array} \right][\overline{M}(\overline{y})]^{-1}(\overline{y})A( \overline{y})\] \[= R^{-T}(\overline{y})\left[ \begin{array}{cc}0&I_{\ell}\end{array}  \right]\left[ \begin{array}{c}I_{N}\\ 0\end{array} \right]=0.\]  
From (17), we see that the matrix \(C(\overline{y})\) constructed in the theorem satisfies (7) at \(\overline{y}\), and thus, as shown in [8], Equations (11) and (12) hold for this matrix at \(\overline{y}\). To determine the computational cost, recall that we assume that \(N\to\infty\), while \(\ell\) and \(n\) are fixed and small. Then, the thin QR factorization in (16) is cheap since the matrix \(\Psi(\overline{y})\) has only \(\ell\) columns. More specifically, the LU factorization of the \((N+\ell)\times N\) dimensional \(A(\overline{y})\) in (13) costs \((N+\ell)N^{2}-N^{3}/3\approx 2N^{3}/3\) flops, with an additional \(O(N^{2})\) comparisons to produce \(P(\overline{y})\)[12], while computing \(S(\overline{y})\) only costs \(O(N)\) flops and the thin QR factorization of the \((N+\ell)\times\ell\) dimensional matrix \(S(\overline{y})\) takes only \((N+\ell)\ell^{2}-\ell^{3}=O(N)\) flops [12]. Notice that solving (11) and (12) involves solving several equations of the form \(u^{T}M(\overline{y})=v^{T}\).