Iterative Hard Thresholding for Compressed Sensing

By Thomas Blumensath, M. Davies. 2008

2,526 citations recorded by the source corpus.

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.

Subfields: Biomedical Engineering, Computational Mechanics, Electrical and Electronic Engineering

How researchers see this paper

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

In Biomedical Engineering

In Computational Mechanics

In Electrical and Electronic Engineering

Citations in the corpus

Best Subset Selection via a Modern Optimization Lens (2015, methodology): “In these cases, the algorithm can be shown to have a linear convergence rate [9, 10], where the rate depends upon the RIP constants.”
Robust Regression via Hard Thresholding (2015, methodology): “Assuming X satisfies the RSC/RSS properties (defined below), (3) can be solved efficiently using results from sparse recovery (for example the IHT algorithm [11, 14] analyzed in [12]).”
Parallel Coordinate Descent for L1-Regularized Loss Minimization (2011, methodology): “Hard l0 (Blumensath & Davies, 2009) uses iterative hard thresholding for compressed sensing.”
Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method (2021, methodology): “For p = 0, the algorithm aligns with the iterative hard thresholding (IHT) algorithm [8], designed for solving the ℓ 0 ball-constrained problem.”
Compressed Sensing with Coherent and Redundant Dictionaries (2010, neutral): “(There are other algorithmic approaches to compressed sensing based on greedy algorithms such as Orthogonal Matching Pursuit [31,42], Iterative Thresholding [7,23], Compressive Sampling Matching Pursuit [34], and many others.)”
Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit (2012, background): “(Candes and Tao, 2007; Chen et al., 1999; Blumensath and Davies, 2009)) provides us with a exploration technique that enables to estimate θ, or more simply its support, provided that θ is sparse, with few measurements.”
Block-Sparse Signals: Uncertainty Relations and Efficient Recovery (2009, methodology): “We point out that the term block-coherence was used previously in [31] in the context of quantifying the recovery performance of the MP algorithm in block-incoherent dictionaries.”
Compressed Channel Sensing: A New Approach to Estimating Sparse Multipath Channels (2010, methodology): “In addition, recent theoretical results have established that θ in this case can be reliably reconstructed from r by making use of either tractable mixed-norm optimization programs [39]–[41], efficient greedy algorithms [28], [60], or fast iterative thresholding methods [61], [62]; see [63] for the ”
Robust Recovery of Signals From a Structured Union of Subspaces (2008, background): “This question is addressed in the following proposition, which quotes a result from [46] based on the proofs of [47]; we rephrase the result to match our notation.”
Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform (2018, methodology): “A main success in compressed sensing (CS) is that there are efﬁcient algorithms [BD08, NT08] for Problem 3.1 when the matrix M satisﬁes a property called the RIP.”
Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching Pursuit (2007, background): “Recent work on thresholding algorithms such as Iterative Hard Thresholding (IHT) by Blumensath and Davies has also provided similar strong guarantees [3].”
Learning the MMSE Channel Estimator (2017, background): “, the orthogonal matching pursuit (OMP) algorithm [28] or iterative hard thresholding (IHT) [29].”
Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing (2009, neutral): “In stage one, we screen for ’signiﬁcant’ nonzeros just as in IST and IHT: We let I i denote the combined support of v i and x i and we solve We then threshold a second time, x i +1 = η 2 t 2 i ( w i ) , producing a sparse vector.”
Sparse Methods for Direction-of-Arrival Estimation (2016, background): “We note that many methods and algorithms have been proposed for sparse signal recovery, e.g., convex relaxation or `1 optimization [11, 12], `q, 0 q 1 (pseudo-)norm optimization [28–34], greedy algorithms such as orthogonal matching pursuit (OMP), compressive sampling matching pursuit (CoSaMP) a”
Multi-Task Learning for Spatio-Temporal Event Forecasting (2015, methodology): “For non-convex problems, we apply the iterative Group Hard Thresholding (IGHT) [8] framework, which is guaranteed to converge to a local solution.”
Low-rank Solutions of Linear Matrix Equations via Procrustes Flow (2015, methodology): “Let M T 0 = C T 0 Σ T 0 D T T 0 be the Singular Value Decomposition (SVD) of M T 0 . f f Updates of the form (2.1) have a long history in compressed sensing/matrix sensing literature (see e.g. [TG07, GK09, NT09, NV09, BD09, MJD09, CCS10]).”