Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
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".
What you want is essentially every 1000th output of a full correlator/convolution?
As the convolution is essentially an inner-product between a fixed weight vector and a delayline of input samples stepped one sample at a time, can’t you just do that inner product stepped 1000 samples at a time?
