Compressive Sensing: The Big Picture
A living document trying to paint the Big Picture in the Compressed Sensing or Compressive Sensing Framework.
[Wired/Slashdot readers, you may want to read this dedicated blog entry first!]
Table of Content:
0. Why this Living Document ?
Compressed Sensing or Compressive Sensing is about acquiring and recovering a sparse signal in the most efficient way possible (subsampling) with the help of an incoherent projecting basis. Unlike traditional sampling methods, Compressed Sensing provides a new framework for acquiring sparse signals in a mutiplexed manner. The main theoretical findings in this recent field have mostly centered on how many multiplexed measurements are necessary to reconstruct the original signal and the attendant nonlinear reconstruction techniques needed to demultiplex these signals. Another equally important thrust in the field has been the actual building of sensing hardware that could produce directly the multiplexed signals.
Information on this technique is growing fast and only few specialists understand how each of these pieces fit each other within the big picture. The Nuit Blanche blog ( RSS feed is here) provides daily update on new papers/preprints and ideas coming into the field while this document is slated to be a little less active because the big picture should not change everyday. While currently much emphasis is rightfully spent on performing faster reconstruction of the original signal from the Compressed Measurements, we are also beginning to see the emergence of other tools that complete this framework.
These tools include
 the ability to search for bases or dictionaries in which sets of signals can be decomposed in a sparse manner and,
 the ability to find and quantify specific measurements tools that are incoherent with said dictionaries.
In other words, once a signal is known to be sparse in a specific basis, one of the main challenge is to find a set of measurement tools (producing the compressed measurements) and the attendant nonlinear solver that reconstructs the original full signal. There are theoretical results yielding the minimum number of required measurements needed to produce the original signal given a specific pair of measurement matrices and nonlinear solvers. In all cases, the expected number of compressed measurements is expected to be low relative to traditional Nyquist sampling constraints. This living document aims at categorizing all these tools for the purpose of providing a rapid adoption by the community.
The next paragraphs try to bring the most updated list of different theoretical and applied endeavors implemented in this framework. The fourth paragraph tries to give an exhaustive list of hardware implementations using Compressed Sensing or Compressive Sampling. The fifth paragraph lists a search engine on the subject and the sixth paragraph provides a calendar of activities in the field. If you feel it is not accurate or missing elements please bring them to my attention. Thanks!. This document tries to summarize most of the information found in:
I have also featured a series of riddles and (magic) tricks that can make Compressive Sensing easier to understand in the CS Riddles page. For more comprehensive examples, you may want to dwell directly into Sparco and its attendant set of examples.
Once you are convinced it works and want to dwell into it, try to watch the excellent lectures videos:
In the same vein, there is a nice tutorial presentation on Compressed Sensing by Richard Baraniuk, Justin Romberg, and Michael Wakin as well as a more indeph tutorial entitled Compressive sensing  Theory and applications by Petros Boufounos, Justin Romberg and Richard Baraniuk.[ There is now a video of Richard Baraniuk showing his latest introduction to Compressed Sensing at Microsoft Research on August 4, 2008. Please be aware, that the address does not seem to work with Firefox, Chrome or Opera (I tried), it only works with Internet Explorer. The original link that can be seen from any browser is here.] Other presentations that might provide insights include:
Additionally there are two courses that might be complementary to these presentations:
Now onto the important stuff
2. Dictionaries for Sparse Recovery (How to Make or Find them)
When a signal is said to be sparse in an engineering sense, it really means that the signal is compressible, i.e. it can be expanded in either a small number of terms or in a series with significantly decaying coefficients. In order to produce Compressed Measurements, one first need to know what is the family of functions in which the signal of interest is sparse. Depending on the case, one might be lucky and know that the signal is sparse in a basis found in harmonic analysis (2.1) or one may have to spend some work in devising what these sparse basis is through an algorithm dedicated to finding sparse dictionaries from a set of signal examples(2.2 and 2.3). Finally, Remi Gribonval and Karin Schnass produce some estimate in Dictionary Identification  Sparse MatrixFactorisation via L1Minimisation on the number of training examples needed to build a dictionary.
2.1 Basis Functions for which signals are either sparse or compressible
2.2 Algorithms that find dictionaries in which signal representation is sparse are presented in:
 CoefROMP: Improving Dictionary Learning: Multiple Dictionary Updates and Coefﬁcient Reuse by Leslie N. Smith and Michael Elad.
 ODSL/Groupstructured dictionaries: Online GroupStructured Dictionary Learning by Zoltan Szabo, , Barnabás Póczos, and András Lőrincz: (.rar,zip,.tar)
 BPFA: Nonparametric Bayesian Dictionary Learning for Analysis of Noisy and Incomplete Images by Mingyuan Zhou, Haojun Chen, John Paisley, Lu Ren, Lingbo Li, Zhengming Xing, David Dunson, Guillermo Sapiro and Lawrence Carin.
 PADDLE is a Python package for learning dictionaries Curzio Basso
 Online Learning for Matrix Factorization and Sparse Coding by Julien Mairal, Francis Bach, Jean Ponce, Guillermo Sapiro [The code is released as SPArse Modeling Software or SPAMS]
 Dictionary Learning Algorithms for Sparse Representation (Matlab implementation of FOCUSS/FOCUSSCNDL is here)
 Multiscale sparse image representation with learned dictionaries [Matlab implementation of the KSVD algorithm is here, a newer implementation by Ron Rubinstein is here ]
 Efficient sparse coding algorithms [ Matlab code is here ]
 Nonnegative Sparse Modeling of Textures (NMF) [Matlab implementation of NMF (Nonnegative Matrix Factorization) and NTF (Nonnegative Tensor), a faster implementation of NMF can be found here, here is a more recent NonNegative Tensor Factorizations package]
 Shift Invariant Sparse Coding of Image and Music Data. Matlab implemention is here
 MoTIF : an Efficient Algorithm for Learning Translation Invariant Dictionaries, but also Learning MultiModal Dictionaries.Also, more recent: Shiftinvariant dictionary learning for sparse representations: extending KSVD.
 Thresholded SmoothedL0 (SL0) Dictionary Learning for Sparse Representations by Hadi Zayyani, Massoud BabaieZadeh and Remi Gribonval.
Let us note the Matlab Toolbox Sparsity by Gabriel Peyre that has implemented some of these techniques. Knowledge of specific domain signals enables the ability to build these hopefully small dictionaries.
For a review of the state of the art on the subject on how to compile dictionaries from training signals and attendant theoretical issues, check the following document by Remi Gribonval for his Habilitation a Diriger Des Recherches entitled: Sur quelques problèmes mathématiques de modélisation parcimonieuse translated into Sparse Representations: From Source Separation to Compressed Sensing. There is a video and in an audio only format of this presentation in French. The accompanying slides in English are here.
2.3 Data Driven Dictionaries
The next step will almost certainly bring about techniques that find elements within a manifold as opposed to a full set of functions, some sort of Data Driven Dictionary. In this setting, one can list:
Some of these techniques are being used for dimensionality reduction, which in effect is stating that datasets are compressible when being represented with these dictionaries.
Applying alternating direction method of multipliers for constrained dictionary learning
In this segment, the emphasis is on finding a means of acquiring sparse signals using projections onto bases that are incoherent with the bases found in the previous paragraph. However, a criterion for checking whether a specific measurement or encoding matrix will allow the recovery of a sparse solution is needed. For that purpose, an early argument was to expect that certain families of matrices to follow the Restricted Isometry Property (RIP). It is however only a sufficient condition and given a matrix, it is NPhard to find out if that matrices follows that property. It is also known that the RIP property is also too strict (as shown by Jared Tanner in Phase Transition Phenomenon in Sparse Approximation).
3.1 Measurement Matrix Admissibility Conditions
3.1.1 The DonohoTanner Phase Transition
The following phase transition diagram that I call the DonohoTanner phase transition is probably the only good means of figuring out if a given measurement / encoding matrix can provide good compressive capabilities with an l_1 solver. One should also note that the phase transition not only depends on the encoding matrix but also on the recovery algorithm used. The following websites provide an interactive way of determining:
3.1.2 Beyond L_1 minimization and the DonohoTanner Phase Transition for Sparse Recovery
Over time, several algorithms have beaten the DonohoTanner phase transition in the noiseless case as is shown by Bob Sturm on his Asilomar 2011 slides. These solvers use different heuristics than the L_1 norm to accomplish this. They include solvers such as SL0, IRLp, Greedy Solvers /Matching Pursuits...
but also EMBGAMP by Jeremy Vila and Phil Schniter:
as well as another very similar solver which uses specific measurement matrices to obtain a new phase diagram:
For more information on this recent developments check the following:
3.1.3 Other Properties (NSP, RIP,....)
Here is a list of properties that measurement matrices must have in order to enable sparse recovery. Let us note that most of them are sufficient conditions:
 NSP: (Null Space Property) as featured in David Donoho in Compressed Sensing and Compressed sensing and best kterm approximation by Albert Cohen, Wolfgang Dahmen, and Ronald DeVore. Sufficient conditions for the Null Space Property can be computed with the following two approaches (JN and AE):
 NSP: Anatoli Juditsky and Arkadii Nemirovski found a sufficient condition that can be computed in On Verifiable Sufficient Conditions for Sparse Signal Recovery via l_1 Minimization. The code necessary to perform this verification is located at: http://sites.google.com/site/testsensingmatrices/ ( more information can be found here)
 NSP: Alexandre d'Aspremont and Laurent El Ghaoui are computing the same constant as JN with SDP in Testing the Nullspace Property using Semidefinite Programming. The NSProp implementation is now available here: http://www.princeton.edu/~aspremon/NSPcode.htm
 SCSP, WCSP, WP: as featured in A Remark on Compressed Sensing by Kashin and Vladimir Temlyakov
 Incoherence: as shown in Sparsity and incoherence in compressive sampling by Emmanuel Candès and Justin Romberg.
 RIP In Combining Geometry And Combinatorics: A Unified Approach to Sparse Signal Recovery by Radu Berinde, Anna Gilbert, Piotr Indyk, Howard Karloff and Martin Strauss , the authors show the possibility of unifying the different measurement matrices found so far. Hence, the Restricted Isometry Property can be broken in RIP(1) or RIP(2) properties. However, when one talks about RIP, one generally refers to RIP(2). Even though, this property is NPhard to prove, an attempt to provide some bound of the Restricted Isometry Constant can be found in: Testing the Nullspace Property using Semidefinite Programming by Alexandre d'Aspremont and Laurent El Ghaoui ..Two more recent papers supply bounds for the Gaussian ensemble: Compressed Sensing: How Sharp is the Restricted Isometry Property ? by Jeffrey Blanchard, Coralia Cartis, and Jared Tanner and Improved Bounds on Restricted Isometry Constants for Gaussian Matrices by Bubacarr Bah and Jared Tanner.
 StRIP: As featured by Robert Calderbank, Stephen Howard and Sina Jafarpour in Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property. This property is computable as mentioned here but it seemed to be restricted to a certain set of encoding matrices.
 SRIP: As featured by Shamgar Gurevich and Ronny Hadani in Incoherent dictionaries and the Statistical Restricted Isometry property.
 GRIP: As featured by Jarvis Haupt and Robert Nowak in this technical report entitled A generalized restricted isometry property (more here)
 RIP_p: Laurent Jacques, David Hammond and M. Jalal Fadili mention it in their paper about Dequantizing CS. The authors used the RIP_p to characterize the performance of the BPDQ decoder. RIP_p is there just the "sandwiching" of the Lp norm (with p>=2) of the random projection of sparse signals x, i.e. Phi x, between their L2 norm multiplied by the common (1+ delta)^1/2 factors, so that RIP_2 is the common RIP. Similarly, Rick Chartrand and Valentina Staneva, in "Restricted isometry properties and nonconvex compressive sensing" introduced also an RIP_p definition, with an existence proof for Gaussian matrices, but for 0 \lt p \le 1. (see this entry)
 UUP: Terry Tao has a set of properties listed here (this is an early version)
