AGCD: a robust periodicity analysis method based on approximate greatest common divisor

Abstract

Periodicity is one of the most common phenomena in the physical world. The problem of periodicity analysis (or period detection) is a research topic in several areas, such as signal processing and data mining. However, period detection is a very challenging problem, due to the sparsity and noisiness of observational datasets of periodic events. This paper focuses on the problem of period detection from sparse and noisy observational datasets. To solve the problem, a novel method based on the approximate greatest common divisor (AGCD) is proposed. The proposed method is robust to sparseness and noise, and is efficient. Moreover, unlike most existing methods, it does not need prior knowledge of the rough range of the period. To evaluate the accuracy and efficiency of the proposed method, comprehensive experiments on synthetic data are conducted. Experimental results show that our method can yield highly accurate results with small datasets, is more robust to sparseness and noise, and is less sensitive to the magnitude of period than compared methods.

Keywords

Periodicity analysis / Period detection / Sparsity / Noise / Approximate greatest common divisor (AGCD)

References

[1] Casey, S.D., Sadler, B.M., 1996. Modifications of the Euclidean algorithm for isolating periodicities from a sparse set of noisy measurements. IEEE Trans. Signal Process., 44(9): 2260-2272. [

[2] Clarkson, I.V.L., 2008. Approximate maximum-likelihood period estimation from sparse, noisy timing data. IEEE Trans. Signal Process., 56(5): 1779-1787. [

[3] Fogel, E., Gavish, M., 1988. Parameter estimation of quasiperiodic sequences. Proc. Int. Conf. on Acoustics, Speech, and Signal Processing, p.2348-2351. [

[4] Gray, D.A., Slocumb, J., Elton, S.D., 1994. Parameter estimation for periodic discrete event processes. Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, p.93-96. [

[5] Howgrave-Graham, N., 2001. Approximate integer common divisors. Proc. Int. Conf. on Cryptography and Lattices, p.51-66. [

[6] Huijse, P., Estevez, P.A., Zegers, P., , 2011. Period estimation in astronomical time series using slotted correntropy. IEEE Signal Process. Lett., 18(6): 371-374. [

[7] Huijse, P., Estevez, P.A., Protopapas, P., , 2012. An information theoretic algorithm for finding periodicities in stellar light curves. IEEE Trans. Signal Process., 60(10): 5135-5145. [

[8] Junier, I., Hérisson, J., Képès, F., 2010. Periodic pattern detection in sparse Boolean sequences. Algor. Mol. Biol., 5: 31.1-31.11. [

[9] Li, Z., Ding, B., Han, J., , 2010. Mining periodic behaviors for moving objects. Proc. 16th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.1099-1108. [

[10] Li, Z., Wang, J., Han, J., 2012. Mining event periodicity from incomplete observations. Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.444-452. [

[11] McKilliam, R., Clarkson, I.V.L., 2008. Maximum-likelihood period estimation from sparse, noisy timing data. Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, p.3697-3700. [

[12] Sadler, B.M., Casey, S.D., 1998. On periodic pulse interval analysis with outliers and missing observations. IEEE Trans. Signal Process., 46(11): 2990-3002. [

[13] Sidiropoulos, N.D., Swami, A., Sadler, B.M., 2005. Quasi-ML period estimation from incomplete timing data. IEEE Trans. Signal Process., 53(2): 733-739. [