Accession Number:

ADA459105

Title:

A Sublinear Algorithm of Sparse Fourier Transform for Nonequispaced Data

Descriptive Note:

Journal article preprint

Corporate Author:

PRINCETON UNIV NJ PROGRAM IN APPLIED AND COMPUTATIONAL MATHEMATICS

Personal Author(s):

Report Date:

2005-08-12

Pagination or Media Count:

28.0

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 LN are available. This includes the case of equispaced data with gaps if the ratio pLN 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 polyB,logL, log p, log1delta, epsilon-1, such that S-R2 smaller or equal 1 epsilonS-RoptB2, where RoptB is the optimal B-term Fourier representation of signal S. The sublinear polylog L time is compared to the superlinear ONlogNL 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.

Subject Categories:

  • Theoretical Mathematics
  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE