6
$\begingroup$

I would like to calculate a long correlation function of length say, 1e6 points. I have a prior knowledge that the correlation peak will be in point k*1000. Is there an efficient way to apply this prior knowledge and perform a shorter calculation.

I don't want to calculate correlation by definition and implement a 1000 correlators. This solution is not sufficient. Batch algorithm (FFT) is always possible but it does not make use of the mentioned structure.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ I don't have time to write up a full answer, but you could implement the correlation using FFTs. If you know a set of equally-spaced points that you care about, what you really want to do is decimate the correlator output. This can be implemented efficiently in the frequency domain by folding and adding the frequency-domain result, allowing you to use a much smaller inverse FFT. This might help reduce your workload. $\endgroup$ – Jason R Apr 24 '15 at 12:12
  • $\begingroup$ You could probably use a variant of Goertzel algorithm ? $\endgroup$ – Ben Jul 8 '18 at 15:03
0
$\begingroup$

If you have a signal of length $N$ you can calculate auto correlation function of length $K=2N-1$.You'll need perform $N$ multiplications for each value of correlation function $r_{xx}$ or in other words you need one correlator. So you need as many correlators as your $r_{xx}$ function length is. If you want to find correlation in the lag $0$ use one correlator. You can can calculate correlation of any lag $i \in (-N+1...N-1)$ via one correlator with signal properly shifted by $i$ times. From the other side $FFT$ method allows you to find $N$ taps of cyclic auto correlation function via only one $FFT$ operation. So it is not optimal if you need only a few correlation values.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the response. Thats is the quistion. I am trying to use some kind of a hybrid algorithm that will use FFT but it will also exploit the structure mentioned in the question. $\endgroup$ – Vlad Sokolik Feb 23 '15 at 9:34
0
$\begingroup$

Reshape the series into 1000 series, each containing points 1000 apart, and the k*1000 autocorrelations of the original series will be the sum of the k autocorrelations from the new series.

You will presumably correlate via FFT so the efficiency gain goes as log(1000), not vast. However, the kind of knowledge that tells you that correlations peak at k*1000 might also allow you to obtain a sufficiently accurate estimate without doing the full calculation. For example, for smooth signals nearby contributions to the total correlation should be very similar and you might get a very good estimate by calculating only every tenth one.

Improve this answer
$\endgroup$
0
$\begingroup$

This reminds me of the days I was programming a correlation routine in C, working under MS DOS. All code and data had to fit in a memory space less than 640 kbytes. . .

If you want a correlation output over a small time window, while you have very long records, you can split up these records and use the overlap-add method to do correlation in the fourier domain. Once all the segments have been added to the fourier domain, you do an inverse fft to get your time domain response back.

The key phrase is "overlap-add".

Improve this answer
New contributor
BartD is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

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.