Research map / Learning theory and algorithms / Matrix and tensor methods
Iterative Regularization with k-support Norm: An Important Complement to Sparse Recovery
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.
Proposes IRKSN, an accelerated iterative regularization method using the k-support norm penalty for sparse recovery, with recovery conditions and an early-stopping error bound that work where l1-based conditions fail.
Problem
Sparse recovery from noisy linear measurements is NP-hard; existing iterative regularization methods rely on the l1 norm, which needs restrictive applicability conditions (e.g., RIP, sign-based conditions) and fails with correlated design matrices.
Approach
Replace the l1 regularizer in primal-dual (Linearized Bregman / accelerated dual gradient) iterative regularization with a regularizer based on the squared k-support norm plus an l2 term, yielding recovery conditions that depend on relative magnitudes of the true coefficients and do not require n >= k, together with an early-stopping bound with explicit constants.
Key results
- On the illustrative 5-variable example with n=4, only IRKSN recovers the true sparse vector with zero error, while Lasso, ElasticNet and other iterative l1 methods fail.
- In the correlated-design synthetic experiments, IRKSN achieves consistently higher support-recovery F1 than competing methods across n, snr and correlation rho (best hyperparameters chosen by grid search on F1).
- The early-stopping bound gives ||w_t - w*|| <= a t delta + b/t, which yields an O(delta^{1/2}) error at t ~ delta^{-1/2}, the standard linear rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IRKSN instead of the competing algorithms | Correlated-design synthetic support recovery · Synthetic support recovery (varied n, SNR, and correlation ρ) | F1 score | Helped |
| Use IRKSN instead of Lasso or ElasticNet | Sparse recovery in Illustrating Example 1 · Illustrating Example 1 | recovery error | Helped |
| Continue training for many iterations | IHT and IRKSN · Synthetic support recovery | F1 score | No clear effect |
| Continue training for many iterations | IRCR, IROSR, and SRDI · Synthetic support recovery | F1 score | Hurt |
Surprising findings
- Lasso cannot recover the true support for any penalty lambda in the illustrative example, even though IRKSN can.
- The k-support-norm condition depends on the relative magnitudes of the entries of w*, not only their signs, unlike the l1 sign-based condition.
Limitations
- The recovery conditions are stated under assumptions on the true vector and the design (injectivity-type and min-norm conditions), and only a simple example is analyzed.
- Hyperparameters were tuned directly on support F1 with the true support known, which is not available in practice.
- Analysis restricted to the case where the k-support norm parameter equals the sparsity k (general s-support norm left open).
Experimental setup
Datasets: synthetic correlated Gaussian data (benchopt make_correlated_data) Haxby fMRI dataset (subject 2)
Benchmarks: synthetic correlated design support recovery Haxby fMRI decoding
Metrics: F1 score of support recovery model error norm sparsity of iterates
Baselines: IHT Lasso ElasticNet KSN penalty OMP SRDI IROSR IRCR
Builds on: Lasso k-support norm regularization Accelerated dual gradient descent / linearized Bregman iterations SRDI IROSR
Closest papers by meaning
- Implicit Regularization for Optimal Sparse Recovery (NeurIPS 2019 · similarity 0.88)
- Implicit Sparse Regularization: The Impact of Depth and Early Stopping (NeurIPS 2021 · similarity 0.88)
- Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm (ICML 2024 · similarity 0.88)
- Estimating Sparse Signals With Smooth Support via Convex Programming and Block Sparsity (CVPR 2016 · similarity 0.88)
- Weakly Convex Regularisers for Inverse Problems: Convergence of Critical Points and Primal-Dual Optimisation (ICML 2024 · similarity 0.86)
- Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks (NeurIPS 2024 · 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.