# How many Fourier coefficients are enough ( in discrete fourier transform)

Probably there's a similar question, but I could't find it through all questions about FT

As the title says, how many Fourier coefficients are enough, to be able to "resume" the original function, using inverse discrete Fourier transform?

For example, in the definition from Wikipedia, it looks like we need N coefficients, where N is the number of given points from the original discrete function. I also noticed, that for FFT (fast Fourier transform), the number of calculated coefficients is the same as the number of given points.

Is this always like this? Or we may have fewer coefficients? Or more? And is there a way to estimate this number of necessary coefficients?

I ran some test with randomly generated "control points" of a discrete function and applied DFT and IDFT (in this order) and all control points were recreated.

-
The FFT is only an algorithm for computing efficiently the DTF en.wikipedia.org/wiki/Discrete_Fourier_transform –  leonbloy Jul 5 '12 at 21:05

The discrete Fourier transform of a signal $\{x_j\}$ is given by a linear combination of the $x_j$'s with some factors of the form $e^{j \pi i /N}$ or something similar. This can be shortly written as

$$x_k=A_{ki} x_i$$

where $A_{ki}$ is the transformation matrix. It is invertible (this is why you also have the inverse transform).

Having understood that, you see that the Fourier transform is nothing more than a change of basis in the space $\mathbb{C}^N$ where $N$ is the signal length. Since any basis will be of size $N$, you see that in order to fully describe your signal you always need exactly $N$ complex numbers (or $2N$ real ones).

Therefore, if your signal is complex you will always need all the coefficients of the DFT. If your signal is purely real then the coefficients in the DFT are related by $x_k=x_{N-k}^*$ and you need only half of them.

-
Thanks, I think I got it. Please, correct me if I'm wrong: so, if I have a sequence of N points ( N complex numbres) $\{ (x_1,y_1), (x_2,y_2) \cdots\}$ , to be able to reconstruct (synthesize) the signal from its Fourier coefficients, I need N coefficients, right? –  Kiril Kirov Jul 6 '12 at 9:23
Exactly (assuming you mean $x_i$ and $y_i$ are real and not complex). –  yohBS Jul 6 '12 at 15:19
Yes, they are real. Thanks a lot! +1 and accepted :) –  Kiril Kirov Jul 6 '12 at 17:17

The number of coefficients needed to reconstitute a given signal depends on signal itself, and on how you're sampling it.

Here's an intuitive answer. The discrete Fourier transform tries to represent your signal as a sum of frequencies, from $0$ frequency (or DC - a flat response), up to some higher frequency that depends on the granularity of your sampling. When in your simulations you increase the sampling rate of your signal (make your sample points closer together), you necessarily increase the frequency range that your signal can represent, and hence you will have more Fourier coefficients for higher frequencies.

However, you might make your signal very slow (have only low frequencies). In this case, you won't need all the Fourier coefficients to reproduce your signal (try making your test signal a slow sign wave, for instance). On the other hand, if you make your signal very fast (have lots of high frequencies), you won't be able to drop coefficients and still reproduce your signal. There is a limit on how "fast" your signal can be and still be reproduced at a given sampling rate. It's called the Nyquist Rate. For certain very special signals, you might be able to do better than the Nyquist rate. This is related to the field of compressed sensing.

-