Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zh. Vychisl. Mat. Mat. Fiz.: Year: Volume: Issue: Page: Find

 Zh. Vychisl. Mat. Mat. Fiz., 2008, Volume 48, Number 5, Pages 899–915 (Mi zvmmf144)

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

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

Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090, Russia

Abstract: 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.

Key words: numerical sequence, a posteriori processing, quasi-periodic fragment, optimal joint detection and partition, efficient algorithm.

Full text: PDF file (2282 kB)
References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2008, 48:5, 850–865

Bibliographic databases:

UDC: 519.7

Citation: A. V. Kel'manov, L. V. Mikhailova, “A posteriori joint detection of reference fragments in a quasi-periodic sequence”, Zh. Vychisl. Mat. Mat. Fiz., 48:5 (2008), 899–915; Comput. Math. Math. Phys., 48:5 (2008), 850–865

Citation in format AMSBIB
\Bibitem{KelMik08} \by A.~V.~Kel'manov, L.~V.~Mikhailova \paper A~posteriori joint detection of reference fragments in a~quasi-periodic sequence \jour Zh. Vychisl. Mat. Mat. Fiz. \yr 2008 \vol 48 \issue 5 \pages 899--915 \mathnet{http://mi.mathnet.ru/zvmmf144} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2433647} \zmath{https://zbmath.org/?q=an:1164.40305} \transl \jour Comput. Math. Math. Phys. \yr 2008 \vol 48 \issue 5 \pages 850--865 \crossref{https://doi.org/10.1134/S0965542508050126} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000262334100012} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44149089073} 

• http://mi.mathnet.ru/eng/zvmmf144
• http://mi.mathnet.ru/eng/zvmmf/v48/i5/p899

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. V. Kel'manov, A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis”, Comput. Math. Math. Phys., 49:11 (2009), 1966–1971
2. A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “Approximation algorithm for the problem of partitioning a sequence into clusters”, Comput. Math. Math. Phys., 57:8 (2017), 1376–1383
•  Number of views: This page: 200 Full text: 63 References: 44 First page: 1