1
$\begingroup$

(This may be an elementary question, I am new to Fourier analysis.)

I am working on a visualization tool. I have a real function $f(x)$, given by N samples on some interval, and vanishing outside that interval. I want to visualize (plot) its Fourier transform:

$$ \hat{f}(\xi) = \int_{-\infty}^{\infty} f(x) e ^{-2 \pi i x \xi} dx$$

A naïve approach is to approximate this via a Riemann sum. By adjusting the distance between successive samples of $\xi$, I can get a "nice" result, e.g. a Gaussian is visibly transformed into another Gaussian. However the computation is too slow, because it's O(N2).

I tried using the discrete Fourier Transform, with ideas of using a FFT:

$$ X_k = \sum\limits_{n=0}^{N-1} x_n e^{-2{\pi}ikn/N}$$

the computed frequencies are multiples of the fundamental frequency, so if I have 1024 samples, I get frequencies 1,2,3,...1023. This is too high: a Gaussian is transformed into a vertical spike! I want the output frequencies to be in a range more like .01,.02,.03...10

My question is, how can I efficiently approximate the Fourier transform for a range of output frequencies which I specify, different from the DFT output frequencies?

$\endgroup$
  • $\begingroup$ in fact, the (slightly modified) FFT can compute in $\mathcal{O}(N \ln N)$ the values of $\displaystyle \sum_{n=0}^{N-1} x_n e^{-2 i \pi k \xi_0}, k \in \{0, \ldots, N-1\}$, but when you want to output non linearly spaced frequencies, you can't use the FFT anymore. you have some weird algorithms for polynomially spaced frequencies, but I don't think you'd like to know those (personally I don't). $\endgroup$ – reuns May 8 '16 at 23:46
  • $\begingroup$ My frequencies are linearly spaced, they just aren't integer multiples (harmonics) of the fundamental frequency. Can I still use this technique? $\endgroup$ – ridiculous_fish May 9 '16 at 3:33
  • $\begingroup$ Did you look at the Constant Q transform? $\endgroup$ – Brannon Apr 14 '17 at 0:09

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.