Other NPHard properties:
Other papers/presentations of interest include:
 Compressed Sensing II, Ronald DeVore
 Ron DeVore's short course ('08)
 Compressed Sensing: Lecture I, Ronald DeVore
 Compressed Sensing: Lecture II, Ronald DeVore
 Compressed Sensing: Lecture III, Ronald DeVore
 Decoding in Compressed Sensing, Albert Cohen, Wolfgang Dahmen, Ronald DeVore, Guergana Petrova, Przemek Wojtaszczek
 Open problem on properties.
 Some stories about Lpminimization, the Restricted Isometry Property, and excessive pessimism by Remi Gribonval
3.2 NonDeterministic and Non Adaptive Measurement matrices / Encodings.
The first encoding matrices follow the RIP(2) property while the most recent sparse encoding matrices follow the RIP(1) property. In the following, the first three measurement matrices are pasted from Terry Tao site:
RIP(2)
RIP(1)
RIP_p
3.3 NonDeterministic and Adaptive Measurement codes/matrices as mentioned here (as well as new ones).
3.4 Deterministic Subsampling
3.4.1 Deterministic Subsampling with no prior information
3.4.1.1 Fourier <> Diracs
3.4.1.2 Other pair of bases
3.4.2 Deterministic Subsampling using additional prior information (besides sparsity)
Obviously, with the advent of Data Driven Dictionaries, I would expect we will have specific domain specific measurement matrix methods.
[ Please note: the most recent solvers are at the end of this list ]
[ For Authors: If your solver is not listed here, please contact me]
The following is a list of nonlinear solvers used to reconstruct the original signal from its compressed measurements / projections on an incoherent basis (as listed above in paragraph 2). Reconstruction codes span a wide series of techniques that include Matching Pursuit/Greedy, Basis Pursuit/Linear Programming, Bayesian, Iterative Thresholding, Proximal . These links generally go to the Matlab toolbox implementing these techniques. Originally, this list was similar to the list found in the excellent Rice Repository.
 l1Magic by Emmanuel Candes and Justin Romberg
 SparseLab by David Donoho, Iddo Drori, Victoria Stodden, Yaakov Tsaig, Morteza Shahram with major contributions from: Michael Saunders, Joshua SweetkindSinger, Michael Elad, Lawrence Carin, Shihao Ji, Ya Xue, David Dunson. (version 2.0)
 GPSR by Mário Figueiredo, Robert D. Nowak, Stephen J. Wright. (version 6.0)
 ell1 LS: Simple Matlab Solver for ell1Regularized Least Squares Problems by Kwangmoo Koh, SeungJean Kim, and Stephen Boyd (version beta)
 Sparsify by Thomas Blumensath (version 0.4)
 MPTK: Matching Pursuit Toolkit, with two packages based on MPTK by Sacha Krstulovic and Remi Gribonval (version 0.5.6)
 Bayesian Compressive Sensing(BCS): also includes TSWCS (release Jan 19, 2009) implemented by an MCMC approach and VBBCS implementing the basic BCS implemented via a variational Bayesian approach. Implemented by Shihao Ji, Ya Xue, David Dunson, Yuting Qi, Dehong Liu, Lihan He and Lawrence Carin. (Version 0.1)
 SPGL1: A solver for large scale sparse reconstruction by Michael Friedlander and Ewout van Der Berg (Version 1.6)
 FPC by Elaine Hale, Wotao Yin and Yin Zhang (Version 1.0)
 FPC_AS by Zaiwen Wen,Wotao Yin (Version 1.0)
 Chaining Pursuit by Joel Tropp
 Regularized OMP (ROMP) by Deanna Needell and Roman Vershynin
 TwIST by José BioucasDias and Mário Figueiredo.
 SparSA by Stephen Wright, Robert Nowak, Mario Figueiredo. (version 2.0)
 SALSA and CSALSA by Manya Afonso, Mário Figueiredo, José BioucasDias,
 Bregman Iterative Algorithms for Constrained Compressed Sensing and Related Problems by Wotao Yin, Stanley Osher, Donald Goldfarb and Jerome Darbon. It uses a modification of FPC. You need to request it from the site (more specifically here)
 The Split Bregman Method for L1 Regularized Problems. The associated C++ code is here, a new Matlab/mex version is here. By Tom Goldstein and Stan Osher.
 Applying the Proximal Point Algorithm to a Non Negative Basis Pursuit Denoising model by François Malgouyres and Tieyong Zeng. The software is here . It features Matlab codes, scripts and results (30 MB). The scripts are compatible with the SPARCO toolbox.
 Sparsest solutions of underdetermined linear systems via minimization for . The code is here. By Simon Foucart and MingJun Lai
 Chambolle's algorithm for the resolution of compressed sensing with TV regularization by Gabriel Peyre. This algorithm is included in the larger Toolbox Sparsity  A toolbox for sparse coding and sparse regularization
 Fast Bayesian Matching Pursuit (FBPM)by Justin Ziniel, Lee C. Potter, Philip Schniter. The code is located here.
 SAMP: Sparsity Adaptive Matching Pursuit for Practical Compressed Sensing : main page and attendant matlab code. By Thong T. Do, Lu Gan, Nam Nguyen, and Trac D. Tran.
 Smoothed L0 (SL0) Algorithm for Sparse Decomposition by G. Hosein Mohimani, Massoud BabaieZadeh and Christian Jutten (local version of sl0.m as provided G. Hosein Mohimani ). Now works with complex functions.
 Convex Iteration by Jon Dattorro. It is discussed in his book on Convex Optimization [1] and specifically in Chapter 4 page 306 to 314.The Matlab algorithm is available here.
 Gradient based method for cone programming with application to largescale compressed sensing by Zhaosong Lu. The attendant Matlab source codes are here.
 Sparse Matching Pursuit (SMP) and CountMin recovery algorithm as featured in the Sparse Recovery Experiments wiki of Piotr Indyk and Radu Berinde
 Alternating l_1 reconstruction algorithm, presented by Stephane Chretien in Tighter relaxations for the sparsest recovery problem. The page for the code is here.
 Nonnegative Underdetermined Iteratively Reweighted Least Squares (NUIRLS) code by Paul O’Grady and Scott Rickard as described in Compressive Sampling of NonNegative Signals.
 Compressive Sensing via Belief Propagation website and code (CSBP) by Dror Baron.
 Compressed Signal Reconstruction using the Correntropy Induced Metric by Sohan Seth, Jose C. Principe earlier. Sohan Seth also released the code implemented in the article.
 RecPF (Version 2.0, May 25th, 2009 ): A MATLAB code for image reconstruction from partial Fourier data that solves models with totalvariation and l_1 regularization and an l_2norm fidelity to fit the available incomplete Fourier data. Developed by Yin Zhang, Junfeng Yang and Wotao Yin.
 FTVd (version 3.0, January 6th, 2009): A MATLAB code for image deblurring and denoising that solves the model with totalvariation regularization and l_2norm fidelity. Developed by Yin Zhang, Junfeng Yang, Yilun Wang and Wotao Yin.
 A Coordinate Gradient Descent Method for l_1regularized Convex Minimization by Sangwoon Yun and KimChuan Toh Matlab code of the CGD method for L1regularized linear least squares problem., Matlab code of the CGD method for L1regularized logistic regression problem.
 Iteratively Reweighted Lp as implemented in Iteratively Reweighted Least Squares Minimization for Sparse Recovery by Ingrid Daubechies, Ronald DeVore, Massimo Fornasier, and C. Sinan Güntürk : irwls_main.m,it_min_l2_w_fast.m
 Two Step Reweighted l1 code from Improved Sparse Recovery Thresholds with TwoStep Reweighted $\ell_1$ Minimization by M. Amin Khajehnejad, Weiyu Xu, Salman Avestimehr, Babak Hassibi.
 Angshul Majumdar sent me a couple of Matlab files for solving lp analysis and synthesis prior algorithms. Both are first order algorithms unlike the IRLS. To a large extent they are based on the MajorizationMinimization approach, which I learnt from the Selesnick and Figueredo's paper: LpAnalysis.m , LpSynthesis.m,
 Lp_re, Iteratively Reweighted Lp  This is my implementation but a better one might be available from the authors. Implemented from Iteratively Reweighted Algorithms for Compressive Sensing by Rick Chartrand and Wotao Yin
 CSRec_SP.m. Subspace Pursuit original code as provided one of the author Wei Dai. ( Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity [*])
 COSAMP: cosamp.m implemented by David Mary . A better version by Bob Sturm can be found here. [as described in CoSaMP: Iterative signal recovery from incomplete and inaccurate samples by Deanna Needell and Joel Tropp. [*]
 SPOCS, Using Non Convex Sparse Signal Space Instead of the Convex l1 Ball Improves POCS Recovery introduced by Laurent Jacques
 Kalman Filter Compressed Sensing page by Namrata Vaswani, Wei Lu, Chenlu Qiu
 ExCoV page by Aleksandar Dogandžić and Kun Qiu.
 Angshul Majumdar has implemented some greedy algorithms for Group Sparsity. Following the works of Eldar et al in
[1] Y. C. Eldar and M. Mishali, "Robust Recovery of Signals From a Union of Subspaces", arXiv.org 0807.4581, submitted to IEEE Trans. Inform. Theory, July 2008.
[2] BlockSparsity: Coherence and Efficient Recovery by Yonina C. Eldar, Helmut Bolcskei to appear in ICASSP 2009.
Four algorithms  Block Orthogonal Matching Pursuit (BOMP), and three others, namely:
 GOMP  Group Orthogonal Matching Pursuit (similar to BOMP, except for decides the group by average correlation of each group instead of highest correlation)
 StGOMP  Stagewise GOMP; combining ideas of BOMP with StOMP
 ReGOMP  Regularized GOMP; combining ideas of ROMP and GOMP.
 All these codes are accessible here.
 Angshul Majumdar also implemented the original OLS algorithm proposed in T. Blumensath, M. E. Davies; "On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares", manuscript 2007. Their algorithm is implemented in SparseOLS.zip. As well as two modified versions: ROLS  Regularized OLS (following ideas similar to ROMP), StOLS  Stagewise OLS (following ideas similar to StOMP)
 Fast Bayesian Compressive Sensing using Laplace Priors. by S. Derin Babacan, Rafael Molina, and Aggelos Katsaggelos. The source code can be found on the project webpage.
 NonIterative Computation of Sparsifiable Solutions to Underdetermined Kronecker Product Linear Systems of Equations by Andrew Yagle. The code is listed in the blog
 YALL1 (version beta4, March26, 2009), Your ALgorithms for L1 by Yin Zhang
 NESTA : (version 1.0, June 3, 2009) A Fast and Accurate Firstorder Method for Sparse Recovery by Jérôme Bobin, Stephen Becker, and Emmanuel Candès.
 The Two Stage l1 Approach to the Compressed Sensing Problem by Stephane Chretien. The code is here (June 10th, 2009)
 Dirk Lorenz just sent me an email:
I just wanted to let you know that I did what I should have done months or years ago: I put mfiles for l^p and especially l^1minimization on my page (see the following three m files)
 iter_thresh.m which implements the usual iterated soft thresholding for different values of p and also a sophisticated other algorithm which we called iterated hard thresholding (not to be confused with the algorithm proposed by Blumensath and Davies) . As presented in Iterated hard shrinkage for minimization problems with sparsity constraints by Kristian Bredies and Dirk A. Lorenz ).
 ssn.m which implements the semismooth Newton method for l^1minimization and which is incredibly fast for the cases in which it converges (unfortunately this is not always the case... convergence is indeed only local) ( As presented in A Semismooth Newton Method for Tikhonov Functionals with Sparsity Constraints by Roland Griesse and Dirk A. Lorenz).
 ppp_l1.m which implements the projection proximal point method for l^1 minimization presented in Numerical Functional Analysis and Optimization).
 Angshul Majumdar also sent me the following:
