The In-Crowd Algorithm for Fast Basis Pursuit Denoising

We introduce a fast method, the “in-crowd” algorithm, for finding the exact solution to basis pursuit denoising problems. The in-crowd algorithm discovers a sequence of subspaces guaranteed to arrive at the support set of the final solution ofl1-regularized least squares problems. We provide theorems showing that the in-crowd algorithm always converges to the correct global solution to basis pursuit denoising problems. We show empirically that the in-crowd algorithm is faster than the best alternative solvers (homotopy, fixed point continuation and spectral projected gradient forl1minimization) on certain well- and ill-conditioned sparse problems with more than 1000 unknowns. We compare the in-crowd algorithm's performance in high- and low-noise regimes, demonstrate its performance on more dense problems, and derive expressions giving its computational complexity.