Near-optimal sparse Fourier representations via sampling

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

doi:10.1145/509907.509933

Near-optimal sparse Fourier representations via sampling

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

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Conference article › peer-review

201 Scopus citations

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 ∥A - R∥₂² is within the factor (1 + ε) of best possible ∥A - R∥_opt∥₂². 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 language	English (US)
Pages (from-to)	152-161
Number of pages	10
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/509907.509933
State	Published - 2002
Event	Proceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada Duration: May 19 2002 → May 21 2002

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/509907.509933

Cite this

@article{6dcd7335bc834cc9820a1c15f3c3c5f3,

title = "Near-optimal sparse Fourier representations via sampling",

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 ∥A - R∥22 is within the factor (1 + ε) of best possible ∥A - R∥opt∥22. 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.",

author = "Gilbert, {A. C.} and S. Guha and P. Indyk and S. Muthukrishnan and M. Strauss",

year = "2002",

doi = "10.1145/509907.509933",

language = "English (US)",

pages = "152--161",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 34th Annual ACM Symposium on Theory of Computing ; Conference date: 19-05-2002 Through 21-05-2002",

}

TY - JOUR

T1 - Near-optimal sparse Fourier representations via sampling

AU - Gilbert, A. C.

AU - Guha, S.

AU - Indyk, P.

AU - Muthukrishnan, S.

AU - Strauss, M.

PY - 2002

Y1 - 2002

N2 - 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∥opt∥22. 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.

AB - 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∥opt∥22. 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.

UR - http://www.scopus.com/inward/record.url?scp=0036041770&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036041770&partnerID=8YFLogxK

U2 - 10.1145/509907.509933

DO - 10.1145/509907.509933

M3 - Conference article

AN - SCOPUS:0036041770

SN - 0734-9025

SP - 152

EP - 161

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 34th Annual ACM Symposium on Theory of Computing

Y2 - 19 May 2002 through 21 May 2002

ER -

Near-optimal sparse Fourier representations via sampling

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this