Creating and sharing knowledge for telecommunications

Teaching an Old Trick to an Old Dog: Revisiting the Quadratic Programming Formulation of Sparse Recovery Using ADMM

Figueiredo, M. A. T.

Teaching an Old Trick to an Old Dog: Revisiting the Quadratic Programming Formulation of Sparse Recovery Using ADMM, Proc IEEE International Conf. on Acoustics, Speech, and Signal Processing - ICASSP, Florence, Italy, Vol. -, pp. - - -, May, 2014.

Digital Object Identifier: 0

Abstract
One of the early successful approaches to deal with the now classical L2 + L1 optimization formulation of sparse signal recovery (often known as the LASSO) was based on re-writing it as a boundconstrained quadratic program (BCQP), which was then tackled using a gradient projection (GP) algorithm with a spectral (Barzilai-Borwein) step choice. The resulting algorithm (called gradient projection for sparse reconstruction – GPSR) exhibited state-of-the-art speed when it was introduced, but now, 6 years later, much faster alternatives exist. In this paper, we revisit the BCQP formulation and show how it can be efficiently dealt with using the alternating direction method of multipliers (ADMM). We give preliminary experimental evidence that this approach is competitive with the current state-of-the-art, in a set of benchmark problems.