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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2021, Volume 61, Number 7, Pages 1162–1171
DOI: https://doi.org/10.31857/S0044466921070097
(Mi zvmmf11266)
 

This article is cited in 1 scientific paper (total in 1 paper)

Computer science

Recognition of a quasi-periodic sequence containing an unknown number of nonlinearly extended reference subsequences

A. V. Kel'manovab, L. V. Mikhailovaa, P. S. Ruzankinab, S. A. Khamidullina

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, 630090, Novosibirsk, Russia
b Novosibirsk State University, 630090, Novosibirsk, Russia
Citations (1)
Abstract: A previously unstudied optimization problem induced by noise-proof recognition of a quasi-periodic sequence, namely, by the recognition of a sequence $Y$ of length $N$ generated by a sequence $U$ belonging to a given finite set $W$ (alphabet) of sequences is considered. Each sequence $U$ from $W$ generates an exponentially sized set $\chi(U)$ consisting of all sequences of length $N$ containing (as subsequences) a varying number of admissible quasi-periodic (fluctuational) repeats of $U$. Each quasi-periodic repeat is generated by admissible transformations of $U$, namely, by shifts and extensions. The recognition problem is to choose a sequence $U$ from $W$ and to approximate $Y$ by an element $X$ of the sequence set $\chi(U)$. The approximation criterion is the minimum of the sum of the squared distances between the elements of the sequences. We show that the considered problem is equivalent to the problem of summing the elements of two numerical sequences so as to minimize the sum of an unknown number $M$ of terms, each being the difference between the nonweighted autoconvolution of $U$ extended to a variable length (by multiple repeats of its elements) and a weighted convolution of this extended sequence with a subsequence of $Y$. It is proved that the considered optimization problem and the recognition problem are both solvable in polynomial time. An algorithm is constructed and its applicability for solving model application problems of noise-proof processing of ECG- and PPG-like quasi-periodic signals (electrocardiogram- and photoplethysmogram-like signals) is illustrated using numerical examples.
Key words: numerical sequences, recognition, quasi-periodic sequence, polynomial-time solvability, difference of weighted convolutions.
Funding agency Grant number
Russian Foundation for Basic Research 19-07-00397
19-01-00308
Russian Academy of Sciences - Federal Agency for Scientific Organizations 0314-2019-0015
Ministry of Education and Science of the Russian Federation
This work was supported by the Russian Foundation for Basic Research (project nos. 19-07-00397 and 19-01-00308), the Basic Research Program of the Russian Academy of Sciences (project no. 0314-2019-0015), and the Program Top-5-100 of the Ministry of Science and Higher Education of the Russian Federation.
Received: 26.11.2020
Revised: 26.11.2020
Accepted: 11.03.2021
English version:
Computational Mathematics and Mathematical Physics, 2021, Volume 61, Issue 7, Pages 1153–1161
DOI: https://doi.org/10.1134/S0965542521070095
Bibliographic databases:
Document Type: Article
UDC: 519.72
Language: Russian
Citation: A. V. Kel'manov, L. V. Mikhailova, P. S. Ruzankin, S. A. Khamidullin, “Recognition of a quasi-periodic sequence containing an unknown number of nonlinearly extended reference subsequences”, Zh. Vychisl. Mat. Mat. Fiz., 61:7 (2021), 1162–1171; Comput. Math. Math. Phys., 61:7 (2021), 1153–1161
Citation in format AMSBIB
\Bibitem{KelMikRuz21}
\by A.~V.~Kel'manov, L.~V.~Mikhailova, P.~S.~Ruzankin, S.~A.~Khamidullin
\paper Recognition of a quasi-periodic sequence containing an unknown number of nonlinearly extended reference subsequences
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2021
\vol 61
\issue 7
\pages 1162--1171
\mathnet{http://mi.mathnet.ru/zvmmf11266}
\crossref{https://doi.org/10.31857/S0044466921070097}
\elib{https://elibrary.ru/item.asp?id=46146277}
\transl
\jour Comput. Math. Math. Phys.
\yr 2021
\vol 61
\issue 7
\pages 1153--1161
\crossref{https://doi.org/10.1134/S0965542521070095}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000687174400009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85113821328}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf11266
  • https://www.mathnet.ru/eng/zvmmf/v61/i7/p1162
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Statistics & downloads:
    Abstract page:64
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024