TY - JOUR

T1 - Recognition of a Quasi-Periodic Sequence Containing an Unknown Number of Nonlinearly Extended Reference Subsequences

AU - Kel’manov, A. V.

AU - Mikhailova, L. V.

AU - Ruzankin, P. S.

AU - Khamidullin, S. A.

N1 - Funding Information: 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. Publisher Copyright: © 2021, Pleiades Publishing, Ltd.

PY - 2021/7

Y1 - 2021/7

N2 - 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 \mathcal{X}(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 \mathcal{X}(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.

AB - 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 \mathcal{X}(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 \mathcal{X}(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.

KW - difference of weighted convolutions

KW - numerical sequences

KW - polynomial-time solvability

KW - quasi-periodic sequence

KW - recognition

UR - http://www.scopus.com/inward/record.url?scp=85113821328&partnerID=8YFLogxK

U2 - 10.1134/S0965542521070095

DO - 10.1134/S0965542521070095

M3 - Article

AN - SCOPUS:85113821328

VL - 61

SP - 1153

EP - 1161

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 7

ER -