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.
Best Answer
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.