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

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

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 12, pp. 2247-2260

Résumé

The problem of joint detection of a recurring tuple of reference fragments in a noisy numerical quasi-periodic sequence is solved in the framework of the a posteriori (off-line) approach. It is assumed that (i) the total number of fragments in the sequence is known, (ii) the index of the sequence member corresponding to the beginning of a fragment is a deterministic (not random) value, and (iii) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is shown that the problem consists of testing a set of simple hypotheses about the mean of a random Gaussian vector. A specific feature of the problem is that the cardinality of the set grows exponentially as the vector dimension (i.e., the length of the observed sequence) and the number of fragments in the sequence increase. It is established that the search for a maximum-likelihood hypothesis is equivalent to the search for arguments that maximize a special auxiliary objective function with linear inequality constraints. It is shown that this function is maximized by solving the basic extremum problem. It is proved that this problem is solvable in polynomial time. An exact algorithm for its solution is substantiated that underlies an algorithm guaranteeing optimal (maximum-likelihood) detection of a recurring tuple of reference fragments. The results of numerical simulation demonstrate the noise stability of the detection algorithm.

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., “Aposteriornyi podkhod k resheniyu tipovykh zadach analiza i raspoznavaniya chislovykh kvaziperiodicheskikh posledovatelnostei: obzor rezultatov”, Dokl. XII Vseros. konf. “Matem. metody raspoznavaniya obrazov” (MMRO-12), M., 2005, 125–128

[3] Kelmanov A. B., “Problemy optimizatsii v tipovykh zadachakh pomekhoustoichivoi aposteriornoi obrabotki chislovykh posledovatelnostei s kvaziperiodicheskoi strukturoi”, Materialy III Vseros. konf. “Probl. optimizatsii i ekonomich. prilozh.”, Omsk, 2006, 37–41

[4] Kelmanov A. B., Khachai M. Yu., “O nekotorykh trudnoreshaemykh zadachakh analiza dannykh i raspoznavaniya obrazov”, Inform. byul. Assotsiatsii matem. programmirovaniya, Tezisy dokl. XIII Vseros. konf. “Matem. programmirovanie i prilozh.” Vyp. 11, Ekaterinburg, 2007, 184–185

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

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

[7] Kligene H., 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. (red.), Obnaruzhenie izmeneniya svoistv signalov i dinamicheskikh sistem, Mir, M., 1989

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

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

[14] Brodskii B. E., Darkhovskii B. C., “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. C., “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, 1979

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

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

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

[22] Fu K. S., Syntactic methods in pattern recognition, Acad. Press, New York, 1974 | 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 Analys., 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 idential subsequences in a quasiperiodic sequence”, Pattern Recognition and Image Analys., 12:4 (2002), 438–147 | MR

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

[27] Gimadi E. Kh., Kelmanov A. B., Kelmanova M. A., Khamidullin S. A. Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov, Sibirskii zhurnal industr. matem., 9:1(25) (2006), 55–74 | MR

[28] Kelmanov A. B., Khamidullin S. A., “Optimalnoe obnaruzhenie v chislovoi posledovatelnosti zadannogo chisla neizvestnykh kvaziperiodicheskikh fragmentov”, Sibirskii zhurnal vychisl. matem., 10:2 (2007), 159–175 | MR