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 + √ 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 ( √ 2 + ε + c)-approximation on any sub-interval (1c)T for some c ∈ (0, 1), which gives even higher interpolation accuracy.