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

-
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

## 2 Answers

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.

-
Thanks for the answer. I'm asking because I'm studying compressed sensing and want to compare it with traditional discrete Fourier analysis. I understand Shannon's sampling theorem says that the sampling rate must be at least 1 over the highest frequency. But it doesn't say HOW MANY samples or the length of the sample required... how do you get 800? – rmp251 Aug 2 '12 at 17:39
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
Thank you Thomas – rmp251 Aug 2 '12 at 23: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

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.

-