3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – gung Dec 31 '14 at 21:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Paulo MiraMor Jan 2 '15 at 1:44
  • $\begingroup$ 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. $\endgroup$ – Paulo MiraMor Jan 2 '15 at 2:02
  • $\begingroup$ 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(). $\endgroup$ – Matt Krause Jan 2 '15 at 5:07
  • $\begingroup$ The complex conjugate (and time reversal) are needed for computing cross-correlation, but not convolution. $\endgroup$ – Matt Krause Jan 2 '15 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.