Performance comparisons of greedy algorithms in compressed sensing. (English) Zbl 1363.94017

Blanchard, Jeffrey D.; Tanner, Jared

Numer. Linear Algebra Appl. 22, No. 2, 254-282 (2015).

Summary: Compressed sensing has motivated the development of numerous sparse approximation algorithms designed to return a solution to an underdetermined system of linear equations where the solution has the fewest number of nonzeros possible, referred to as the sparsest solution. In the compressed sensing setting, greedy sparse approximation algorithms have been observed to be both able to recover the sparsest solution for similar problem sizes as other algorithms and to be computationally efficient; however, little theory is known for their average case behavior. We conduct a large-scale empirical investigation into the behavior of three of the state of the art greedy algorithms: Normalized Iterative Hard Thresholding (NIHT), Hard Thresholding Pursuit (HTP), and CSMPSP. The investigation considers a variety of random classes of linear systems. The regions of the problem size in which each algorithm is able to reliably recover the sparsest solution is accurately determined, and throughout this region, additional performance characteristics are presented. Contrasting the recovery regions and the average computational time for each algorithm, we present algorithm selection maps, which indicate, for each problem size, which algorithm is able to reliably recover the sparsest vector in the least amount of time. Although no algorithm is observed to be uniformly superior, NIHT is observed to have an advantageous balance of large recovery region, absolute recovery time, and robustness of these properties to additive noise across a variety of problem classes. A principle difference between the NIHT and the more sophisticated HTP and CSMPSP is the balance of asymptotic convergence rate against computational cost prior to potential support set updates. The data suggest that NIHT is typically faster than HTP and CSMPSP because of greater flexibility in updating the support that limits unnecessary computation on incorrect support sets. The algorithm selection maps presented here are the first of their kind for compressed sensing.

MSC:

94A12	Signal theory (characterization, reconstruction, filtering, etc.)
65Y10	Numerical algorithms for specific classes of architectures
90C90	Applications of mathematical programming

Keywords:

greedy algorithm; compressed sensing; GPU computing; hard thresholding; sparse approximation

Software:

Mosek; CPLEX; CVX; GAGA; CoSaMP

References:

