A Sublinear Algorithm of Sparse Fourier Transform for Nonequispaced Data
Abstract
We present a sublinear randomized algorithm to compute a sparse Fourier transform for nonequispaced data. We address the situation where a signal S is known to consist of N equispaced samples, of which only L<N are available. This includes the case of "equispaced data with gaps"; if the ratio p=L/N is smaller than 1, the available data are typically non-equispaced samples, with little or no visible trace of the equispacing the full set of N 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 smaller or equal (1 + epsilon)||S-R_{opt}^B||^2, where R_{opt}^B is the optimal B-term Fourier representation of signal S. The sublinear poly(log L) time is compared to the superlinear O(NlogN+L) time requirement of the present best know Inverse Nonequispaced Fast Fourier Transform (INFFT) algorithms, in the sense of weighted norm with the number of dimensions delta, smoothness parameter B. 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 12, 2005
- Accession Number
- ADA459105
Entities
People
- Jing Zhou
Organizations
- Princeton University