This is the code for solving problems of the form
min x_m,p s.t. y = Ax
I have replaced the ._2,p norm with the ._m,p norm for the group sparsity problem.
It uses the same Reweighted Least Squares method but with a different weighing method.
The jth index of the ith group is weighed by (x(j)_m)^(pm) . x(i,j)^(m2).
I derived it using the FOCUSS methodology.
The code is here: lmp_re_ls.m
 The BPDQ Toolbox by David Hammond, Laurent Jacques and M. Jalal Fadili . The Basis Pursuit Dequantizers for recovery of sparse signals from quantized random measurements.
 The GraDes algorithm is now available here. It was featured in Gradient Descent with Sparsification: An iterative algorithm for sparse recovery with restricted isometry property by Rahul Garg and Rohit Khandekar.
 proMP.m an implementation of Probabilistic Matching Pursuit for Compressive Sensing by Atul Divekar and Okan Ersoy (to be used with pbp.m )
 SLEP (Sparse Learning with Efficient Projections) package by Jun Liu and Jieping Ye provides a set of programs for sparse learning:
 ℓ1regularized (constrained) sparse learning
 ℓ1/ℓqregularized sparse learning (q>1)
 Fussed Lasso
 Sparse inverse covariance estimation
 Trace norm regularized learning
 Simon Foucart
