LSQR

LSQR (Paige & Saunders 1982) solves least-squares problems

$$\underset{\mathbf{x}}{\min }\Vert A\mathbf{x}-\mathbf{b}{\Vert }_2\text{or}\underset{\mathbf{x}}{\min }{\Vert \left(\begin{array}{c}A\\ \sqrt{\lambda }B\end{array}\right)\mathbf{x}-\left(\begin{array}{c}\mathbf{b}\\ 0\end{array}\right)\Vert }_2$$

for rectangular, sparse or matrix-free $A$. It uses only products with $A$ and $A^{\top }$. In exact arithmetic it is equivalent to CG applied to the normal equations $A^{\top }A\mathbf{x}=A^{\top }\mathbf{b}$, but it is numerically more stable because it never forms $A^{\top }A$, whose condition number is the square of that of $A$. It is based on Golub–Kahan bidiagonalisation.

In EIT. A Levenberg–Marquardt step minimises $\Vert J\delta +r{\Vert }^2+\lambda \Vert B\delta {\Vert }^2$, where $B^{\top }B=L_{\text{LM}}$ is the damping matrix. This is exactly the stacked least-squares problem above, with $A=J$ and $\mathbf{b}=-r$. With $B=I$ it is plain damped least squares, which LSQR supports directly through its damping parameter. For a general $L_{\text{LM}}$, use a factor $B$ (for example the Cholesky factor of the mass or stiffness matrix) or change variables.

Early termination of LSQR acts as an additional implicit regularisation.

References

1. C. C. Paige, M. A. Saunders (1982). LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares. ACM Trans. Math. Softw. 8(1), 43–71. doi:10.1145/355984.355989
2. Å. Björck (1996). Numerical Methods for Least Squares Problems. SIAM. doi:10.1137/1.9781611971484