Optimal detection of a~given number of unknown quasiperiodic fragments in a~numerical sequence

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

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 10 (2007) no. 2, pp. 159-175.

Résumé

The a posteriori approach to the problem of the noise-proof detection of unknown quasiperiodic fragments in a numerical sequence is studied. It is assumed that the number of elements in the fragments is given. The case is analyzed, where (1) the number of fragments is known; (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 established that the problem under consideration is reduced to testing a set of hypotheses about the mean of a random Gaussian vector. It is shown that the search for a maximum-likelihood hypothesis is equivalent to finding the arguments which yield a maximum for auxiliary object function. It is proven that maximizing this auxiliary object function is a polynomial-solvable discrete optimization problem. An exact algorithm for solving this auxiliary problem is substantiated. We derive and prove an algorithm for the optimal (maximum-likelihood) detection of fragments. The kernel of this algorithm is the algorithm for solution to an auxiliary problem. The results of numerical simulation are presented.

Bibliographie

[1] Wiley R. G., Electronic Intelligence: The Analysis of Radar Signals, Artech House, Norwood, MA, 1993

[2] Skolnik M. I., Introduction to Radar System, 3rd ed., McGraw-Hill, New York, 2001

[3] Haykin S., Communication System, 4th ed., John Wiley Sons Inc., New York, 2001

[4] Robinson E. A. and Treitel S., Geophysical Signal Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1980 | Zbl

[5] Markel J. D. and Gray A. H., Linear Prediction of Speech, Springer Verlag, Berlin–Heidelberg–New York, 1976

[6] Tompkins W. J., Biomedical Digital Signal Processing, Prentice-Hall, Englewood Cliffs, NJ, 1993

[7] Vas P., Parameter Estimation, Condition Monitoring and Diagnosis of Electrical Machines, Oxford University Press, Oxford, 1993

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

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

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

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

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

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

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

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

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

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

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

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

[20] Helstrom C. W., Elements of signal detection and estimation, Prentice-Hall, Englewood Cliffs, NJ, 1979

[21] Anderson B. D. and Moore J. D., Optimal filtering, Prentice-Hall, Englewood Cliffs, NJ, 1995

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

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

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

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

[26] 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, March | DOI | MR

[27] 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. matem. i mat. fiziki, 46:1 (2006), 172–189 | MR

[28] Gimadi E. Kh., Kelmanov A. V., Kelmanova M. A., Khamidullin S. A., “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zhurn. industrialnoi matem. / RAN. Sib. otd-nie. — Novosibirsk, 9:1 (2006), 55–74 | MR

[29] Kelmanov A. V., “Aposteriornyi podkhod k resheniyu tipovykh zadach analiza i raspoznavaniya chislovykh kvaziperiodicheskikh posledovatelnostei: obzor rezultatov”, Doklady XII Vserossiiskoi konf. “Matematicheskie metody raspoznavaniya obrazov” (MMRO-12), Moskva, 2005, 125–128