Freely Available, Optimally Tuned Iterative Thresholding Algorithms for Compressed Sensing

Arian Maleki; David L. Donoho

inria-00369615, version 1

Freely Available, Optimally Tuned Iterative Thresholding Algorithms for Compressed Sensing

Arian Maleki () ¹, David L. Donoho () ²

SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations (2009)

1: Department of Electrical Engineering - Stanford University
http://www-ee.stanford.edu/
Stanford University David Packard Building 350 Serra Mall Stanford, CA 94305-9505 United States
2: Department of Statistics - Stanford University
http:///www-stat.stanford.edu/
Stanford University Stanford University Stanford, CA 94305-4065 United States

Bibliographic reference

Type of document: Peer-reviewed conferences/proceedings
Domain:
Computer Science/Signal and Image Processing

Engineering Sciences/Signal and Image processing
Title: Freely Available, Optimally Tuned Iterative Thresholding Algorithms for Compressed Sensing
Abstract: We conducted an extensive computational experiment, lasting multiple CPU-years, to optimally select parameters for important classes of algorithms for finding sparse solutions of underdetermined systems of linear equations. We make the optimally tuned implementations freely available at sparselab.stanford.edu; they can be used 'out of the box' with no user input: 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 given 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. Several specific findings are established. (a) For all algorithms the worst amplitude distribution for nonzeros is generally the constantamplitude random-sign distribution; where all nonzeros are the same size. (b) Various random matrix ensembles give the same phase transitions; random partial isometries give different transitions and require different tuning; (c) Optimally tuned Subspace Pursuit dominates optimally tuned CoSaMP, particularly so when the system is almost square. (d) For randomly decimated partial Fourier transform sampling, our recommended Iterative Soft Thresholding gives extremely good performance, making more complex algorithms like CoSaMP and Subspace Pursuit relatively pointless.
Full text language: English
Publication date: 2009
Audience: international
Conference title: SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations
Conference city: Saint Malo
Country: France
Conference date: 2009-04-06
Organizer: Inria Rennes - Bretagne Atlantique
Scientific editor(s): Rémi Gribonval

Attached file list to this document:

PDF

35.pdf

(365.1 KB)

inria-00369615, version 1
http://hal.inria.fr/inria-00369615
oai:hal.inria.fr:inria-00369615
From: Ist Rennes <>
Submitted on: Friday, 20 March 2009 14:50:07
Updated on: Friday, 20 March 2009 15:28:09

See short view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%% inria-00369615, version 1
%% http://hal.inria.fr/inria-00369615
@inproceedings{maleki:inria-00369615,
    hal_id = {inria-00369615},
    url = {http://hal.inria.fr/inria-00369615},
    title = {{Freely Available, Optimally Tuned Iterative Thresholding Algorithms for Compressed Sensing}},
    author = {Maleki, Arian and Donoho, David L.},
    abstract = {{We conducted an extensive computational experiment, lasting multiple CPU-years, to optimally select parameters for important classes of algorithms for finding sparse solutions of underdetermined systems of linear equations. We make the optimally tuned implementations freely available at sparselab.stanford.edu; they can be used 'out of the box' with no user input: 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 given 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. Several specific findings are established. (a) For all algorithms the worst amplitude distribution for nonzeros is generally the constantamplitude random-sign distribution; where all nonzeros are the same size. (b) Various random matrix ensembles give the same phase transitions; random partial isometries give different transitions and require different tuning; (c) Optimally tuned Subspace Pursuit dominates optimally tuned CoSaMP, particularly so when the system is almost square. (d) For randomly decimated partial Fourier transform sampling, our recommended Iterative Soft Thresholding gives extremely good performance, making more complex algorithms like CoSaMP and Subspace Pursuit relatively pointless.}},
    language = {English},
    affiliation = {Department of Electrical Engineering - Stanford University , Department of Statistics - Stanford University},
    booktitle = {{SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations}},
    address = {Saint Malo, France},
    organization = {Inria Rennes - Bretagne Atlantique},
    editor = {R{\'e}mi Gribonval },
    audience = {international },
    year = {2009},
    pdf = {http://hal.inria.fr/inria-00369615/PDF/35.pdf},
}

%F inria-00369615, version 1
%0 Conference Proceedings
%U http://hal.inria.fr/inria-00369615
%2 INFO:INFO_TS;SPI:SIGNAL
%T Freely Available, Optimally Tuned Iterative Thresholding Algorithms for Compressed Sensing
%A Maleki, Arian
%A Donoho, David L.
%+ Department of Electrical Engineering - Stanford University , Department of Statistics - Stanford University
%X We conducted an extensive computational experiment, lasting multiple CPU-years, to optimally select parameters for important classes of algorithms for finding sparse solutions of underdetermined systems of linear equations. We make the optimally tuned implementations freely available at sparselab.stanford.edu; they can be used 'out of the box' with no user input: 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 given 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. Several specific findings are established. (a) For all algorithms the worst amplitude distribution for nonzeros is generally the constantamplitude random-sign distribution; where all nonzeros are the same size. (b) Various random matrix ensembles give the same phase transitions; random partial isometries give different transitions and require different tuning; (c) Optimally tuned Subspace Pursuit dominates optimally tuned CoSaMP, particularly so when the system is almost square. (d) For randomly decimated partial Fourier transform sampling, our recommended Iterative Soft Thresholding gives extremely good performance, making more complex algorithms like CoSaMP and Subspace Pursuit relatively pointless.
%G English
%8 2009-00-00
%2 international
%B SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations
%2 Saint Malo
%2 France
%8 2009-04-06
%2 Inria Rennes - Bretagne Atlantique
%E Rémi Gribonval