Creating and sharing knowledge for telecommunications

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


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.