Home / Curated / Algorithms / Iterative Hard Thresholding for Compressed Sensing

Iterative Hard Thresholding for Compressed Sensing

Algorithms AIMech:IterativeHardThresholdingForCompressedSensing DRAFT

Aliases: Iterative Hard Thresholding, IHT for Compressed Sensing, Blumensath-Davies Iterative Hard Thresholding, Projected Gradient Hard Thresholding

Iterative Hard Thresholding for Compressed Sensing (IHT) is a first-order non-convex projected gradient algorithm analyzed by Blumensath and Davies (2009) for recovering s-sparse and compressible signals x in R^M from noisy linear measurements y = Phi x + e in R^N (N < M). Starting from x^{[0]} = 0, each iteration n >= 0 updates x^{[n+1]} = H_s(x^{[n]} + Phi^T(y - Phi x^{[n]})), where the non-linear hard-thresholding operator H_s(a) retains the s largest-magnitude entries of a and sets all remaining M - s entries to zero. Under the Restricted Isometry Property beta_{3s} < 1/sqrt(32) (where ||Phi_B^T Phi_B - I||_2 <= beta_{|B|}), IHT requires only a single matrix-vector application of Phi and Phi^T per iteration (avoiding the inner least-squares inversions of CoSaMP and Subspace Pursuit) while guaranteeing geometric contraction ||x - x^{[n]}||_2 <= 2^{-n} ||x^s||_2 + 6 ||x - x^s||_2 + (6/sqrt(s)) ||x - x^s||_1 + 5 ||e||_2.

Identity Notes & Concept Scope Distinct from convex l1 Basis Pursuit / Lasso (AIO:LassoRegression), greedy Orthogonal Matching Pursuit (AIMech:OrthogonalMatchingPursuitTroppGilbertSignalRecovery), and two-stage least-squares pursuit methods (CoSaMP and Subspace Pursuit). Specifically captures the Blumensath-Davies (2009) Iterative Hard Thresholding update x^{[n+1]} = H_s(x^{[n]} + Phi^T(y - Phi x^{[n]})) (Equation 1.5), its RIP contraction analysis on evolving 3s-sparse unions B^n = Gamma^{x,s} union Gamma^n union Gamma^{n+1} (Theorem 4 and Corollary 1), and its residual-based finite-termination criterion (Lemma 5 and Theorem 5).

Claims & Grounded Evidence

3 Claims

Mechanism #claim-01

By restricting the gradient step a^{[n]} = x^{[n]} + Phi^T(y - Phi x^{[n]}) to the union support B^{n+1} = Gamma^{x,s} union Gamma^n union Gamma^{n+1} of cardinality |B^{n+1}| <= 3s, the best-s-term property ||x^{[n+1]}_{B^{n+1}} - a^{[n]}_{B^{n+1}}||_2 <= ||x_{B^{n+1}} - a^{[n]}_{B^{n+1}}||_2 combines with the triangle inequality and RIP bounds ||(I - Phi_B^T Phi_B) v||_2 <= beta_{3s} ||v||_2 to yield the per-step linear error recursion ||r^{n+1}||_2 <= 2*sqrt(2)*beta_{3s} ||r^n||_2 + 2*(1+sqrt(2))*sqrt(1+beta_{2s}) ||tilde{e}||_2 = (1/sqrt(2)) ||r^n||_2 + 4.38 ||tilde{e}||_2 whenever beta_{3s} < 1/sqrt(32).

supports Source: Iterative hard thresholding for compressed sensing · Locator: Section 3.2, Lemmas 1-4 and Proof of Theorem 4, Equations 3.9-3.17, pp. 6-8
supports Source: Iterative hard thresholding for compressed sensing (Crossref metadata) · Locator: Bibliographic metadata for Applied and Computational Harmonic Analysis 27(3):265-274

Scope #claim-02

For exactly s-sparse signals x = x^s in the presence of observation noise e, Corollary 1 establishes ||x - x^{[n]}||_2 <= 2^{-n/2} ||x||_2 + 5 ||e||_2 after n iterations, and Lemma 5 proves that once ||x^s - x^{[n]}||_2 <= 1.25 ||tilde{e}||_2, consecutive iterates satisfy the observable stopping bound ||x^{[n]} - x^{[n-1]}||_2 <= 2.5 ||tilde{e}||_2 and residual bound ||y - Phi x^{[n]}||_2 <= 2.34 ||tilde{e}||_2 within k* <= ceil(2 log_2(||x^s||_2 / ||tilde{e}||_2)) steps (Theorem 5).

supports Source: Iterative hard thresholding for compressed sensing · Locator: Section 2.1, Theorem 4 and Corollary 1, pp. 4-5; Section 3.3, Lemma 5 and Theorem 5, pp. 8-9

Limitation #claim-03

Unit-step Iterative Hard Thresholding requires the sensing matrix Phi to be properly scaled so that its 3s-restricted isometry constant satisfies beta_{3s} < 1/sqrt(32) approx 0.1768 (or spectral norm < 1 for convergence to a local minimum); if the signal sparsity s exceeds the RIP threshold of the undersampled measurement operator or if Phi is unscaled, the linear gradient step amplifies off-support interference and fails to recover the signal.

supports Source: Iterative hard thresholding for compressed sensing · Locator: Section 1.2, Convergence discussion, p. 3; Section 2.1, Theorem 4 condition beta_{3s} < 1/sqrt(32) and Section 4 Discussion, pp. 4, 9-10

⚠️ Curated Limitations & Negative Results

Requires the sensing operator Phi to satisfy the 3s-Restricted Isometry Property beta_{3s} < 1/sqrt(32) with unit step size (or adaptive step-size scaling); when the signal is dense or s exceeds the undersampling RIP capacity, IHT cannot recover the underlying vector.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LinearRegression` Linear Regression	related_match	IHT solves cardinality-constrained linear inverse problems y = Phi x + e via hard-thresholded gradient descent.
`AIO:LassoRegression` Lasso Regression	related_match	IHT is the direct non-convex l0 hard-thresholding counterpart to l1-penalized Lasso / Basis Pursuit.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r314-primary-pdf`	Iterative hard thresholding for compressed sensing Thomas Blumensath, Mike E. Davies	primary paper full_text	ID: https://doi.org/10.1016/j.acha.2009.04.002 sha256:8f79a0c78751…
`r314-arxiv-abs`	Iterative hard thresholding for compressed sensing (arXiv abstract) Thomas Blumensath, Mike E. Davies	primary paper abstract_only	ID: https://arxiv.org/abs/0805.0510v1 sha256:746f7b74e1a4…
`r314-metadata-cr`	Iterative hard thresholding for compressed sensing (Crossref metadata) Thomas Blumensath, Mike E. Davies	primary paper abstract_only	ID: https://doi.org/10.1016/j.acha.2009.04.002 sha256:1e679d2f8c63…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T06:20:00Z

Updated: 2026-10-19T06:20:00Z

Source File: data/curated/IterativeHardThresholdingForCompressedSensing.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories