DIMACS TR: 2004-49

Improved Time Bounds for Near-Optimal Sparse Fourier Representations



Authors: Anna C. Gilbert, S. Muthukrishnan, and Martin J. Strauss

ABSTRACT
We study the problem of finding a Fourier representation R of B terms for a given discrete signal A of length N. The Fast Fourier Transform (FFT) can find the optimal N-term representation in O(N*log(N)) time, but our goal is to get sublinear algorithms when B Suppose ||A||<=M||A-Ropt||, where Ropt is the optimal output. The previously best known algorithms output R such that ||A-R||<=(1+\epsilon)||A-Ropt|| with high probability in time poly(B,log(N),log(M),1/epsilon). Although this is sublinear in the input size, the dominating quantity is the polynomial factor in B which, for published algorithms, is greater than the bottleneck at B^2 that we identify below. Our experience with these algorithms shows that this is serious limitation in theory and in practice. Our algorithm beats this B^2 bottleneck.

Our main result is a significantly improved algorithm for this problem and the d-dimensional analog. Our algorithm outputs an R with the same approximation guarantees but it runs in time B*poly(d,log(N),log(M),1/\epsilon).

We need two crucial ideas to achieve this bound: bulk sampling and estimation for multipoint polynomial evaluation using an unevenly-spaced Fourier tranform, and construction and use of arithmetic-progression independent random variables.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-49.ps.gz

DIMACS Home Page