Joint detection of a given number of reference fragments in a quasi-periodic sequence and its partition into segments containing series of identical fragments

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

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 46 (2006) no. 1, pp. 172-189

Résumé

The problem of joint a posteriori detection of reference fragments in a quasi-periodic sequence and its partition into segments containing series of recurring fragments from the reference tuple is solved. It is assumed that (i) an ordered reference tuple of sequences to be detected is given, (ii) the number of desired fragments is known, (iii) the index of the sequence term 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 in 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. An efficient a posteriori algorithm producing a maximum-likelihood optimal solution to the problem is substantiated. Time and space complexity bounds related to the parameters of the problem are derived. The results of numerical simulation are presented.

Bibliographie

[1] Kelmanov A. B., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla odinakovykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Zh. vychisl. matem. i matem. fiz., 41:5 (2001), 807–820 | MR

[2] Kelmanov A. B., Khamidullin S. A., “Aposteriornoe sovmestnoe obnaruzhenie i razlichenie zadannogo chisla podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Sibirskii zhurnal industr. matem., 2:2(4) (1999), 106–119 | MR

[3] Kelmanov A. B., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla usechennykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Sibirskii zhurnal industr. matem., 3:1(5) (2000), 137–156 | MR

[4] Kelmanov A. B., Okolnishnikova L. V., “Aposteriornoe sovmestnoe obnaruzhenie i razlichenie zadannogo chisla podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Sibirskii zhurnal industr. matem., 3:2(6) (2000), 115–139 | MR

[5] Kelmanov A. B., Khamidullin C. A., Okolnishnikova L. V., “Aposteriornoe obnaruzhenie odinakovykh podposledovatelnostei-fragmentov v kvaziperiodicheskoi posledovatelnosti”, Sibirskii zhurnal industr. matem., 5:2(10) (2002), 94–108 | MR

[6] Kelmanov A. B., Khamidullin C. A., “Aposteriornoe obnaruzhenie kvaziperiodicheski povtoryayuschegosya fragmenta chislovoi posledovatelnosti v usloviyakh shuma i poteri dannykh”, Sibirskii zhurnal industr. matem., 6:2(14) (2003), 46–63 | MR

[7] Kligene N., Telksnis L., “Metody obnaruzheniya momentov izmeneniya svoistv sluchainykh protsessov”, Avtomatika i telemekhan., 1983, no. 10, 5–56 | MR | Zbl

[8] Torgovitskii I. Sh., “Metody opredeleniya momenta izmeneniya veroyatnostnykh kharakteristik sluchainykh velichin”, Zarubezhnaya radioelektronika, 1976, no. 1, 3–52

[9] Nikiforov I. V., Posledovatelnoe obnaruzhenie izmeneniya svoistv vremennykh ryadov, Nauka, M., 1983 | MR

[10] Zhiglyavskii A. A., Kraskovskii A. E., Obnaruzhenie razladki sluchainykh protsessov v zadachakh radiotekhniki, LGU, L., 1988

[11] Bassvil M., Vilski A., Banvenist A. i dr., Obnaruzhenie izmeneniya svoistv signalov i dinamicheskikh sistem, Mir, M., 1989

[12] Darkhovskii B. S., “O dvukh zadachakh otsenivaniya momentov izmeneniya veroyatnostnykh kharakteristik sluchainoi posledovatelnosti”, Teoriya veroyatnostei i ee primeneniya, 29:3 (1984), 464–473 | MR

[13] Darkhovskii B. S., “Neparametricheskii metod otsenivaniya intervalov odnorodnosti sluchainoi posledovatelnosti”, Teoriya veroyatnostei i ee primeneniya, 30:4 (1985), 795–799 | MR

[14] Brodskii B. E., Darkhovskii B. S., “Sravnitelnyi analiz nekotorykh neparametricheskikh metodov skoreishego obnaruzheniya momenta “razladki” sluchainoi posledovatelnosti”, Teoriya veroyatnostei i ee primeneniya, 35:4 (1990), 655–668 | MR

[15] Darkhovskii B. S., “Retrospektivnoe obnaruzhenie “razladki” v nekotorykh modelyakh regressionnogo tipa”, Teoriya veroyatnostei i ee primeneniya, 40:4 (1995), 898–903 | MR

[16] Gini F., Farina A., Greco M., “Selected list of references on radar signal processing”, IEEE Trans. Aerospace and Electronic Systems, 37:1 (2001), 329–359 | DOI | MR

[17] Van Trees H. L., Detection, estimation, and modulation theory, Part I, John Wiley Sons Inc., New York, 1968

[18] Heistrom C. W., Elements of signal detection and estimation, Prentice-Hall, Englewood Cliffs, NJ, 1995

[19] Duda R. O., Hart P. E., Pattern classification and scene analysis, John Wiley Sons Inc., New York, 1973 | Zbl

[20] Fukinaga K., Introduction to statistical pattern recognition, 2nd ed., Acad. Press, New York, 1990 | MR

[21] Fu K. S., Syntactic methods in pattern recognition, Acad. Press, New York, 1974 | MR

[22] Kelmanov A. B., Khamidullin C. A., “Raspoznavanie kvaziperiodicheskoi posledovatelnosti, obrazovannoi iz zadannogo chisla odinakovykh podposledovatelnostei”, Sibirskii zhurnal industr. matem., 2:1 (1999), 53–74 | MR