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 -