Near-optimal sparse fourier representations via sampling

(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N, such that \|-\|₂² is within the factor (1 +ε) of best possible \|-_\|₂². 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.