# 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?

Thanks!

-
To prevent aliasing, you need to know, a priori, an upper bound on the frequency content. No matter what sampling frequency you take, you can always find a sinusoid in the 'null space' of the sampler. – copper.hat Aug 2 '12 at 5:57
What information do you have about the signal? Frequencies? – copper.hat Aug 2 '12 at 6:55
Suppose you have a tight upper bound on the frequencies. But all you can do is sample the function f at times t. – rmp251 Aug 2 '12 at 17:41
The Nyquist criterion gives a sufficient condition, which is to take the sampling frequency to be greater than twice the maximum signal frequency. – copper.hat Aug 2 '12 at 17:50
OK, but how many samples? – rmp251 Aug 2 '12 at 18:25

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.
I assumed that it is known that the signal has period $2\pi$. I further assumed that it is known that uniform sampling with a spacing smaller than $\frac{\pi}{400}$ is sufficient. – Thomas Klimpel Aug 2 '12 at 21:32
The 800 came from twice the frequency of the fastest signal (which has frequency $\frac{400}{2 \pi}$). You need to sample faster than twice this and 801 is the smallest integer greater than 800. Hence sample at the points $k \frac{2 \pi}{801}$, with $k=0,...,800$. – copper.hat Aug 2 '12 at 23:34
In your case, you should get $\hat{f}_1 = \hat{f}_2 = \hat{f}_{400} = \frac{1}{2 i}$, $\hat{f}_{-k} = \overline{\hat{f}_{k}}$, and the rest 0. (Assuming I haven't goofed.) – copper.hat Aug 2 '12 at 23:50