TY - JOUR

T1 - Minimization Problem for Sum of Weighted Convolution Differences

T2 - The Case of a Given Number of Elements in the Sum

AU - Kel’manov, A. V.

AU - Mikhailova, L. V.

AU - Ruzankin, P. S.

AU - Khamidullin, S. A.

PY - 2020/6/1

Y1 - 2020/6/1

N2 - We consider an unstudied optimization problem of summing elements of two numerical sequences: Y of length N and U of length q ≤ N. The objective of the problem is minimization of the sum of differences of weighted convolutions of sequences of variable length (not less than q). In each difference, the first unweighted convolution is the autoconvolution of the sequence U expanded to a variable length due to multiple repetitions of its elements, and the second one is the weighted convolution of the expanded sequence with a subsequence from Y .We analyze a variant of the problem with a given input number of differences.We show that the problem is equivalent to that of approximation of the sequence Y by an element X of some exponentially-sized set of sequences. Such a set consists of all the sequences of length N that include as subsequences a given number M of admissible quasi-periodic (fluctuating) repetitions of the sequence U. Each quasi-periodic repetition results from the following admissible transformations of the sequence U: (1) shift of U by a variable, which do not exceed Tmax ≤ N for neighboring repetitions, (2) variable expanding mapping of U to a variable-length sequence: variable-multiplicity repetitions of elements of U. The approximation criterion is minimization of the sum of the squares of element-wise differences. We demonstrate that the optimization problemand the respective approximation problemare solvable in a polynomial time. Specifically, we show that there exists an exact algorithm that solves the problem in the time O(T 3 maxMN). If Tmax is a fixed parameter of the problem, then the time taken by the algorithm is O(MN). In examples of numerical modeling, we show the applicability of the algorithm to solving model applied problems of noise-robust processing of electrocardiogram (ECG)-like and photoplethysmogram (PPG)-like signals.

AB - We consider an unstudied optimization problem of summing elements of two numerical sequences: Y of length N and U of length q ≤ N. The objective of the problem is minimization of the sum of differences of weighted convolutions of sequences of variable length (not less than q). In each difference, the first unweighted convolution is the autoconvolution of the sequence U expanded to a variable length due to multiple repetitions of its elements, and the second one is the weighted convolution of the expanded sequence with a subsequence from Y .We analyze a variant of the problem with a given input number of differences.We show that the problem is equivalent to that of approximation of the sequence Y by an element X of some exponentially-sized set of sequences. Such a set consists of all the sequences of length N that include as subsequences a given number M of admissible quasi-periodic (fluctuating) repetitions of the sequence U. Each quasi-periodic repetition results from the following admissible transformations of the sequence U: (1) shift of U by a variable, which do not exceed Tmax ≤ N for neighboring repetitions, (2) variable expanding mapping of U to a variable-length sequence: variable-multiplicity repetitions of elements of U. The approximation criterion is minimization of the sum of the squares of element-wise differences. We demonstrate that the optimization problemand the respective approximation problemare solvable in a polynomial time. Specifically, we show that there exists an exact algorithm that solves the problem in the time O(T 3 maxMN). If Tmax is a fixed parameter of the problem, then the time taken by the algorithm is O(MN). In examples of numerical modeling, we show the applicability of the algorithm to solving model applied problems of noise-robust processing of electrocardiogram (ECG)-like and photoplethysmogram (PPG)-like signals.

KW - difference of weighted convolutions

KW - electrocardiogram-like signal

KW - exact polynomial-time algorithm

KW - minimum of sum

KW - numerical modeling

KW - numerical sequences

KW - photoplethysmogram-like signal

KW - variable length of convolution

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

U2 - 10.1134/S1995423920020020

DO - 10.1134/S1995423920020020

M3 - Article

AN - SCOPUS:85086894811

VL - 13

SP - 103

EP - 116

JO - Numerical Analysis and Applications

JF - Numerical Analysis and Applications

SN - 1995-4239

IS - 2

ER -