Research map / Learning theory and algorithms / Matrix and tensor methods
Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first polynomial-time algorithm for k-sparse band-limited interpolation from noisy time-domain samples with a provable (3+√2+ε)-approximation guarantee.
Problem
Interpolating a k-sparse band-limited signal from a small set of noisy time-domain samples, where prior approximation guarantees were weaker.
Approach
A new analytic framework for hierarchical frequency decomposition that performs systematic noise cancellation, yielding a provable approximation ratio for continuous interpolation.
Key results
- First polynomial-time algorithm with a provable (3+√2+ε)-approximation guarantee for continuous k-sparse band-limited interpolation from noisy time-domain samples.
Experimental setup
Metrics: approximation ratio
Closest papers by meaning
- Deterministic Sparse Fourier Transform for Continuous Signals with Frequency Gap (ICML 2025 · similarity 0.86)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.84)
- A Fast and Provable Algorithm for Sparse Phase Retrieval (ICLR 2024 · similarity 0.83)
- Exponential Spectral Pursuit: An Effective Initialization Method for Sparse Phase Retrieval (ICML 2024 · similarity 0.81)
- Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing (NeurIPS 2026 · similarity 0.81)
- LSCD: Lomb--Scargle Conditioned Diffusion for Time series Imputation (ICML 2025 · similarity 0.81)
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.