The In-Crowd Algorithm for Fast Basis Pursuit Denoising

You may recall some entries on a lensless sensor at Cornell (Facing Mona Lisa, The answer is No) , Patrick Gill, one of the inventor, and I are having an ongoing discussion on calibration. Patrick just let me know of a new reconstruction algorithm and a paper: The In-Crowd Algorithm for Fast Basis Pursuit Denoising by Patrick Gill, Albert Wang and Alyosha Molnar. The abstract reads:

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 of l1 -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 for l1 minimization) 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.

Patrick let me know of the following:

It might be of interest to your blog readers who solve BPDN. [The algorithm] works particularly well for the largest of problems (N larger than 10 000), and doesn't mind terribly-coherent A matrices. It works by selecting a group of around 25 atoms to be added to the active set simultaneously. The way we add atoms and the structure of the loops we use guarantees that this hyper-greedy approach still converges to the global BPDN optimum. ....Demo code .... is available at http://molnargroup.ece.cornell.edu/files/InCrowdBeta1.zip.

Thanks Patrick.

Image Credit: NASA/JPL/Space Science Institute. W00070549.jpg was taken on October 08, 2011 and received on Earth October 09, 2011. The camera was pointing toward SATURN at approximately 2,303,243 kilometers away, and the image was taken using the CL1 and CL2 filters. 

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.