released the Hard Thresholding Pursuit (HPT) code featured in Hard
thresholding pursuit: an algorithm for Compressive Sensing. The code
is here.
 Modelbased Compressive Sensing Toolbox: Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, Chinmay Hegde (as featured in ModelBased Compressive Sensing)
 RFSS.m is the code implemented in: ElasticNet Regularization: Error estimates and Active Set Methods.by Jin, Bangti, Lorenz, Dirk A., Schiffler, Stefan.
 ThresholdISD by Yilung Wang and Wotao Yin
 PDSparse: Penalty Decomposition Methods for $l_0$Norm Minimization by Zhaosong Lu,Yong Zhang.
 TFOCS (Templates for
FirstOrder Conic Solvers ) by Stephen Becker, Emmanuel J. Candes and Michael Grant.
 Cyclic Matching Pursuit by Bob Sturm
 Compressed Sensing Image Reconstruction via Recursive Spatially Adaptive Filtering by Aram Danielyan, Karen Egiazarian, Alessandro Foi, Vladimir Katkovnik
 ALPS: accelerated IHT methods for sparse recovery by Volkan Cevher and Anastasios Kyrillidis
 Sparse Bayesian learning exploiting temporal correlation: TSBL/TMSBL (MMV algorithms) by Zhilin Zhang and Bhaskar D. Rao.
 tMFOCUSS [temporal MFOCUSS, which exploits temporal correlation] by Zhilin Zhang and Bhaskar D. Rao.
 ARSBL [AR model based sparse Bayesian learning] by Zhilin Zhang and Bhaskar D. Rao.
 Binary Iterative Hard Thresholding (BIHT) Demo by Laurent Jacques, Jason Laska, Petros Boufounos, and Richard Baraniuk
 Approximate Message Passing (AMP) Code for Compressive Sensing by Ulugbek Kamilov
 The Generalized Approximate Message Passing (GAMP) MATLAB package by Sundeep Rangan, Alyson Fletcher, Vivek Goyal, Ulugbek Kamilov, Jason Parker, Phil Schniter.
 Compressive Imaging using Turbo AMP by Subhojit Som and Phil Schniter,
 Spectral compressive sensing toolbox by Marco Duarte and Richard Baraniuk
 Recursive Projected Compressive Sensing by Chenlu Qiu, Namrata Vaswani
 Distributed Basis pursuit ( BPinSN) : From Distributed Basis Pursuit by João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, and Markus Püschel.
 RecPC by Wotao Yin , Simon Morgan (Los Alamos National Lab), Junfeng Yang, Yin Zhang
 CLASH: The algorithm is presented in "Combinatorial Selection and Least Absolute Shrinkage via the CLASH Algorithm", Technical Report, by Anastasios Kyrillidis and Volkan Cevher (corresponding ICML 2011 Structured Sparsity Workshop slides can be found here).
 TurboGAMP: joint channelestimation/equalization/decoding of BICMOFDM signals transmitted over channels with clusteredsparse impulse responses by Phil Schniter.
 ISAL1: InfeasiblePoint Subgradient Algorithm for L1Minimization by Dirk Lorenz, Marc Pfetsch and Andreas Tillmann (SPEAR Project page)
 A*OMP: A* Orthogonal Matching Pursuit: BestFirst Search for Compressed Sensing Signal Recovery by Nazim Burak Karahanoglu and Hakan Erdogan
 SpaRCS: SpaRCS: Recovering Lowrank and Sparse matrices from Compressive Measurements by Andrew E. Waters, Aswin C. Sankaranarayanan, and Richard G. Baraniuk
 SAMUSIC: Subspace Methods for Joint Sparse Recovery by Kiryung Lee and Yoram Bresler
 EMBGAMP:: ExpectationMaximization BernoulliGaussian Approximate Message Passing by Jeremy Vila and Philip Schniter.
 BMP: Robust 1bit compressive sensing using binary matching pursuit by Ming Yan, Yi Yang, Stanley Osher
 ASPICS: Statistical physicsbased reconstruction in compressed sensing by Florent Krzakala, Marc Mézard, François Sausset,Yifan Sun, Lenka Zdeborová, (C++, Python, now in Matlab)
 CPR: Compressive Phase Retrieval From Squared Output Measurements Via Semidefinite Programming by Henrik Ohlsson, Allen Y. Yang, Roy Dong, S. Shankar Sastry.
 Compressive MUSIC (with forward CSF, and backward CSF) Compressive MUSIC: A Missing Link between Compressive Sensing and Array Signal Processing by Jong Min Kim, Ok Kyun Lee, and
