Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing

By Arian Maleki, David L. Donoho. IEEE Journal on Selected Topics in Signal Processing, 2009

304 citations recorded by the source corpus.

We conducted an extensive computational experiment, lasting multiple CPU-years, to optimally select parameters for two important classes of algorithms for finding sparse solutions of underdetermined systems of linear equations. We make the optimally tuned implementations available at sparselab.stanford.edu; they run ¿out of the box¿ with no user tuning: it is not necessary to select thresholds or know the likely degree of sparsity. Our class of algorithms includes iterative hard and soft thresholding with or without relaxation, as well as CoSaMP, subspace pursuit and some natural extensions. As a result, our optimally tuned algorithms dominate such proposals. Our notion of optimality is defined in terms of phase transitions, i.e., we maximize the number of nonzeros at which the algorithm can successfully operate. We show that the phase transition is a well-defined quantity with our suite of random underdetermined linear systems. Our tuning gives the highest transition possible within each class of algorithms. We verify by extensive computation the robustness of our recommendations to the amplitude distribution of the nonzero coefficients as well as the matrix ensemble defining the underdetermined system. Our findings include the following. 1) For all algorithms, the worst amplitude distribution for nonzeros is generally the constant-amplitude random-sign distribution, where all nonzeros are the same amplitude. 2) Various random matrix ensembles give the same phase transitions; random partial isometries may give different transitions and require different tuning. 3) Optimally tuned subspace pursuit dominates optimally tuned CoSaMP, particularly so when the system is almost square.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/5612748b26fccd0df77e5c091b15fe0bce969022

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Message passing algorithms for compressed sensing: I. motivation and construction (2009, background): “The interested reader is referred to [3] for a survey and detailed comparison.”
Compressed Sensing Signal and Data Acquisition in Wireless Sensor Networks and Internet of Things (2013, background): “In contrast to BP, basis pursuit de-noising (BPDN) (also called LASSO) has additional de-noising performance [27]–[30].”
SPICE: A Sparse Covariance-Based Estimation Method for Array Processing (2011, background): “, [6] for a critical discussion on this aspec t).”
From Denoising to Compressed Sensing (2014, methodology): “To demonstrate the efﬁcacy of the D-AMP framework, we evaluate its performance in an imaging application.”
Compressed Sensing for Wireless Communications: Useful Tips and Tricks (2015, methodology): “This approach called iterative har d thresholding (IHT) [90], [91] performs the following update step iteratively”