Compressed Sensing Codes

A long list of compressive sensing codes (or sparse recovery solvers) can be found here 

This page is dedicated to codes I implemented on the subject of Compressed Sensing. A better implementation is surely available from the authors, please contact them for true and tried implementations. Other codes can be found on the Monday Morning Algorithm Series page. The Nuit Blanche blog on Compressed Sensing is here. General Codes for Compressed Sensing can be found here or at the Rice Compressed Sensing Repository. I am trying, as much as I can, to make sure these codes work with Octave.

1. Reconstruction codes

* CoSaMP

1.CoSaMP.m: by Bob Sturm can be found here with some explanation. 

[ Warning the following two versions may not be optimal: 

2.   cosamp.m implemented by David Mary as described in CoSaMP: Iterative signal recovery from incomplete and inaccurate samples by Deanna Needell and Joel Tropp.

3. A version of CoSAMP called cosamp3.m by Daryl Lim. ]

* Subspace Pursuit for Compressive Sensing

1. Wei Dai provided me with the original code used in the paper and asked me to put it on this site. It is called CSRec_SP.m.This version is to be used instead of the one listed below.

2. [Warning this version of the code is NOT optimal, please use the code provided below by the authors] The code is here. Version 0.1, March 13th, 2008. The algorithm was introduced here and implemented here. The algorithm is implemented from directions given in Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity by Wei Dai and Olgica Milenkovic.

* Reweighted Lp algorithm

1. Lp_re.m ,Version 0.1, Feb 8th, 2008. It was implemented from Iteratively Reweighted Algorithms for Compressive Sensing by Rick Chartrand and Wotao Yin.

* S-POCS Algorithm

1.cspocs_K.m, can be found in this zip file. This algorithm was discovered and implemented by Laurent Jacques. The algorithm is discussed in this entry (Monday Morning Algorithm 16: S-POCS, Using Non Convex Sparse Signal Space Instead of the Convex l1 Ball Improves POCS Recovery). 

* Smoothed L0 norm algorithm

1. sl0.m as provided G. Hosein Mohimani and described in Fast Sparse Representation using Smoothed L0 Norm by G. Hosein Mohimani, Massoud Babaie-Zadeh and Christian Jutten. Article submitted to IEEE Trans. on signal processing. [ Important Update: The authors now have a site with a probably updated version of the algorithm, please visit the Smoothed L0 (SL0) Algorithm for Sparse Decomposition site ]


* Subspace Pursuit + Reweighted Lp reconstruction algorithm for Compressive Sensing

The code is here with an example. It is a cleaned up version of MMA12 where it was featured and uses a sequential combination of the two algorithms listed below. [Warning this version of the code is NOT optimal, as it used my version of the Subspace Pursuit code, please read this entry for more information ]

* Other Reconstruction Techniques (codes) can be found here.

2. Measurement Matrices / Encoding

* Noiselet Measurement Matrix/ Fast Noiselet Transform

1. Fast Noiselet Transform (1d and 2D) Written by Laurent Jacques. A newer and faster version can be found on Laurent Jacques' code webpage. Some comments on Noiselets by Laurent Jacques.

2.  1. Build_Noiselets.m, version 1. April 14th, 2008. Written by Laurent Duval.

* Sparse Matrix Measurement

1. SparseMeasurementMatrix.m, Version 0.1, Feb. 8th, 2008

Implemented from Sparse Recovery Using Sparse Random Matrices by Radu Berinde and Piotr Indyk ( an older version of this paper is here).

* Scrambled Block Hadamard Ensemble

1. sbhe.m, version 0.1, March 24th, 2008

Implemented from Fast compressive imaging using scrambled block Hadamard ensemble by Lu Gan, Thong Do and Trac Tran.

* Other Compressed Sensing Measurement Matrices can be found here.

3. Examples

* How to Wow your friends (example)

This script shows you how to reconstruct a series of sine functions by evaluating that series only at few points using the Compressed Sensing framework. Some explanations are given here.

* Compressed Sensing Meets Machine Learning

The script is here. More explanation are given in Compressed Sensing meets Machine Learning / Recognition via Sparse Representation Classification Algorithm, an entry and script written by Jort Gemmeke

* Comparison between various reconstruction codes:

A Comparison of the Reconstruction Capability of CoSaMP, OMP, Subspace Pursuit and Reweighted Lp. The code is here. Version 2.

* Other codes implemented in the Monday Morning Algorithm series can be found here.

The disclaimer for using these codes can be found here.

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License.

Site Meter