Near-optimal sparse Fourier representations via sampling

A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss

Research output: Contribution to journalConference articlepeer-review

201 Scopus citations


We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal A of length N, such that ∥A - R∥22 is within the factor (1 + ε) of best possible ∥A - R∥opt22. Our algorithm can access A by reading its values on a sample set T ⊆ (0, N), chosen randomly from a (non-product) distribution of our choice, independent of A. That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log(N) log(M)/ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.

Original languageEnglish (US)
Pages (from-to)152-161
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2002
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Near-optimal sparse Fourier representations via sampling'. Together they form a unique fingerprint.

Cite this