Fast line searches for the robust solution of linear systems in the hybrid ℓ1/ℓ2 and Huber norms

Authors:
Publisher website
Google Scholar
Abstract
Linear systems of equations arise in traveltime tomography, deconvolution, and many other geophysical applications. Nonlinear problems are often solved by successive linearization, leading to a sequence of linear systems. Overdetermined linear systems are solved by minimizing some measure of the size of the misfit or residual. The most commonly used measure is the ℓ2 norm (squared), leading to least squares problems. The advantage of least squares problems for linear systems is that they can be solved by methods (for example, QR factorization) that retain the linear behavior of the problem. The disadvantage of least squares solutions is that the solution is sensitive to outliers. More robust norms, approximating the ℓ1 norm, can be used to reduce the sensitivity to outliers. Unfortunately, these more robustnorms lead to nonlinear minimization problems, even for linear systems, and many efficient algorithms for nonlinear minimization problems require line searches. One iterative method for solving linear problems in these more robust norms is iteratively reweighted least squares (IRLS). Recently, the limited-memory Broyden, Fletcher, Goldfarb, and Shanno (BFGS) algorithm (LBFGS) has been applied efficiently to these problems. A variety of nonlinear conjugate gradient algorithms (NLCG) can also be applied. LBFGS and NLCG methods require a line search in each iteration. We show that exact line searches for these methods can be performed very efficiently for computing solutions to linear systems in these robust norms, thereby promoting fast convergence of these methods. We also compare LBFGS and NLCG (with and without exact line searches) to IRLS for a small number of iterations.