Full Text:   <941>

Summary:  <443>

CLC number: TP301.6

On-line Access: 2015-06-04

Received: 2014-10-09

Revision Accepted: 2015-03-17

Crosschecked: 2015-05-15

Cited: 1

Clicked: 2009

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Juan Yu

http://orcid.org/0000-0001-9562-1325

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2015 Vol.16 No.6 P.466-473

http://doi.org/10.1631/FITEE.1400345


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


Author(s):  Juan Yu, Pei-zhong Lu

Affiliation(s):  School of Computer Science and Technology, Fudan University, Shanghai 200433, China

Corresponding email(s):   juanyu10@fudan.edu.cn, pzlu@fudan.edu.cn

Key Words:  Periodicity analysis, Period detection, Sparsity, Noise, Approximate greatest common divisor (AGCD)


Juan Yu, Pei-zhong Lu. AGCD: a robust periodicity analysis method based on approximate greatest common divisor[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(6): 466-473.

@article{title="AGCD: a robust periodicity analysis method based on approximate greatest common divisor",
author="Juan Yu, Pei-zhong Lu",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="16",
number="6",
pages="466-473",
year="2015",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1400345"
}

%0 Journal Article
%T AGCD: a robust periodicity analysis method based on approximate greatest common divisor
%A Juan Yu
%A Pei-zhong Lu
%J Frontiers of Information Technology & Electronic Engineering
%V 16
%N 6
%P 466-473
%@ 2095-9184
%D 2015
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1400345

TY - JOUR
T1 - AGCD: a robust periodicity analysis method based on approximate greatest common divisor
A1 - Juan Yu
A1 - Pei-zhong Lu
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 16
IS - 6
SP - 466
EP - 473
%@ 2095-9184
Y1 - 2015
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1400345


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.

The article presents a method to extract the greatest common divisor in data containing sparse, noisy, and missing points. The proposed method is remarkably simple (and hence elegant), and the results clearly demonstrate the efficiency of the proposed algorithm.

AGCD:一种基于最大公因子逼近的鲁棒周期分析方法

目的:设计较现有方法鲁棒性更佳、效率更高的周期分析方法,从稀疏且含有噪声的周期事件观测数据中估算周期。
创新点:本文首次将最大公因子逼近算法应用于周期估算问题。该算法在处理稀疏且含有噪声的数据方面具有效率高、性能稳定、鲁棒性好的特点。
方法:首先,确定观测数据的噪声空间。本文根据观测数据自适应获取噪声上下限。然后,对观测数据进行预处理,消除其中包含的未知相位参数,并对预处理后的数据逐对以噪声穷举方式搜索所有可能的最大公因子,即采用公因子逼近的方法搜索候选周期,同时统计这些候选周期在整个搜索过程中出现的频率。搜索完成后,根据候选周期出现频率估算周期值,即选择出现频率最高的候选周期为估算周期。最后,采用仿真数据验证AGCD方法在处理稀疏且含有噪声的观测数据方面的鲁棒性和高效性。
结论:(1)AGCD算法效率高,因其以穷举搜索噪声空间方式估算周期。而现有方法是以穷举周期的方式估算周期,噪声空间相比周期的取值空间小很多。所以,AGCD方法在效率上有很大提升。(2)AGCD能以更少的观测数据获得与其他方法近似或更高的准确率。(3)AGCD性能(准确性和效率)较其他方法更加稳定且受周期值影响更小。(4)AGCD方法无需利用有关周期取值区间的先验知识,相比于其他方法适用性更强。

关键词:周期性分析;周期估算;稀疏;噪声;AGCD

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[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 quasi-periodic 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., et al., 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., et al., 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., et al., 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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE