# An Efficient Algorithm for the Separable Nonlinear Least Squares Problem
## 2 Analysis
However, the matrix \(M(y)\) defined in (10) and which is used in (11) and (12), differs from the matrix \(\overline{M}(\overline{y})\) defined in (14) whose LU factors are given in (18). To reduce the cost of solving (11) and (12) from \(O(N^{3})\) to \(O(N^{2})\) operations, we can exploit the factorization (18) of the matrix \(\overline{M}(\overline{y})\), as below. This result is essentially an application of the Sherman-Morrison-Woodbury formula. **Theorem 2**. : _Let \(P(\overline{y})A(\overline{y})=L(\overline{y})U(\overline{y})\) be the LU factorization of \(A(\overline{y})\) with a permutation matrix \(P(\overline{y})\) as in (13), and let the matrices \(\overline{M}(\overline{y})\), \(S(\overline{y})\) and \(C(\overline{y})\) be defined as in (14)-(16), while \(M(y)\) is defined by (10). Denote_  
\[W(\overline{y})=I_{N+\ell}-[C(\overline{y})-S(\overline{y})]C^{T}(\overline{y }). \tag{19}\]  
_Then,_  
1. \(M^{-1}(\overline{y})=\overline{M}^{-1}(\overline{y})W(\overline{y})\)_;_
2. _For_ \(u,v,w\in\mathbf{R}^{N+\ell}\)_,_ \(u^{T}M(\overline{y})=v^{T}\) _if and only if_ \[w^{T}\overline{M}(\overline{y})=v^{T},\quad u^{T}=w^{T}W(\overline{y}).\] (20)  
Proof. : \((a)\) By (18),  
\[W(\overline{y})M(\overline{y})=W(\overline{y})\left[ \begin{array} []{cc}A(\overline{y})&\mid&C(\overline{y})\end{array} \right]\] \[= \left[\{I_{N+\ell}-[C(\overline{y})-S(\overline{y})]C^{T}( \overline{y})\}A(\overline{y})\mid\{I_{N+\ell}-[C(\overline{y})-S(\overline{y })]C^{T}(\overline{y})\}C(\overline{y})\right]\] \[= [A(\overline{y})\quad\mid\quad C(\overline{y})-[C(\overline{y})-S (\overline{y})]]=[A(\overline{y})\quad\mid\quad S(\overline{y})]=\overline{M}( \overline{y}).\]  
Then,  
\[M^{-1}(\overline{y})=\overline{M}^{-1}(\overline{y})[\overline{M} (\overline{y})]M^{-1}(\overline{y})\] \[= \overline{M}^{-1}(\overline{y})[W(\overline{y})M(\overline{y})]M^ {-1}(\overline{y})=\overline{M}^{-1}(\overline{y})W(\overline{y}).\]  
Part (b) follows directly from (a). Finally, we show how the value \(z^{*}\) defined by (3) can be computed efficiently using the LU factorization of \(A(y^{*})\). **Theorem 3**. : \(z^{*}=-A^{+}(y^{*})b(y^{*})\) _if and only if_  
\[z^{*}=-\left[ \begin{array}{cc}I_{N}&0_{N\times\ell}\end{array} \right]\left[ \begin{array}{cc}A(y^{*})&C(y^{*})\end{array} \right]^{-1}b(y^{*}). \tag{21}\]  
Proof. : Let the QR factorization of \(A(y^{*})\) be  
\[A(y^{*})=QR\equiv\left[ \begin{array}{cc}(Q_{1})_{(N+\ell)\times N}&(Q_{2})_{ (N+\ell)\times\ell}\end{array} \right]\left[\begin{array}{c}R_{1}\\ \begin{array}{c}0\end{array} \right].\]  
Since \(A(y^{*})\) is full rank, we see that  
\[A^{+}(y^{*})=[A^{T}(y^{*})A(y^{*})]^{-1}A^{T}(y^{*})\] \[=\left(\left[ \begin{array}{cc}(R_{1})^{T}&0\end{array} \right]Q^ {T}Q\left[ \begin{array}{c}R_{1}\\ \begin{array}{c}0\end{array}\end{array} \right]\right)^{-1}\left[ \begin{array} []{cc}(R_{1})^{T}&0\end{array} \right]Q^{T}\] \[=R_{1}^{-1}((R_{1})^{T})^{-1}\left[ \begin{array}{cc}(R_{1})^{T}& 0\end{array} \right]Q^{T}=\left[ \begin{array}{cc}R_{1}^{-1}&0\end{array}  \right]Q^{T}.\]Since \(C(y^{*})\) is an orthonormal matrix, there exists an \(\ell\times\ell\) orthogonal matrix \(\Theta\) such that  
\[\left[ \begin{array}{cc}I_{N}&0_{N\times\ell}\end{array} \right] \left[ \begin{array}{cc}A(y^{*})&C(y^{*})\end{array} \right]^{-1}=\left[ \begin{array}{cc}I_{N}&0_{N\times\ell}\end{array} \right]\left(\mathcal{Q} \left[ \begin{array}{cc}R_{1}&0\\ 0&\Theta_{\ell\times\ell}\end{array} \right]\right)^{-1}\] \[=\left[ \begin{array}{cc}I_{N}&0_{N\times\ell}\end{array} \right] \left(\left[ \begin{array}{cc}R_{1}^{-1}&0\\ 0&\Theta_{\ell\times\ell}^{T}\end{array} \right]Q^{T}\right)=\left[ \begin{array} []{cc}R_{1}^{-1}&0\end{array} \right]Q^{T}.\]  
Hence, the conclusion follows. Computing \(z^{*}\) via (21) involves the matrix \(M(y^{*})\) of (10), but the technique of Theorem 2 may again be used to replace this by the known LU factorization (18) of \(\overline{M}(y^{*})\) obtained from the LU factorization of \(A(y^{*})\).