3
$\begingroup$

The aliasing formula for the discrete Fourier transform (DFT) can be written succinctly as $$G_k^N=\sum_{l=-\infty}^\infty G_{k+Nl}$$ where $G_k^N:=\frac{1}{N}\sum_{i=0}^{N-1}g(\frac{iT}{N})\exp[-j2\pi\frac{ki}{N}]$ for a $T$-periodic function $g$ with absolutely convergent Fourier series and Fourier coefficients $G_k:=\frac{1}{T}\int_0^Tg(\tau)\exp[-j2\pi\frac{k}{T}\tau]d\tau$.

Potts, D. and Steidl, G. Fast summation at nonequispaced knots by NFFTs. SIAM J. Sci. Comput. 24, 2013-2037, 2003 (can be downloaded from here) for example state it somewhat less succinct as Theorem 2.1 (Aliasing formula) without proof as $$\hat{g}_k=c_k(g)+\sum_{\begin{array}{c}r\in\mathbb Z\\r\neq 0\end{array}} c_{k+rn}(g)$$ where the Fourier coefficients of $g$ have been named $c_k(g)$ instead of $G_k$ and $\hat{g}_k$ was described as an approximation of $c_k(g)$ using the trapezoidal quadrature rule instead of calling it the DFT $G_k^N$.

The aliasing formula is easy to prove (just plug the Fourier series for $g$ into the formula for $G_k^N$), but I never saw any reference explicitly proving it. In fact, I even had trouble finding a reference (like the one given above) stating the aliasing formula as an explicit formula, instead of just describing it in informal words when explaining the need for a low-pass filter to avoid aliasing during sampling.

One indication that I am not the only one having problems finding an explicit (textbook) reference for this formula is the statement of the formula in Theorem 2.8 of the thesis by S. Kunis Nonequispaced FFT - Generalisation and Inversion from 2006 (can be downloaded from here) without a reference to a source, while many other theorems and lemmas in the same chapter have explicit references to a source.

The strange thing about the aliasing formula is that it is not really difficult (neither to state nor to prove). Hence I wonder why I can't find it in textbooks, and whether it is really a folklore result (whatever that means)? After all, it is used in an informal sense in some (engineering) textbooks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.