Revisiting the Quadratic Programming Formulation of Sparse Recovery
Figueiredo, M. A. T.
Revisiting the Quadratic Programming Formulation of Sparse Recovery, Proc SIAM Conf. on Imaging Science - SIAM-IS, Hong Kong, China, Vol. -, pp. - - -, May, 2014.
Digital Object Identifier: 0
Abstract
One of the first successful algorithms to handle the famous
L2+L1 optimization problem of sparse recovery (a.k.a. the
LASSO) was based on reformulating it as a bound-constrained quadratic program (BCQP), solved using projected gradient descent with spectral (Barzilai-Borwein) step choice. We revisit the BCQP formulation, considering two different algorithmic approaches: the alternating direction method of multipliers and a quasi-Newton-type algorithm. Although both involve a matrix inverse in each iteration, in several relevant problems this inversion can be efficiently computed and these methods achieve
state-of-the-art speed.