Minimum Data Length for Integer Period Estimation

Abstract

Detecting periodicity in a short sequence is an important problem, with many applications across science and engineering. Several efficient algorithms have been proposed for this over the years. There is a wide choice available today in terms of the trade-off between algorithmic complexity and estimation accuracy. In spite of such a rich history, one particular aspect of period estimation has received very little attention from a fundamental perspective. Namely, given a discrete time periodic signal and a list of candidate integer periods, what is the absolute minimum datalength required to estimate its integer period' Notice that the answer we seek must be a fundamental bound, i.e., independent of any particular period estimation technique. Common intuition suggests the minimum datalength as twice the largest expected period. However, this is true only under some special contexts. This paper derives the exact necessary and sufficient bounds to this problem. The above question is also extended to the case of mixtures of periodic signals. First, a careful mathematical formulation discussing the unique identifiability of the component periods (hidden integer periods) is presented. Once again, a rigorous theoretical framework in this regard is missing in the existing literature, but is a necessary platform to derive precise bounds on the minimum necessary datalength. The bounds given here are generic, that is, independent of the algorithms used. Specific algorithm-dependent bounds are also presented in the end for the case of dictionary based integer period estimation reported in recent years.

Additional details