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(xj) under the assumption that f belongs to a shift-invariant space $V(\varphi)$. If the generator $\varphi$ 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(S2J) operations, where J is the number of samples and S is the support length of the generator $\varphi$. Further optimization can be achieved by means of data segmentation. Ample numerical simulation is provided.