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

Yang Cao (University of Science and Technology of China) · Xiaoyu Li (University of New South Wales) · Zhao Song (University of California, Berkeley) · Chiwun Yang (Sun Yat-sen University)

analytic frameworkapproximation accuracyapproximation guaranteeband-limited signalcontinuous interpolationhierarchical frequency decompositionhigh-accuracyinterpolationk-sparsenoise cancellationoptimal recoverypolynomial-time algorithmshrinking-range variantstate of the artsub-interval

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.