Research map / Learning theory and algorithms / Matrix and tensor methods

Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm

ICML 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Signal recovery and phase retrieval · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Applies the straight-through estimator to sparse support recovery, yielding the Support Exploration Algorithm (SEA), which explores more supports than IHT/HTP/OMP/ELS and comes with RIP-based recovery guarantees.

Problem

Sparse support recovery (model selection) from noisy linear measurements is NP-hard; existing greedy and thresholding algorithms explore limited supports and struggle with strongly coherent matrices, and STE, used for quantized networks, is poorly understood theoretically.

Approach

Reparameterize the k-sparse problem as minimizing F(H(z)) where H projects a dense support-exploration variable z onto the best k-sparse least-squares solution on its top-k support, and update z with a straight-through gradient computed at the sparse iterate; the best iterate seen is returned, letting the method explore many supports.

Key results

• In phase transition experiments, SEA initialized with ELS (SEA-ELS) outperforms all tested algorithms for all m/n, with the largest gains for coherent matrices (m/n < 0.4).
• In spike deconvolution (coherence 0.97), cold-start SEA has the lowest average support distance for every sparsity k in 1 to 50, while ELS, OMP and OMPR are trapped in local minima.
• Theoretical guarantee: under a (2k+1)-RIP condition and a min-magnitude condition on the true signal, SEA recovers the true support within a bounded number of iterations; the RIP-based conditions are more stringent than those of existing methods.

Measured effects reported in the paper

Surprising findings

• The loss along SEA iterations oscillates strongly, yet the best iterate is retained, and the convergence proofs do not rely on decrease of the objective.
• SEA explores about two times fewer supports than ELS while outperforming it in deconvolution experiments.

Limitations

• Theoretical guarantees require RIP conditions that do not hold for coherent matrices where SEA performs best, so the empirical advantage is not explained by the theory.
• Conditions on the true signal (ratio of max to min nonzero magnitude) make recovery guarantees restrictive; the RIP-based condition is more stringent than the state of the art.
• Halting criterion and step size were not tuned; the method uses a fixed large number of iterations.

Experimental setup

Datasets: synthetic Gaussian matrices synthetic convolution (Gaussian filter) spike deconvolution problems

Benchmarks: phase transition diagram (n=500) spike deconvolution (n=500, sparsity 1 to 50)

Metrics: success rate of exact support recovery support distance phase transition threshold at 95% success

Baselines: IHT HTP OMP OMPR ELS LASSO

Builds on: BinaryConnect Hard Thresholding Pursuit Iterative Hard Thresholding Orthogonal Matching Pursuit

Closest papers by meaning

• Sparse Support Recovery with Non-smooth Loss Functions (NeurIPS 2016 · similarity 0.89)
• The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.88)
• The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information (NeurIPS 2024 · similarity 0.88)
• Iterative Regularization with k-support Norm: An Important Complement to Sparse Recovery (AAAI 2024 · similarity 0.88)
• Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization (ICML 2024 · similarity 0.86)
• How many measurements are enough? Bayesian recovery in inverse problems with general distributions (NeurIPS 2025 · similarity 0.86)