A 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 best possible error. Our algorithm can access s by reading its values on a sample set T in [0,N), chosen randomly from a (non-product) 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) log(M) / epsilon (where M is a standard input precision parameter), which implies a similar bound for the number of samples. This algorithm has implications for an algorithmic discrete uncertainty principle and applications to numerical analysis.