Fast line searches for the robust solution of linear systems in the hybrid l1/l2 and Huber norms

Linear systems of equations arise in traveltime tomography, deconvolution, and many other geophysical applications. Nonlinear problems are often solved by successive linearization, leading to I 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 l(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 l(1) norm, can be used to reduce the sensitivity to outliers. Unfortunately, these more robust norms 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 con--vergence of these methods. We also compare LBFGS and NLCG (with and without exact line searches) to IRLS for a small number of iterations.