This repository offers a collection of greedy algorithms for sparse recovery and several scripts to evaluate their empirical performance.
In compressed sensing, one wants to find the solution to the sparse recovery problem
$$ \min_{x \in \mathbb{R}^N} |x |_0 ~~ \text{subject to} ~~ y = A\hat{x} \label{eq:sparseRec} $$
given
As
$$ \min_{x \in \mathbb{R}^N} |x |_1 ~~ \text{subject to} ~~ y = A\hat{x}. \label{eq:basisPur} $$
Under appropriate conditions on the measurement matrix
Although
Usually the ground truth
$$ \min_{x \in \mathbb{R}^N} |x |_1 ~~ \text{subject to} ~~ |y-A\hat{x}|\leq \eta $$
for a given error threshold
The performance of the different greedy algorithms can be evaluated by running the included scripts, which give empirical results based on several Monte-Carlo simulations in which different parameters of the estimation problem are varied, respectively. Further, these empirical results can be used to plot the phase diagrams of the respective algorithms, which are two-dimensional figures that visualize the empirical probability of successful recovery while varying two of the dimensions
COSAMP
(COmpressive SAmpling Matching Pursuit), see [N+09].CSMPSP
(A hybrid between COSAMP and Subspace Pursuit), see [B+15].GOMP
(Generalized Orthogonal Matching Pursuit), see [W+12].NIHT
(Normalized Iterative Hard Thresholding), see [B+10].OMP
(Orthogonal Matching Pursuit), see [T+07].ROMP
(Regularized Orthogonal Matching Pursuit), see [N+09].STOMP
(STagewise Orthogonal Matching Pursuit), see [D+12].
The above listed algorithms can be used as stand-alone. For the correct usage, including the assignment of the inputs and outputs of the individual algorithms, refer to the comments provided in the respective source codes.
To perform the Monte-Carlo simulations, run the respective files with the prefix 'script'. Additional information is provided in the source codes.
- The code of 'Sample_measOp_CS.m' is adapted from Claudio M. Verdun, Technical University Munich.
- The remaining code is written by Thomas Weinberger ([email protected]).
If you have any problems or questions, please contact me via e-mail.
- [N+09] Needell, Deanna, and Joel A. Tropp. "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples." Applied and computational harmonic analysis 26.3 (2009): 301-321.
- [B+15] Blanchard, Jeffrey D., and Jared Tanner. "Performance comparisons of greedy algorithms in compressed sensing." Numerical Linear Algebra with Applications 22.2 (2015): 254-282.
- [W+12] J. Wang, S. Kwon and B. Shim, "Generalized Orthogonal Matching Pursuit," in IEEE Transactions on Signal Processing, vol. 60, no. 12, pp. 6202-6216, Dec. 2012, doi: 10.1109/TSP.2012.2218810.
- [B+10] T. Blumensath and M. E. Davies, "Normalized Iterative Hard Thresholding: Guaranteed Stability and Performance," in IEEE Journal of Selected Topics in Signal Processing, vol. 4, no. 2, pp. 298-309, April 2010, doi: 10.1109/JSTSP.2010.2042411.
- [T+07] J. A. Tropp and A. C. Gilbert, "Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit," in IEEE Transactions on Information Theory, vol. 53, no. 12, pp. 4655-4666, Dec. 2007, doi: 10.1109/TIT.2007.909108.
- [N+09] Needell, D., Vershynin, R. Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit. Found Comput Math 9, 317โ334 (2009).
- [D+12] D. L. Donoho, Y. Tsaig, I. Drori and J. Starck, "Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit," in IEEE Transactions on Information Theory, vol. 58, no. 2, pp. 1094-1121, Feb. 2012, doi: 10.1109/TIT.2011.2173241.