# Approximating Fourier transform for range of output frequencies

(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?

• 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). – reuns May 8 '16 at 23:46
• My frequencies are linearly spaced, they just aren't integer multiples (harmonics) of the fundamental frequency. Can I still use this technique? – ridiculous_fish May 9 '16 at 3:33
• Did you look at the Constant Q transform? – Brannon Apr 14 '17 at 0:09