Teaching a new trick to an old dog: Revisiting the quadratic programming formulation of sparse recovery using ADMM
One of the early successful approaches to deal with the now classical ℓ2 + ℓ1 optimization formulation of sparse signal recovery (often known as the LASSO) was based on re-writing it as a bound-constrained 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.