A variable projection method for large-scale inverse problems with ℓ¹ regularization

Inference by means of mathematical modeling from a collection of observations remains a crucial tool for scientific discovery and is ubiquitous in application areas such as signal compression, imaging restoration, and supervised machine learning. With ever-increasing model complexities and larger data sets, new specially designed methods are urgently needed to recover meaningful quantities of interest. We consider the broad spectrum of linear inverse problems where the aim is to reconstruct quantities with a sparse representation on some vector space. We provide a new variable projection augmented Lagrangian algorithm to solve the underlying ℓ¹ regularized inverse problem that is both efficient and effective. We present the proof of convergence for an algorithm using an inexact step for the projected problem at each iteration. The performance and convergence properties for various imaging problems are investigated. The efficiency of the algorithm makes it feasible to automatically find the regularization parameter, here illustrated using an argument based on the degrees of freedom of the objective function equipped with a bisection algorithm for root-finding.