A posteriori joint detection of reference fragments in a quasi-periodic sequence

A. V. Kel'manov ; L. V. Mikhailova

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 5, pp. 899-915

Résumé

The problem of joint detection of quasi-periodic reference fragments (of given size) in a numerical sequence and its partition into segments containing series of recurring reference fragments is solved in the framework of the a posteriori approach. It is assumed that (i) the number of desired fragments is not known, (ii) an ordered reference tuple of sequences to be detected is given, (iii) the index of the sequence member corresponding to the beginning of a fragment is a deterministic (not random) value, and (iv) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is established that the problem consists of testing a set of hypotheses about the mean of a random Gaussian vector. The cardinality of the set grows exponentially as the vector dimension (i.e., the sequence length) increases. It is shown that the search for a maximum-likelihood hypothesis is equivalent to the search for arguments that minimize an auxiliary objective function. It is proved that the minimization problem for this function can be solved in polynomial time. An exact algorithm for its solution is substantiated. Based on the solution to an auxiliary extremum problem, an efficient a posteriori algorithm producing an optimal (maximum-likelihood) solution to the partition and detection problem is proposed. The results of numerical simulation demonstrate the noise stability of the algorithm.