Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing

Abstract

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 {\tt 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.

12 pages, 14 figures

References in corpus (2)

• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Compressed Sensing in Astronomy

Cited by in corpus (50)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Sparse Distributed Learning Based on Diffusion Adaptation
• Weighted SPICE: A Unifying Approach for Hyperparameter-Free Sparse Estimation
• A Sparsity-Aware Adaptive Algorithm for Distributed Learning
• Compressed Sensing Signal Recovery via Forward-Backward Pursuit
• Near optimal compressed sensing without priors: Parametric SURE Approximate Message Passing
• Linear Convergence of Adaptively Iterative Thresholding Algorithms for Compressed Sensing
• Orthogonal Matching Pursuit with Replacement
• An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
• Online Hyperparameter-Free Sparse Estimation Method
• Variational Free Energies for Compressed Sensing
• Orthonormal Expansion l1-Minimization Algorithms for Compressed Sensing
• A Unifying Analysis of Projected Gradient Descent for ${\ell }_p$-constrained Least Squares
• Group Iterative Spectrum Thresholding for Super-Resolution Sparse Spectral Selection
• Compressive Sensing for Spread Spectrum Receivers
• Fusion of Greedy Pursuits for Compressed Sensing Signal Reconstruction
• Compressed Sensing with Linear Correlation Between Signal and Measurement Noise
• Optimal Quantization for Compressive Sensing under Message Passing Reconstruction
• GPU-Accelerated Algorithms for Compressed Signals Recovery with Application to Astronomical Imagery Deblurring
• Improving A*OMP: Theoretical and Empirical Analyses With a Novel Dynamic Cost Model
• Does ${\ell }_p$-minimization outperform ${\ell }_1$-minimization?
• Analysis-based sparse reconstruction with synthesis-based solvers
• Near-optimal matrix recovery from random linear measurements
• Sparse Vector Distributions and Recovery from Compressed Sensing
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• EM based Framework for Single-shot Compressive Holography
• Improving Smoothed l0 Norm in Compressive Sensing Using Adaptive Parameter Selection
• Online Recovery Guarantees and Analytical Results for OMP
• Approximate Message Passing for Indoor THz Channel Estimation
• Compressed Sensing for STM imaging of defects and disorder
• Real-Time Reconstruction of Counting Process through Queues
• A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing
• An Exploration of the Heterogeneous Unsourced MAC
• Fast thresholding algorithms with feedbacks for sparse signal recovery
• Recovery of Sparsely Corrupted Signals
• Subspace Thresholding Pursuit: A Reconstruction Algorithm for Compressed Sensing
• BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory
• Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay
• Data-driven Algorithm Selection and Parameter Tuning: Two Case studies in Optimization and Signal Processing
• Adaptive support driven Bayesian reweighted algorithm for sparse signal recovery
• Alternating direction algorithms for ${\ell }_0$ regularization in compressed sensing
• Algebraic Optimization of Binary Spatially Coupled Measurement Matrices for Interval Passing
• Random Access for Massive Machine-Type Communications
• Sparse Solution of Underdetermined Linear Equations via Adaptively Iterative Thresholding
• Generalized Approximate Message Passing for Massive MIMO mmWave Channel Estimation with Laplacian Prior
• The convergence guarantee of the iterative thresholding algorithm with suboptimal feedbacks for large systems