1

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.

jettero
  • 113

1 Answers1

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.

learner
  • 382
  • I think I saw something like this on Wolfram at some point but didn't realize it was answering my questions. I wish I could find a convenient list of Fourier properties. – jettero Mar 10 '17 at 15:38
  • This one is rather complete: http://fourier.eng.hmc.edu/e101/lectures/handout3/node2.html – learner Mar 10 '17 at 15:45
  • Anyway, if you are familiar with basic Calculus, you should be capable of applying the Fourier transform to the definition of $g(t)$ and you'll eventually get the product of $\tilde{f}(\omega)$ with its conjugate, which equals $|\tilde{f}(\omega)|^2$ (because the product of a complex number with its conjugate is the squared magnitude of that number). – learner Mar 10 '17 at 15:48
  • I was familiar with basic calculus 20 years ago … I wouldn't have thought of it being all that basic, but apparently the non-fft definition of a Fourier transform is a lot more simple than the cool-turkey. I hadn't realized this. – jettero Mar 10 '17 at 17:42
  • The FFT is simply an algorithm that implements the discrete Fourier transform. The Fourier transform I used here is the continuous one. The continuous Fourier transform of a signal is closely related with the discrete Fourier transform of the sampled version of that same signal. Moreover, their properties are analogous. – learner Mar 11 '17 at 19:15