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.
|Original language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|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
ASJC Scopus subject areas