Efficient $k$-Sparse Band–Limited Interpolation with Improved Approximation Ratio

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}+ϵ)$-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}+\epsilon +c)$-approximation on any sub-interval $(1-c)T$ for some $c\in (0,1)$, which gives even higher interpolation accuracy.