New algorithms for band-limited interpolation and extrapolation: A synthetic view

We propose a classification of several algorithms for solving the discrete-discrete band-limited interpolation and extrapolation problems. The classification is based on the dimension of certain underlying vector spaces, and distinguishes between time-domain and frequency-domain methods. This perspective allows a synthetic view of the problem, clarifies the connections between some of the existing algorithms, and establishes the existence of "missing variants". We introduce the missing variants, and analyze the relative performance of the complete set of methods. It is shown that no method can be "best overall". Instead, there are classes of problems for which one set of methods clearly outperforms the others. These classes are characterized, and the main issues that arise when designing efficient algorithms for the solution of a specific problem are discussed.