[1]	Donoho, Compressed sensing, IEEE Transactions on Information Theory 52 (4) pp 1289– (2006) · Zbl 1288.94016
[2]	Candès, International congress of mathematicians pp 1433– (2006)
[3]	MOSEK ApS Mosek optimization software http://www.mosek.com
[4]	CVX Research Inc CVX: Matlab software for disciplined convex programming, version 2.0 beta http://cvxr.com/cvx
[5]	ILOG CPLEX Mathematcial programming system http://www.cplex.com
[6]	Figueiredo, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE Journal Selected Topics in Signal Processing 1 (4) pp 586– (2007)
[7]	Berg, Probing the pareto frontier for basis pursuit solutions, SIAM Journal on Scientific Computing 31 (2) pp 890– (2008) · Zbl 1193.49033
[8]	Wright, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing 57 (7) pp 2479– (2009) · Zbl 1391.94442
[9]	Yin, Bregman iterative algorithms for 1-minimization with applications to compressed sensing, SIAM Journal on Imaging Science 1 (1) pp 143– (2008) · Zbl 1203.90153
[10]	Donoho DL Neighborly polytopes and sparse solution of underdetermined linear equations Technical Report 2004
[11]	Donoho, High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension, Discrete and Computational Geometry 35 (4) pp 617– (2006) · Zbl 1095.52500
[12]	Xu, Precise stability phase transitions for 1 minimization: a unified geometric framework, IEEE Transactions on Information Theory 57 (10) pp 6894– (2011) · Zbl 1365.94089
[13]	Donoho, Neighborliness of randomly projected simplices in high dimensions, Proceedings of the National Academy of Sciences USA 102 (27) pp 9452– (2005) · Zbl 1135.60300
[14]	Donoho, Sparse nonnegative solution of underdetermined linear equations by linear programming, Proceedings of the National Academy of Sciences USA 102 (27) pp 9446– (2005) · Zbl 1135.90368
[15]	Donoho, Counting faces of randomly projected polytopes when the projection radically lowers dimension, Journal of the American Mathematical Society 22 (1) pp 1– (2009) · Zbl 1206.52010
[16]	Donoho, Counting the faces of randomly-projected hypercubes and orthants, with applications, Discrete and Computational Geometry 43 (3) pp 522– (2010) · Zbl 1191.52004
[17]	Recht, Null space conditions and thresholds for rank minimization, Mathematical Programming. Series B 127 pp 175– (2011) · Zbl 1211.90172
[18]	Stojnic, Optimization in block-sparse compressed sensing and its strong thresholds, IEEE Journal of Selected Topics in Signal Processing 4 (2) pp 350– (2010)
[19]	Donoho, Message-passing algorithms for compressed sensing, Proceedings of the National Academy of Sciences 106 (45) pp 18914– (2009)
[20]	Donoho, The noise-sensitivity phase transition in compressed sensing, IEEE Transactions on Information Theory 57 (10) pp 6920– (2011) · Zbl 1365.94094
[21]	Donoho, Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing, Philosophical Transactions of The Royal Society A 367 (1906) pp 4273– (2009) · Zbl 1185.94029
[22]	Monajemi, Deterministic matrices matching the compressed sensing phase transitions of gaussian random matrices, Proceedings of the National Academy Of Sciences 110 (4) pp 1181– (2013) · Zbl 1292.94007
[23]	Needell, CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Applied and Computational Harmonic Analysis 26 (3) pp 301– (2009) · Zbl 1163.94003
[24]	Dai, Subspace pursuit for compressive sensing signal reconstruction, IEEE Transactions on Information Theory 55 (5) pp 2230– (2009) · Zbl 1367.94082
[25]	Blumensath, Iterative hard thresholding for compressed sensing, Applied and Computational Harmonic Analysis 27 (3) pp 265– (2009) · Zbl 1174.94008
[26]	Blumensath, Normalised iterative hard thresholding: guaranteed stability and performance, IEEE selected Topics in Signal Processing 4 (2) pp 298– (2010)
[27]	Foucart, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM Journal on Numerical Analysis 49 (6) pp 2543– (2011) · Zbl 1242.65060
[28]	Candes, Decoding by linear programming, IEEE Transactions on Information Theory 51 (12) pp 4203– (2005) · Zbl 1264.94121
[29]	Blanchard, Phase transitions for greedy sparse approximation algorithms, Applied and Computational Harmonic Analysis 30 (2) pp 188– (2011) · Zbl 1229.94003
[30]	Cartis C Thompson A A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing 2013 http://eprints.maths.ox.ac.uk/1752/ · Zbl 1359.94071
[31]	Donoho D Johnstone I Montanari A Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising 2013 http://front.math.ucdavis.edu/1111.1041 · Zbl 1364.94092
[32]	Maleki, Optimally tuned iterative reconstruction algorithms for compressed sensing, IEEE Journal of Selected Topics in Signal Processing 4 (2) pp 330– (2010)
[33]	Sturm B Sparse vector distributions and recovery from compressed sensing 2011
[34]	Blanchard, GPU accelerated greedy algorithms for compressed sensing, Mathematical Programming Computation 5 (3) pp 267– (2013) · Zbl 1300.65038
[35]	Blanchard JD Tanner J GAGA:GPU Accelerated Greedy Algorithms 2012 www.gaga4cs.org
[36]	Hestenes, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards 49 (6) pp 409– (1952) · Zbl 0048.09901
[37]	Blanchard JD Tanner J Performance comparisons of greedy algorithms in compressed sensing: supplementary material 2014 people.maths.ox.ac.uk/tanner/papers/PCGACS.pdf
[38]	Blanchard, Compressed sensing: how sharp is the restricted isometry property?, SIAM Review 53 (1) pp 105– (2011) · Zbl 1214.41008
[39]	Donoho, Precise undersampling theorems, Proceedings of the IEEE 98 (6) pp 913– (2010)