(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.
No takes yet. Share an insight, caveat, or question.
Gilbert et al. (2002) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: