A tight bound of hard thresholding
From MaRDI portal
Abstract: This paper is concerned with the hard thresholding operator which sets all but the largest absolute elements of a vector to zero. We establish a {em tight} bound to quantitatively characterize the deviation of the thresholded solution from a given signal. Our theoretical result is universal in the sense that it holds for all choices of parameters, and the underlying analysis depends only on fundamental arguments in mathematical optimization. We discuss the implications for two domains: Compressed Sensing. On account of the crucial estimate, we bridge the connection between the restricted isometry property (RIP) and the sparsity parameter for a vast volume of hard thresholding based algorithms, which renders an improvement on the RIP condition especially when the true sparsity is unknown. This suggests that in essence, many more kinds of sensing matrices or fewer measurements are admissible for the data acquisition procedure. Machine Learning. In terms of large-scale machine learning, a significant yet challenging problem is learning accurate sparse models in an efficient manner. In stark contrast to prior work that attempted the -relaxation for promoting sparsity, we present a novel stochastic algorithm which performs hard thresholding in each iteration, hence ensuring such parsimonious solutions. Equipped with the developed bound, we prove the {em global linear convergence} for a number of prevalent statistical models under mild assumptions, even though the problem turns out to be non-convex.
Recommendations
- Hard thresholding pursuit: an algorithm for compressive sensing
- Between hard and soft thresholding: optimal iterative thresholding algorithms
- scientific article; zbMATH DE number 6982922
- A generalized class of hard thresholding algorithms for sparse signal recovery
- Iterative hard thresholding for compressed sensing
Cites work
- A mathematical introduction to compressive sensing
- A proximal stochastic gradient method with progressive variance reduction
- A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit
- A simple proof of the restricted isometry property for random matrices
- A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
- Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Atomic Decomposition by Basis Pursuit
- Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
- Compressed sensing
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Decoding by Linear Programming
- Dual averaging methods for regularized stochastic learning and online optimization
- Efficient online and batch learning using forward backward splitting
- Fast global convergence of gradient methods for high-dimensional statistical recovery
- Fast Solution of $\ell _{1}$-Norm Minimization Problems When the Solution May Be Sparse
- Greed is Good: Algorithmic Results for Sparse Approximation
- Greedy sparsity-constrained optimization
- Hard thresholding pursuit: an algorithm for compressive sensing
- High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity
- scientific article; zbMATH DE number 6982922 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Improved bounds on restricted isometry constants for Gaussian matrices
- Introductory lectures on convex optimization. A basic course.
- Iterative hard thresholding for compressed sensing
- Iterative thresholding for sparse approximations
- Least angle regression. (With discussion)
- Linear Convergence of Stochastic Iterative Greedy Algorithms With Sparse Constraints
- Minimax Rates of Estimation for High-Dimensional Linear Regression Over \ell_q-Balls
- New Bounds for Restricted Isometry Constants
- On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit
- Performance comparisons of greedy algorithms in compressed sensing.
- Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima
- Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Safe and Effective Importance Sampling
- Sharp RIP bound for sparse signal and low-rank matrix recovery
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Simultaneous analysis of Lasso and Dantzig selector
- Sparse online learning via truncated gradient
- Sparse principal component analysis and iterative thresholding
- Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
- Sparse Recovery With Orthogonal Matching Pursuit Under RIP
- Stable recovery of sparse overcomplete representations in the presence of noise
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
- The convex geometry of linear inverse problems
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
- The restricted isometry property and its implications for compressed sensing
- Truncated power method for sparse eigenvalue problems
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
Cited in
(29)- Maxisets for \(\mu \) -thresholding rules
- A tight lower bound for the hardness of clutters
- Gradient projection Newton pursuit for sparsity constrained optimization
- Adaptive iterative hard thresholding for low-rank matrix recovery and rank-one measurements
- An Impossibility Result for Linear Signal Processing Under Thresholding
- Binary sparse signal recovery with binary matching pursuit
- Global and quadratic convergence of Newton hard-thresholding pursuit
- Sparse convex optimization via adaptively regularized hard thresholding
- Between hard and soft thresholding: optimal iterative thresholding algorithms
- An equivalence between critical points for rank constraints versus low-rank factorizations
- Dual iterative hard thresholding
- scientific article; zbMATH DE number 7307474 (Why is no real title available?)
- Jointly low-rank and bisparse recovery: questions and partial answers
- Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
- Heavy-ball-based hard thresholding algorithms for sparse signal recovery
- Improving first-order threshold implementations of \textsf{SKINNY}
- A tight bound of modified iterative hard thresholding algorithm for compressed sensing.
- From theoretical guarantee to practical performance: selectable and optimal step-lengths for IHT and HTP algorithms in compressed sensing
- \texttt{skscope}: fast sparsity-constrained optimization in Python
- Relaxation quadratic approximation greedy pursuit method based on sparse learning
- Convergence on thresholding-based algorithms for dictionary-sparse recovery
- New restricted isometry property analysis for _p-_q minimization
- Sufficient condition based on nearly optimal order RIC for IHT algorithm
- Supervised factor modeling for high-dimensional linear time series
- Computationally efficient and statistically optimal robust high-dimensional linear regression
- Binary least squares: an algorithm for binary sparse signal recovery
- Attribute-efficient learning of halfspaces with malicious noise: near-optimal label complexity and noise tolerance
- A new conjugate gradient hard thresholding pursuit algorithm for sparse signal recovery
- Threshold-based declustering
This page was built for publication: A tight bound of hard thresholding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558539)
