Monday, January 14, 2008

Compressed Sensing: A Method for Large-Scale l1-Regularized Least Squares

An Efficient Method for Compressed Sensing in Proceedings International Conference on Signal Processing
by Seung-Jean Kim, Kwangmoo Koh, Michael Lustig, and Stephen Boyd. The abstract reads

Compressed sensing or compressive sampling (CS) has been receiving a lot of interest as a promising method for signal recovery and sampling. CS problems can be cast as convex problems, and then solved by several standard methods such as interior-point methods, at least for small and medium size problems. In this paper we describe a specialized interior point method for solving CS problems that uses a preconditioned conjugate gradient method to compute the search step. The method can efficiently solve large CS problems, by exploiting fast algorithms for the signal transforms used. The method is demonstrated with a medical resonance imaging (MRI) example.

We talked about l1_ls when it came out. It looks like we have an improvement. The l1_ls package and an explanation of what it does is here: l1_ls.pdf. I think at some point there should be a benchmark on recovery with very large problems with all the different algorithms available. For instance, for the calibration of the random lens imager, we need to solve for very large problems.

No comments: