Consider the problem of computing the Fourier transform of a function, $f(x).$ $$ \hat{f}(k) = \int_{-\infty}^{\infty} dx~ f(x)~ e^{i k x} .$$

Suppose I want to approximate this transform by a discrete, truncated version, $$ \hat{F}_{\Delta, ~L}(k) = \sum_{n = -L}^L \Delta~ f(\Delta n)~ e^{i k \Delta n} .$$

I want the approximation to work with error $\epsilon$ in some interval $[0, k_{max}]$,

$$\sup_{k \in [0, k_{max}]} ~| \hat{f}(k) - \hat{F}_{\Delta, ~L}(k) | \leq \epsilon $$

What values of $\Delta$, $L$ should I choose to achieve this error. The answer will obviously depend on the properties of $\hat{f}(k)$, like how fast it decays. I have seen this done for specific functions but haven't seen any general rigorous result. Since this seems to be a problem with many practical applications it seems unlikely that no one has worked it out. Are there any rigorous results known for this general case ?


1 Answer 1


If you assume that $f \in L^1$, then approximations are not so terrible because $\hat{f}$ is uniformly continuous, with $\|\hat{f}\|_{\infty}\le \|f\|_{1}$. So, for $\epsilon > 0$, there exists $R > 0$ large enough such that $$ \left|\hat{f}(k)-\frac{1}{\sqrt{2\pi}}\int_{-R}^{R}f(x)e^{-ikx}dx\right| \\ \le \frac{1}{\sqrt{2\pi}}\int_{|u|\ge R}|f(u)|du < \frac{\epsilon}{2},\;\;\; k\in\mathbb{R}. $$ So the Fourier transform is uniformly approximated by the truncated Fourier series integral on $[-R,R]$. Then you can approximate the Fourier integral over $[-R,R]$ by a discrete sum $$ \hat{f}(k)\approx\sum_{n=-N}^{N-1}\frac{1}{\sqrt{2\pi}}\int_{Rn/N}^{R(n+1)/N}f(x)dxe^{-ikRn/N}. $$ I'm not sure if that's the type of approximation you want or not.

  • $\begingroup$ So you assume $f$ is continuous ($f(x)=e^{-x^2}(1 - 1_{x\in \mathbb{Q}})$) $\endgroup$
    – reuns
    Commented Jan 20, 2019 at 2:24
  • $\begingroup$ This is the kind of approximation I use. The question is how does $\epsilon$ depend on $R$ and $N$. $\endgroup$
    – biryani
    Commented Jan 21, 2019 at 10:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .