2
$\begingroup$

Example,

T = array([0,1,1,1,0,0,1,0,1,1,1,0,0,1,1,1,1,1,0,0,1,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0,1,1,1,0,0,1])

( T is almost a repeat of the array([0,1,1,1,0,0,1]) six times )

I say almost because it is not perfect. I have hundreds of thousands of binary-valued time series with lengths in the 500-50,000 range. I'd like to know the fastest way to detect periodicities within in the data. The periodicities can be local, for example, consistent in the first quarter of the signal but not the rest.

$\endgroup$

1 Answer 1

1
$\begingroup$

I assume you don't know the periodicity in advance.

TLDR: Autocovariance. Details and fastest implementation may depend on your exact problem.

Other than autocovariance, which has a basic definition but is usually implemented using Fast Fourier Transform (FFT) for efficiency; closely related search words are from the FFT world: periodogram and spectral density.

Such questions arise in signal processing, and speed of computation is a major issue there. If you are as serious about speed as you sound, ask at the "Signal Processing" SE.

With weak signals, there is a trade-off:

Losely speaking, there are at least two ways for the "signal" (repetitions) to hide in the "noise" (random or non-periodic data):

  • being very imperfect, and
  • repeating only once or twice, not many times over.

The best measure will be some kind of trade-off between detecting short repetitions, detecting imperfect repetitions, and avoiding false positives. You tune the autocovariance measure's locality by using on segments ("windows") of your sequence, possibly with some overlap. The best window size is a compromise.

For "strong" signals the trade-off will not be painful - very long repetitions, known period lengths, or very low propabilities of "imperfections".

"The fastest" implementation way depends on that tradeoff and on your data. Independent of the implementation, autocovariance will be a good measure of "repeatedness".

If all periods are short, and the input is binary, run-times will be faster with some one-pass and bit-fiddling algorithm. "Local" repeatedness can then be some decaying (exponentially-weightened) autocovariance/approximation thereof. It's probably not worth the hassle though!

Autocovariance coefficient

This is a correlation coefficients between your array and the same array. For a given candidate period p, its value is basically $\sum_k T_k\cdot T_{k+p}$, but previous normalization of T.

The autocovariance coefficient, if normalized like a Pearson coefficient, is a number between -1 and +1, has a value of 1 for p=0 and for perfect periods, is close to 0 when p is not a period.

For example, here's the autocovariance coefficient of your example array for different values of p>1 - blue line with dots is you data, orange line without markers is a random sequence of zeroes and ones of the same length:

plot: example autocovariance

The period p=7 is quite obvious from the blue line, the autocovariance being close to .8 at p=7, p=14, p=21, but around zero otherwise. With more data (larger window size), random sequences will have autocovariances much closer to zero. But locality will be less exact - this is the trade-off.

Autocovariance / autocorrelation has efficient implementations. It's also "fast" in terms of developer time, you'll find it in your favourite library and it's readily understood by other devs. What's more, it has general applications than just binary sequences.

For long sequences and somewhat long, unknown periods, the first step in a fast algorithm will be a Fast Fourier Transform whose result can then be re-used.

To find "the fastest" way, you'll have to benchmark with your data.

$\endgroup$

Your Answer

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

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