Optimal detection of a~recurring tuple of reference fragments in a~quasi-periodic sequence

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

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 11 (2008) no. 3, pp. 311-327.

Résumé

The a posteriori (off-line) approach to solving the problem of maximum-likelihood detection of a recurring tuple containing reference fragments in a numerical quasi-periodic sequence is studied. The case is analyzed, where (1) the total number of fragments in a sequence is unknown; (2) the index of a sequence term corresponding to the beginning of a fragment is a deterministic (not random) value; (3) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is shown that the problem under consideration is reduced to testing a set of simple hypotheses about the mean of a random Gaussian vector. The cardinality of this totality exponentially grows as the vector dimension (i.e., the length of a sequence understudy) increases. It is established that the search for a maximum-likelihood hypothesis is equivalent to finding the arguments which yield a maximum for an auxiliary objective function. It is shown that maximizing this objective function is reduced to solving a special optimization problem. It is proven that this special problem is a polynomial-solvable one. The exact algorithm for solving this problem is substantiated, which underlies the algorithm for the optimal (maximum-likelihood) detection of the recurring tuple. The kernel of this algorithm is the algorithm for solution of a special (basic) optimization problem. The results of numerical simulation are presented.

Bibliographie

[1] Kelmanov A. V., Mikhailova L. V., Khamidullin S. A., “Zadacha aposteriornogo obnaruzheniya v chislovoi kvaziperiodicheskoi posledovatelnosti povtoryayuschegosya nabora etalonnykh fragmentov. Sluchai zadannogo chisla fragmentov”, Tez. dokl. Vseross. konf. “Matematicheskoe programmirovanie i prilozheniya”, Ekaterinburg, 2007, 182–183

[2] Kelmanov A. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie zadannogo chisla odinakovykh podposledovatelnostei v kvaziperiodicheskoi posledovatelnosti”, Zhurn. vychisl. matematiki i mat. fiziki, 41:5 (2001), 807–820 | MR

[3] Kel'manov A. V., Khamidullin S. A., Okol'nishnikova L. V., “A posteriori detection of identical subsequences in a quasiperiodic sequence”, Pattern Recognition and Image Analysis, 12:4 (2002), 438–447 | MR

[4] Kel'manov A. V., Jeon B., “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train”, IEEE Transactions on Signal Processing, 52:3 (2004), 1–12 | DOI | MR

[5] Wald A., Sequential analysis, John Wiley, New York, 1947 | MR

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

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

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

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

[10] M. Bassvil, A. Vilski, A. Banvenist i dr. (ed.), Obnaruzhenie izmeneniya svoistv signalov i dinamicheskikh sistem, Mir, M., 1989

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

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

[13] 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

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

[15] 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, January | DOI | MR

[16] Van Trees H. L., Detection, Estimation, and Modulation Theory, Part I, John Wiley Sons Inc., New York, 1968

[17] Helstrom C. W., Elements of Signal Detection and Estimation, Prentice-Hall, Englewood Cliffs, NJ, 1979

[18] Anderson B. D. and Moore J. D., Optimal Filtering, 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] Fukunaga K., Introduction to Statistical Pattern Recognition, 2nd ed., Academic Press, New York, 1990 | MR | Zbl

[21] Fu K. S., Syntactic Methods in Pattern Recognition, Academic Press, New York, 1974 | MR

[22] Kel'manov A. V., Khamidullin S. A., “A posteriori joint detection and discrimination of a given number of subsequences in a quasiperiodic sequence”, Pattern Recognition and Image Analysis, 10:3 (2000), 379–388 | MR

[23] Kel'manov A. V., Okol'nishnikova L. V., “A posteriori simultaneous detection and discrimination of subsequences in a quasiperiodic sequence”, Pattern Recognition and Image Analysis, 11:3 (2001), 505–520

[24] Kelmanov A. V., Mikhailova L. V., “Sovmestnoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti zadannogo chisla fragmentov iz etalonnogo nabora i ee razbienie na uchastki, vklyuchayuschie serii odinakovykh fragmentov”, Zhurn. vychisl. matematiki i mat. fiziki, 46:1 (2006), 172–189 | MR