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.