TY - JOUR

T1 - Problem of Minimizing a Sum of Differences of Weighted Convolutions

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), by the Basic Research Program of the Russian Academy of Sciences (project no. 0314-2019-0015), and by the Program Top-5-100 of the Ministry of Science and Higher Education of the Russian Federation. Publisher Copyright: © 2020, Pleiades Publishing, Ltd. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/12

Y1 - 2020/12

N2 - A previously unstudied optimization problem concerning the summation of elements of numerical sequences Y and U of respective lengths N and q ≤ N is considered. The task is to minimize the sum of differences between weighted convolutions of sequences of variable length (of at least q). In each difference, the minuend is a nonweighted autoconvolution of the sequence U extended to a variable length (by multiple repeats of its elements) and the subtrahend is a weighted convolution of this extended sequence and a subsequence of Y. The variant of the problem with an optimized number of summed differences is analyzed. It is shown that the problem is equivalent to a problem of approximating the sequence Y by an element X of an exponential-size set of sequences. This set consists of all sequences of length N that include, as subsequences, a variable number M of admissible quasi-periodic (fluctuation) repeats of U. Each quasi-periodic repeat is generated by admissible transformations of U. These transformations are (i) a shift of U by a variable quantity that does not exceed Tmax ≤ N between neighboring repeats, and (ii) a variable extension mapping of U into a sequence of variable length defined in the form of repeats of elements of U with the multiplicity of these repeats being variable. The approximation criterion is the minimum of the sum of squared distances between the elements of the sequences. It is proved that the considered optimization problem, together with the approximation problem, is solvable in polynomial time. More specifically, it is shown that there exists an exact algorithm finding the solution of the problem in O(Tmax3N) time. If Tmax is a fixed parameter of the problem, then the running time of the algorithm is linear. Examples of numerical simulation are used to illustrate the applicability of the algorithm for solving model application problems of noise-proof processing of ECG-like and PPG-like quasi-periodic signals (electrocardiogram-like and photoplethysmogram-like signals).

AB - A previously unstudied optimization problem concerning the summation of elements of numerical sequences Y and U of respective lengths N and q ≤ N is considered. The task is to minimize the sum of differences between weighted convolutions of sequences of variable length (of at least q). In each difference, the minuend is a nonweighted autoconvolution of the sequence U extended to a variable length (by multiple repeats of its elements) and the subtrahend is a weighted convolution of this extended sequence and a subsequence of Y. The variant of the problem with an optimized number of summed differences is analyzed. It is shown that the problem is equivalent to a problem of approximating the sequence Y by an element X of an exponential-size set of sequences. This set consists of all sequences of length N that include, as subsequences, a variable number M of admissible quasi-periodic (fluctuation) repeats of U. Each quasi-periodic repeat is generated by admissible transformations of U. These transformations are (i) a shift of U by a variable quantity that does not exceed Tmax ≤ N between neighboring repeats, and (ii) a variable extension mapping of U into a sequence of variable length defined in the form of repeats of elements of U with the multiplicity of these repeats being variable. The approximation criterion is the minimum of the sum of squared distances between the elements of the sequences. It is proved that the considered optimization problem, together with the approximation problem, is solvable in polynomial time. More specifically, it is shown that there exists an exact algorithm finding the solution of the problem in O(Tmax3N) time. If Tmax is a fixed parameter of the problem, then the running time of the algorithm is linear. Examples of numerical simulation are used to illustrate the applicability of the algorithm for solving model application problems of noise-proof processing of ECG-like and PPG-like quasi-periodic signals (electrocardiogram-like and photoplethysmogram-like signals).

KW - difference of weighted convolutions

KW - ECG-like signal

KW - linear-time algorithm

KW - minimum of a sum

KW - numerical sequences

KW - numerical simulation

KW - polynomial-time solvability

KW - PPG-like signal

KW - variable length of convolution

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

U2 - 10.1134/S0965542520120052

DO - 10.1134/S0965542520120052

M3 - Article

AN - SCOPUS:85098626121

VL - 60

SP - 1951

EP - 1963

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 12

ER -