Fast local reconstruction methods for nonuniform sampling in shift-invariant spaces

We present a new method for the fast reconstruction of a function f from its samples f(x(j)) under the assumption that f belongs to a shift-invariant space V (phi). If the generator phi has compact support, then the reconstruction is local, quite in contrast to methods based on band-limited functions. Using frame theoretic arguments, we show that the matrix of the corresponding linear system of equations is a positive-definite banded matrix. This special structure makes possible the fast local reconstruction algorithm in O(S(2)J) operations, where J is the number of samples and S is the support length of the generator phi. Further optimization can be achieved by means of data segmentation. Ample numerical simulation is provided.