1
$\begingroup$

I have $N$ signals, each of length $\tau$, with $N\ll \tau$, eg. $\tau=10^8$ samples and $N=100$. I want the $r=10$ first components of all pairwise cross-correlation for the $N$ signals.

The naive way to do this, is to for every signal, take the dot product between the signal, and the $r$ shifted versions of all the other signals. The problem is that this has time complexity $O(N^2 \ \tau \ r)$.

Is there any way of doing this more efficiently? It is ok if the cross-correlation is a bit lossy.

Some ideas: Use some variation of wavelet transforms, compressed sensing or FFT.

Improve this question
$\endgroup$
1
  • $\begingroup$ Each cross correlation would $2\tau-1$ samples long. Do you need the entire lag range or can you narrow it down to a "useful" length $\endgroup$
    – Hilmar
    Nov 29, 2022 at 4:33

1 Answer 1

Reset to default
1
$\begingroup$

Since $r$ is so small, I think the cheapest method will be the "naive way". If $r \approx \tau$ then cross-correlation using FFT would be cheaper.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Given that the difference between $r$ and $\tau$ was bigger, but the difference between $N$ and $\tau$ was still big: How could one implement it? FFT and slightly modified convolution is one way. Are there any others that could work well? $\endgroup$
    – wavelet_surfer
    Nov 28, 2022 at 21:46
  • $\begingroup$ I don't think there is anything you can do to reduce the $O(N^2)$ complexity. There are $\frac{N(N-1)}{2}$ possible pairings of signals. For each pairing, you need $r$ points of the cross-correlation function. If you're not using an FFT for the cross-correlation, then there are $\tau$ multiply-accumulate (MAC) instructions for each of the $r$ offset values. The number of MAC operations is $\frac{N(N-1)}{2} \times r \times \tau$. $\endgroup$
    – robert bristow-johnson
    Nov 28, 2022 at 22:36
  • $\begingroup$ The problem is not really the $O(N^2)$, but that it is multiplied with $\tau$. If one is able to decrease $\tau$, that would be helpful though, For instance by doing some operation $O(N \tau)$, and then $O(N^2 \tau_2)$ $\endgroup$
    – wavelet_surfer
    Nov 29, 2022 at 17:40
  • $\begingroup$ What I do in the auto-correlation that I do for real-time pitch detection is to sample (or "select") the $x[n]$ and $x[n+k]$ (where $k$ is the lag). But instead of selecting every, say, 10th sample (so you skip over 9), make the spacing of your selected samples more random in its nature and appearance. Maybe use spacing randomly selected from a list of prime numbers. That way no single frequency will be missed as it would be if the spacings between selected samples were equal. $\endgroup$
    – robert bristow-johnson
    Nov 29, 2022 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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