Iterative hard thresholding for compressed sensing
From MaRDI portal
Abstract: Compressed sensing is a technique to sample compressible signals below the Nyquist rate, whilst still allowing near optimal reconstruction of the signal. In this paper we present a theoretical analysis of the iterative hard thresholding algorithm when applied to the compressed sensing recovery problem. We show that the algorithm has the following properties (made more precise in the main text of the paper) - It gives near-optimal error guarantees. - It is robust to observation noise. - It succeeds with a minimum number of observations. - It can be used with any sampling operator for which the operator and its adjoint can be computed. - The memory requirement is linear in the problem size. - Its computational complexity per iteration is of the same order as the application of the measurement operator or its adjoint. - It requires a fixed number of iterations depending only on the logarithm of a form of signal to noise ratio of the signal. - Its performance guarantees are uniform in that they only depend on properties of the sampling operator and signal sparsity.
In the presented paper, it is shown that one of the previously by the authors developed iterative hard thresholding algorithms (termed IHTs) has similar performance guarantees to those of Compressed Sampling Matching Pursuit. Section 2 of the paper starts with a definition of sparse signal models and a statement of the compressed sensing problem. In Section 3, an iterative hard thresholding algorithm is discussed. The rest of the paper shows that this algorithm is able to recover, with high accuracy, signals from compressed sensing observations. This result is formally stated in the theorems of the first subsection of Section 4. The rest of Section 4 is devoted to the proof of the theorems. In fact, the derived result is near-optimal as shown in Section 5. Section 6 takes a closer look at a stopping criterion for the algorithm, which guarantees certain estimation accuracy. The results of the paper are similar to those for the Compressed Sampling Matching Pursuit algorithm and a more detailed comparison is given in Section 7. However, as discussed in Section 8, uniform guarantees are not the only consideration and in practice marked differences in the average performance of different methods are apparent. For many small problems, the restricted isometry property of random matrices is often too large to explain the behavior of the different methods. Furthermore, it has long been observed that the distribution of the magnitude of the non-zero coefficients also has an important influence on the performance of different methods. Whilst the theoretical guarantees derived in the presented and similar papers are important to understand the behavior of an algorithm, it is also clear that other facts have to be taken into account in order to predict the typical performance of algorithms in many practical situations.
Recommendations
- Hard thresholding pursuit: an algorithm for compressive sensing
- Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms
- Dictionary-sparse recovery via thresholding-based algorithms
- Phase transitions for greedy sparse approximation algorithms
- Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
Cites work
- Compressed sensing
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- scientific article; zbMATH DE number 3062467 (Why is no real title available?)
- Iterative hard thresholding for compressed sensing
- Iterative thresholding for sparse approximations
- On sparse reconstruction from Fourier and Gaussian measurements
- Quantitative robust uncertainty principles and optimally sparse decompositions
- Reconstruction and subgaussian operators in asymptotic geometric analysis
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sampling signals with finite rate of innovation
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Stable signal recovery from incomplete and inaccurate measurements
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
- Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit
- Uniform uncertainty principle for Bernoulli and subgaussian ensembles
Cited in
(only showing first 100 items - show all)- Sparse estimation of Cox proportional hazards models via approximated information criteria
- MOEA/D with chain-based random local search for sparse optimization
- Observable dictionary learning for high-dimensional statistical inference
- Expander \(\ell_0\)-decoding
- Recovery of block sparse signals under the conditions on block RIC and ROC by BOMP and BOMMP
- Existence and convergence analysis of \(\ell_{0}\) and \(\ell_{2}\) regularizations for limited-angle CT reconstruction
- A globally convergent algorithm for nonconvex optimization based on block coordinate update
- An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration
- A new piecewise quadratic approximation approach for \(L_0\) norm minimization problem
- Efficient projected gradient methods for cardinality constrained optimization
- Learning semidefinite regularizers
- Convergence radius and sample complexity of ITKM algorithms for dictionary learning
- A non-smooth and non-convex regularization method for limited-angle CT image reconstruction
- Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem
- Approximately normalized iterative hard thresholding for nonlinear compressive sensing
- Compressive sensing in signal processing: algorithms and transform domain formulations
- Broken adaptive ridge regression and its asymptotic properties
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Sparse signal recovery via ECME thresholding pursuits
- Analysis of the ratio of \(\ell_1\) and \(\ell_2\) norms in compressed sensing
- Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion
- Sparse signal inversion with impulsive noise by dual spectral projected gradient method
- Optimality conditions for locally Lipschitz optimization with l₀-regularization
- A Lorentzian IHT for complex-valued sparse signal recovery
- Sparse approximate reconstruction decomposed by two optimization problems
- Measurement matrix optimization via mutual coherence minimization for compressively sensed signals reconstruction
- Maximum correntropy adaptation approach for robust compressive sensing reconstruction
- Learning general sparse additive models from point queries in high dimensions
- An algebraic perspective on integer sparse recovery
- Stochastic greedy algorithms for multiple measurement vectors
- Convergent inexact penalty decomposition methods for cardinality-constrained problems
- Iterative Potts minimization for the recovery of signals with discontinuities from indirect measurements: the multivariate case
- Modified iterations for data-sparse solution of linear systems
- The cost of privacy: optimal rates of convergence for parameter estimation with differential privacy
- Galaxy image restoration with shape constraint
- DANTE: deep alternations for training neural networks
- Adaptive wavelet estimations for the derivative of a density in GARCH-type model
- Analysis of generalized Bregman surrogate algorithms for nonsmooth nonconvex statistical learning
- Structured iterative hard thresholding with on- and off-grid applications
- Sparse methods for automatic relevance determination
- Partial gradient optimal thresholding algorithms for a class of sparse optimization problems
- A Lagrange-Newton algorithm for sparse nonlinear programming
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Unbiasing in iterative reconstruction algorithms for discrete compressed sensing
- Sparse recovery of sound fields using measurements from moving microphones
- Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
- Unconstrained \(\ell_1\)-\(\ell_2\) minimization for sparse recovery via mutual coherence
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- Iterative algorithm for discrete structure recovery
- Gradient projection Newton pursuit for sparsity constrained optimization
- The springback penalty for robust signal recovery
- Generalized greedy alternatives
- Adaptive multi-penalty regularization based on a generalized Lasso path
- Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
- Parametrized quasi-soft thresholding operator for compressed sensing and matrix completion
- Iterative hard thresholding for compressed data separation
- Fast overcomplete dictionary construction with probabilistic guarantees
- Geological facies recovery based on weighted \(\ell_1\)-regularization
- A characterization of proximity operators
- New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem
- Stability of 1-bit compressed sensing in sparse data reconstruction
- Robust high dimensional expectation maximization algorithm via trimmed hard thresholding
- Discrete optimization methods for group model selection in compressed sensing
- Matrix recipes for hard thresholding methods
- An evaluation of the sparsity degree for sparse recovery with deterministic measurement matrices
- Spectral compressive sensing
- Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
- Convergence of projected Landweber iteration for matrix rank minimization
- Fast thresholding algorithms with feedbacks for sparse signal recovery
- Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
- The convergence guarantee of the iterative hard thresholding algorithm with suboptimal feedbacks for large systems
- Accelerated iterative hard thresholding algorithm for \(l_0\) regularized regression problem
- \(h\)-\(p\) adaptive model based approximation of moment free sensitivity indices
- A new proximal iterative hard thresholding method with extrapolation for \(\ell _0\) minimization
- Sparse reconstruction with multiple Walsh matrices
- Optimization problems involving group sparsity terms
- Quantized compressed sensing for random circulant matrices
- Block matching video compression based on sparse representation and dictionary learning
- Robust sparse principal component analysis
- Outlier deletion based improvement on the stomp algorithm for sparse solution of large-scale underdetermined problems
- Greedy approximation in convex optimization
- Near oracle performance and block analysis of signal space greedy methods
- Greedy signal space methods for incoherence and beyond
- Sparsity optimization in design of multidimensional filter networks
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- Low rank tensor recovery via iterative hard thresholding
- Adaptive step-size matching pursuit algorithm for practical sparse reconstruction
- Quantization of compressive samples with stable and robust recovery
- Generalized sparse recovery model and its neural dynamical optimization method for compressed sensing
- Submodular functions: from discrete to continuous domains
- Non-iterative CS recovery algorithm for surveillance applications: subjective and real-time experience
- A refined convergence analysis of \(\mathrm{pDCA}_{e}\) with applications to simultaneous sparse recovery and outlier detection
- A simple homotopy proximal mapping algorithm for compressive sensing
- Greedy-like algorithms for the cosparse analysis model
- Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
- Wavelet optimal estimations for a density with some additive noises
- Optimized projections for compressed sensing via rank-constrained nearest correlation matrix
- Fast and RIP-optimal transforms
- Convergence analysis of projected gradient descent for Schatten-p nonconvex matrix recovery
- Nonconvex sorted \(\ell_1\) minimization for sparse approximation
This page was built for publication: Iterative hard thresholding for compressed sensing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q734323)
