DIMACS TR: 2001-44

Near-Optimal Sparse Fourier Representations via Sampling

Authors: Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan and Martin J. Strauss


We give an algorithm for finding a Fourier representation r of B terms for a given discrete signal a of length N, such that the sum-square error is within the factor (1+ epsilon) of best possible sum-square error. Our algorithm can access the signal a by reading its values on a sample set T, chosen randomly from a (non-product) distribution of our choice, independent of the signal a. That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log(N) log(M)/epsilon (where M is a standard input precision parameter), which implies a similar bound for the number of samples.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-44.ps.gz
DIMACS Home Page