3

I have two signals that I want to synchronize. I could achieve this by doing a cross-correlation using the ccf function and finding the lag time at which the ccf is maximum. This is a similar approach:

How can I align/synchronize two signals?

For efficiency reasons, I want to use a Fast Fourier Transform. From what I read here: Cross-correlation and convolution, I concluded that what I want can be achieved simply by:

> convolve(vector1, vector2)

Since convolve already uses the FFT, and I got the same result as using ccf, I assumed it was right. Could someone confirm if this approach is correct?

Community
  • 1
Paulo MiraMor
  • 165
  • 8
  • 2
    Although phrased in terms of `R`, I think this question may be more about the concepts than the code. More specifically, understanding the concepts that the code is instantiating. – gung - Reinstate Monica Dec 31 '14 at 21:36

1 Answers1

2

Sorta.

Cross-correlation and convolution are closely linked. Cross-correlation of $f(t)$ and $g(t)$ is the same as the convolution of $\bar{f}(-t)$ and $g(t)$, where $\bar{f}$ is the complex conjugate of $f$.

For certain types of $f$s, called Hermitian functions, cross correlation and convolution and convolution would produce exactly the same results. Thus, you're correct that convolution and cross-correlation can sometimes be interchanged. Even if your function is not Hermitian, you might be able to get away with using either method, depending on your goal.

However, neither cross-correlation nor convolution necessarily involve a Fourier transform. Both transforms are defined has happening purely in the time domain, and a naive implementation would just operate there.

That said, the Convolution Theorem says that convolution in one domain is equivalent to element-wise multiplication in the other. That is $$\mathscr{F}(f\ast g) = \mathscr{F}(f) \cdot \mathscr{F}(g)$$ where $\mathscr{F}$ is the Fourier transform$^1$. With a little bit of rearrangement$, one can instead write

$$f \ast g = \mathscr{F}^{-1}\big(\mathscr{F}(f) \cdot \mathscr{F}(g)\big)$$ uses the Fourier transform to compute convolution. Similar logic lets one compute the cross correlation in the same way: $$ f \star g = \mathscr{F}^{-1} \bigg( \overline{\mathscr{F}(f)} \cdot \mathscr{F}(g)\bigg)$$

This may seem like a round-about way of performing convolution, but it can often be more efficient. Convolving two sequences of length $n$ in the time domain requires $O\bigl(n^2\bigr)$ time. However, the Fourier transform can be performed in $O\bigl(n \log n\bigr)$ time$^2$ each while the pointwise multiplication takes $O(n)$ time. If your sequences are large and of approximately equal size, this approach can be faster.

1. You may need to correct for a normalizing factor of $2\pi$ or its square root, depending on how you defined the Fourier transform.

2.In addition to the asymptotic speed-up, many FFT implementations are incredibly well-tuned, so this works both in theory and in practice! FFTW is a good place to start if you're curious about that.

Matt Krause
  • 19,089
  • 3
  • 60
  • 101
  • not using the FFT achieves the same result, however the performance using the FFT is incredibly better. Is it possible to do the same using `ccf` and `fft` composed (or something analogous)? Thanks! – Paulo MiraMor Jan 02 '15 at 01:44
  • Also, shoundn't the last equation be convolution(f∗g)=F^-1*(Conj(F(f))⋅F(g)), where Conj(F(f)) represents the complex conjugate of the fourier transform of function `f`? Thanks again. – Paulo MiraMor Jan 02 '15 at 02:02
  • To answer your question directly, yes. If $f$ is Hermitian, then just use R's convolve(). Otherwise, transform $f$ by finding its complex conjugate and time-reversing it, and pass it to convolve(). – Matt Krause Jan 02 '15 at 05:07
  • The complex conjugate (and time reversal) are needed for computing cross-correlation, but not convolution. – Matt Krause Jan 02 '15 at 05:10