FFT Autocorrelation

Question

I'm particularly fond of a new smoothing thing "ASAP" under Stanford Future Data [Rong/Bailis]. I've been playing around with it for a couple days. I'm no stranger to Fourier transforms and frequency domains, but the math tends to be over my head. I rarely grasp what frequency domain really means.

In the algorithm, they do something like:

  FR(f) = FFT(data)
  S(f)  = [ x.real ** 2 + x.imag ** 2 for x in FR ]
  R(t)  = inverse_fft( S )

What is x.real**2 + x.imag**2 (the real part squared plus the imaginary part squared)? I would think the square root of it is like the length of the vector, but they don't take the square root.

They then say the correlations are [ x/R[0] for x in R ]. Why is the inverse FFT of the length things giving us a correlation? (And a correlation to what?)

I tried to google this, and use wolfram and wikipedia, but I'm just not wrapping my mind around it. It may be I'm not even sure what question to ask. But the two questions above are what I'm trying to figure out.

Answer 1

Suppose your data corresponds to the (discretized) function $f(t)$. The autocorrelation $g$ of a (real-valued) signal $f$ defined in an interval $[a,b]$ is usually defined as:

$g(t)=\int_a^b f(\tau)f(\tau+t)d\tau$,

i.e. it is the convolution of $f(t)$ with $f(-t)$.

If you take a look at some basic Fourier transform properties, you will figure out that the Fourier transform of $g(t)$ and $f(t)$, respectively $\tilde{g}(\omega)$ and $\tilde{f}(\omega)$, are related by:

$\tilde{g}(\omega)=|\tilde{f}(\omega)|^2$.

Therefore, instead of computing the autocorrelation $g(t)$ explicitly (using the integral above), you may obtain $g(t)$ by first computing the Fourier transform of $f(t)$, here denoted by $\tilde{f}(\omega)$, then obtaining $\tilde{g}(\omega)$ from the formula above and finally obtaining $g(t)$ by the inverse of the Fourier transform.

Because the FFT algorithm is much more efficient than the computation of convolutions, this approach turns out to be advantageous when compared to using the explicit definition of autocorrelation.