Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Zh. Vychisl. Mat. Mat. Fiz.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 2 scientific papers (total in 2 papers)

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
Received: 20.10.2006

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
\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
\jour Comput. Math. Math. Phys.
\yr 2008
\vol 48
\issue 5
\pages 850--865

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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru

    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  mathnet  crossref  mathscinet  isi
    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  mathnet  crossref  crossref  isi  elib
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:200
    Full text:63
    First page:1

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022