An Interior-Point Method for Large-Scale l1-Regularized Least SquaresS.-J. Kim, K. Koh, M. Lustig, S. Boyd, and D. Gorinevsky
IEEE Journal on Selected Topics in Signal Processing, 1(4):606-617,
December 2007. 2012 IEEE Signal Processing Society Best Paper Award. Recently, a lot of attention has been paid to l1 regularization based methods for sparse signal reconstruction (e.g., basis pursuit denoising and compressed sensing) and feature selection (e.g., the Lasso algorithm) in signal processing, statistics, and related fields. These problems can be cast as l1-regularized least squares programs (LSPs), which can be reformulated as convex quadratic programs (QPs), and then solved by several standard methods such as interior-point methods, at least for small and medium size problems. In this paper we describe a specialized interior-point method for solving large-scale l1-regularized LSPs that uses the preconditioned conjugate gradients (PCG) algorithm to compute the search direction. The interior-point method can solve large sparse problems with a million variables with high accuracy in a few tens of minutes on a PC. It can efficiently solve very large dense problems, that arise in sparse signal recovery with orthogonal transforms, by exploiting fast algorithms for those transforms. The performance of the method is demonstrated with real medical resonance imaging (MRI) data. Roughly speaking, we can compute an adequately accurate solution within around a hundred PCG steps, which amounts to performing a few hundred fast Fourier transform operations on the object of interest. |