  We present a sublinear randomized algorithm to compute a sparse Fourier
transform for nonequispaced data. Suppose a signal S is known to consist of N
equispaced samples, of which only L<N are available. If the ratio p=L/N is not
close to 1, the available data are typically non-equispaced samples. Then our
algorithm reconstructs a near-optimal B-term representation R with high
probability 1-delta, in time and space poly(B,log(L),log p, log(1/delta),
epsilon^{-1}, such that ||S-R||^2 < (1+epsilon) ||S-R_{opt}^B||^2, where
R_{opt}^B is the optimal B-term Fourier representation of signal S. The
sublinear poly(logL) time is compared to the superlinear O(Nlog N+L) time
requirement of the present best known Inverse Nonequispaced Fast Fourier
Transform (INFFT) algorithms. Numerical experiments support the advantage in
speed of our algorithm over other methods for sparse signals: it already
outperforms INFFT for large but realistic size N and works well even in the
situation of a large percentage of missing data and in the presence of noise.
