Research map / Learning theory and algorithms / Matrix and tensor methods
On the Iteration Complexity of Support Recovery via Hard Thresholding Pursuit
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use approximate (gradient-descent) solutions for the restricted subproblem instead of exact solves (ablation) | HTP · Numerical study, sparsity sweep s=1 to 50 | iterations to support recovery | No clear effect |
| Use approximate subproblem solutions (GD with 50 steps) instead of exact solves (ablation) | HTP · Numerical study, sparsity sweep s=1 to 50 | percentage of success | No clear effect |
| Increase number of measurements N (condition number decreases) (ablation) | HTP · Numerical study, s=5, N from 1 to 100 | iterations to support recovery | Helped |
| Increase number of measurements N above threshold of 20 (ablation) | HTP · Numerical study, s=5 | percentage of success | Helped |
| Use a proxy function F(x) with added l2 regularization (e.g., least squares plus alpha||x||^2) rather than the sparsity-constrained objective | HTP · Theoretical statistical models (sparse linear / logistic regression) | support recovery guarantee | Helped |
Closest papers by meaning
- Exact Recovery of Hard Thresholding Pursuit (NeurIPS 2016 · similarity 0.93)
- A Fast and Provable Algorithm for Sparse Phase Retrieval (ICLR 2024 · similarity 0.88)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.87)
- Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm (ICML 2024 · similarity 0.86)
- Exponential Spectral Pursuit: An Effective Initialization Method for Sparse Phase Retrieval (ICML 2024 · similarity 0.86)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.