Compressed Sensing: Chaining Pursuit Code for dimension reduction in the L1 norm for sparse vectors

Make that seven codes useful to do compressed sensing. Joel Tropp made available a Matlab toolbox to perform Compressed Sensing using Chaining pursuit [tar.gz]. The Chaining Pursuit algorithm was explained in the following paper entitled Algorithmic linear dimension reduction in the l`1 norm for sparse vectors by Anna Gilbert, Martin Strauss, Joel Tropp, and Roman Vershynin:

Using a number of different algorithms, we can recover approximately a sparse signal with limited noise, i.e, a vector of length d with at least d−m zeros or near-zeros, using little more than mlog(d) nonadaptive linear measurements rather than the d measurements needed to recover an arbitrary signal of length d. We focus on two important properties of such algorithms.
• Uniformity. A single measurement matrix should work simultaneously for all signals.
• Computational Efficiency. The time to recover such an m sparse signal should be close to the obvious lower bound, mlog(d/m).
This paper develops a new method for recovering m sparse signals that is simultaneously uniform and quick. We present a reconstruction algorithm whose run time, O(mlog2(m) log2(d)), is sublinear in the length d of the signal. The reconstruction error is within a logarithmic factor (in m) of the optimal m-term approximation error in l`1. In particular, the algorithm recovers m-sparse signals perfectly and noisy signals are recovered with polylogarithmic distortion. Our algorithm makes O(mlog2(d)) measurements, which is within a logarithmic factor of optimal. We also present a small space implementation of the algorithm.
These sketching techniques and the corresponding reconstruction algorithms provide an algorithmic dimension reduction in the l`1 norm. In particular, vectors of support m in dimension d can be linearly embedded into O(mlog2 d) dimensions with polylogarithmic distortion. We can reconstruct a vector from its low-dimensional sketch in time O(mlog2(m) log2(d)). Furthermore, this reconstruction is stable and robust under small perturbations.

Joel also came out with bounds of interest to the previous small example I gave earlier on approximating sines with diracs (Compressed Sensing: How to Wow your friends). The article is entitled: "On the linear independence of spikes and sines" [ .pdf | arXiv math.FA 0709.0517 ]

Photo Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Southwest Research Institute: New Horizons Spacecraft watching Io and its volcano and Europa in the same photo shoot.