Determining sparse frequency distribution via discrete Fourier transform Consider the function $$f(t) = 2 \sin(t)+\sin(2t)+25 \sin(400t)$$
(for example).
In this case, how many samples of this function would I have to take, and at what sampling frequency, to determine the three frequencies it is composed of? And, how exactly would I identify those frequencies from the Fourier coefficients?
This is not a homework problem by the way, just something that I'm confused about. Please help!
Thanks!
 A: Are you asking this because you heared about "The faster-than-fast Fourier transform"? The corresponding "Nearly Optimal Sparse Fourier Transform" paper shows that you need more than $O(k \log (n/k)/\log \log n)$ and less than $O(k \log n)$ samples, where $k$ is the number of non-zero Fourier coefficients and $n$ is the length of the signal. Obviously $k=3$ for your case, because you have three different frequencies. By Shannon's sampling theorem, we get that any $n$ with $n>800$ will be fine, because your signal has period $2\pi$ and the largest occurring frequency is $\frac{400}{2\pi}$. So I guess you will need approximatively $c\cdot30$ samples (if you use $c$ and the sampling strategy from that paper, and take the knowledge about the period and the largest possible frequency of the function as given a priory). Without reference to that paper, my answer would be that you need $801$ samples.
A: When you have infinite samples, the three frequency components can be determined exactly if the sampling rate is higher than Nyquist frequency, which is twice the maximum frequency component. However, with finite samples, you can never exactly determine the energy of the frequency components in the original continuous signal. This is called spectral leakage.
