Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio
Yang Cao, Xiaoyu Li, Zhao Song, Chiwun Yang
Abstract
We consider the task of interpolating a $k$-sparse band–limited signal from a small collection of noisy time-domain samples. Exploiting a new analytic framework for hierarchical frequency decomposition that performs systematic noise cancellation, we give the first polynomial-time algorithm with a provable $(3+\sqrt{2}+\epsilon)$-approximation guarantee for continuous interpolation. Our method breaks the long-standing $C > 100$ barrier set by the best previous algorithms, sharply reducing the gap to optimal recovery and establishing a new state of the art for high-accuracy band–limited interpolation. We also give a refined ``shrinking-range'' variant that achieves a $(\sqrt{2}+\varepsilon+c)$-approximation on any sub-interval $(1-c)T$ for some $c \in (0,1)$, which gives even higher interpolation accuracy.
BibTeX
@inproceedings{
cao2025efficient,
title={Efficient \$k\$-Sparse Band{\textendash}Limited Interpolation with Improved Approximation Ratio},
author={Yang Cao and Xiaoyu Li and Zhao Song and Chiwun Yang},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=0xFgYI6oZr}
}