Jong Chul Ye .
 MIrror Prox Solver by
Anatoli Juditsky, Fatma Kilinc Karzan, Arkadi Nemirovski. Manual is here. Attendant paper is:
L1 Minimization via Randomized First Order Algorithms
 Bregman CookBook by
Jerome Gilles
 SPIN Toolbox:
Signal Recovery on Incoherent Manifolds by Chinmay Hegde and Richard Baraniuk.
 Sparse Signal Reconstruction from Quantized Noisy Measurements via GEM Hard Thresholding by Kun. Qiu and Aleksandar Dogandžić.
 Split Bregman implementations by Tom Goldstein
 TV normed pursuits by Anastasios Kyrillidis, Gilles Puy, and Volkan Cevher.
 EMGMAMP: An Algorithm for Sparse Reconstruction: by Jeremy Vila and Phil Schniter
 Gradient Support Pursuit (GraSP) : Greedy SparsityConstrained Optimization by Sohail Bahmani, Petros Boufounos, and Bhiksha Raj.
 ProPPA: ProPPA: A Fast Algorithm for $\ell_1$ Minimization and LowRank Matrix Completion by Ranch Y.Q. Lai, Pong C. Yuen.
From now on, I will list the entries on the Nuit Blanche blog dedicated to the reconstruction solvers (One entry = one solver). They are all listed under the implementation tag, they are also listed in the Reproducible Research Page.
Last Updated July 2013 5. Hardware / Compressive Sensing Sensor implementations
Most of these entries are summarized in the Compressive Sensing Sensor / Hardware page. You should go to that page in order to see updated information. One should notice a difference between hardware that does not require modification but different operating procedures and totally new hardware. Hardware implementations vary according to what the hardware can already do. In the case of MRI, one is directly sampling in the Fourier Space and therefore it is directly amenable to subsampling in the Fourier world. Other instrumentations do not sample in the Fourier space and one is led to think of inventive schemes to do that. The most salient features of the random or noiselet measurements is that one can foresee a hardware implementation without having to know the decomposing sparse basis since there is a high probability that these two will be incoherent with each other.
Phase Retrieval Sampling strategy:

Updating...
ć Igor Carron, Dec 3, 2011, 3:11 PM
Igor Carron, May 12, 2010, 2:23 PM
Ċ Igor Carron, Jun 1, 2011, 12:07 AM
Igor Carron, Mar 30, 2010, 1:05 AM
Igor Carron, Mar 30, 2010, 1:06 AM
csindexing_matlab.zip (5k) Igor Carron, Feb 4, 2011, 1:26 AM
Ċ Igor Carron, Jun 8, 2011, 1:26 PM
Igor Carron, Apr 15, 2011, 8:50 AM
Igor Carron, Sep 30, 2010, 2:46 PM
Igor Carron, Jun 17, 2012, 1:41 PM
