Nearly Optimal Sparse Fourier Transform

Details Nearly Optimal Sparse Fourier Transform Nearly Optimal Sparse Fourier Transform

2012-01-12

arxiv.org/abs/1201.2501v2

Computer Science

Data Structures and Algorithms

28 pages, appearing at STOC 2012

Scientific paper

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: * An O(k log n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and * An O(k log n log(n/k))-time randomized algorithm for general input signals. Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). They are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = n^{\Omega(1)}. We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least \Omega(k log(n/k)/ log log n) signal samples, even if it is allowed to perform adaptive sampling.

Affiliated with

Also associated with

No associations

Rating

Nearly Optimal Sparse Fourier Transform does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nearly Optimal Sparse Fourier Transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nearly Optimal Sparse Fourier Transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-151801