Compressed Sensing: Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity

[Update: the codes for this algorithm are here ]

Here is another preprint from Arxiv.org: Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity by Wei Dai and Olgica Milenkovic

We propose a new algorithm, termed subspace pursuit, for signal reconstruction of sparse and compressible signals with and without noisy perturbations. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques, and reconstruction capability of the same order as that of $l_{1}$-norm optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm is capable of exactly reconstructing an arbitrary sparse signals, provided that the linear measurements satisfy the restricted isometry property with a constant parameter which can be described in a closed form. In the noisy setting and the case where the signal is not exactly sparse, it can be shown that the mean squared error of the reconstruction is upper bounded by a constant multiple of the measurement and signal perturbation energy.

They give some bounds for recovery by the Subspace Pursuit Algorithm of zero-one sparse signals, sparse signals with power-law decaying entries, with exponentially decaying entries and or with noise. The conclusions are somewhat impressive.

We introduced a new algorithm, termed subspace pursuit, for low-complexity recovery of a large class of sparse signals and for sampling matrices satisfying the RIP with a constant parameter δ3K. Also presented were simulation results demonstrating that the recovery performance of the algorithm matches, and sometimes even exceeds, that of the LP programming technique; and, simulations showing that the number of iterations executed by the algorithm for 0−1 sparse signals and compressible signals is of the order O(log K).

Credit Photo: Christie L. Dyett - NASA Space Coast Launch Services, via the Darkroastedblend blog. Yes new engines are added to the Space shuttle at every launch!