Fourier series decomposes a signal into its trigonometric
components, which vibrate at various frequencies. A B-term Fourier
approximation of a discrete signal s of length N consists of the B
largest Fourier coefficients. We give an algorithm for finding a
Fourier representation r of B terms for a given signal s, such that
the sum-square-error of the representation is within the factor (1 +
epsilon) of the best possible error. Our algorithm can access s by
reading its values on a sample set T in [0,N), chosen randomly from a
distribution of our choice, independent of s. That is, we sample
non-adaptively. The total time cost of the algorithm is polynomial in
B log(N)/epsilon which implies a similar bound for the number of
samples. This algorithm has implications for an algorithmic
uncertainty principle and applications to numerical analysis.
|