Implementation: Signal Space CoSaMP Toolbox

From Mark Davenport's page:

The bulk of the Compressive sensing (CS) literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well-conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary.

This software package implements a variant of the iterative reconstruction algorithm CoSaMP for this more challenging setting. In contrast to prior approaches, the method is "signal-focused"; that is, it is oriented around recovering the signal rather than its dictionary coefficients.

For further details, see the paper "Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries," by M.A. Davenport, D. Needell, and M.B. Wakin.

Signal Space CoSaMP can be downloaded here; the Matlab files entitled "demo_*.m" provide several examples of how to invoke Signal Space CoSaMP and compare the results to traditional CS algorithms. The Matlab data (.mat) files necessary to reproduce the figures presented in the paper can be downloaded here. Please e-mail mdav-at-gatech-dot-edu if you find any bugs or have any questions.

The attendant paper: Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries by Mark A. Davenport, Deanna Needell, Michael B. Wakin. The abstract reads:

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well-conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary. In this paper we describe a variant of the iterative reconstruction algorithm CoSaMP for this more challenging setting. We utilize the D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are "signal-focused"; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. We also provide a discussion of practical examples and empirical results.

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.