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


    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

    ASJC Scopus subject areas

    • Software


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

    Cite this