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
ABSTRACT
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