The

A. V. Kel'manov ; L. V. Mikhailova ; P. S. Ruzankin ; S. A. Khamidullin

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 23 (2020) no. 2, pp. 127-142

Résumé

We consider an unstudied optimization problem of summing the elements of the two numerical sequences: $Y$ of length $N$ and $U$ of length $q\leqslant N$. The objective of the optimization problem is to minimize the sum of differences of weighted convolutions of sequences of variable lengths (which are not less than $q$). In each of the differences, the first convolution is the unweighted autoconvolution of the sequence $U$ nonlinearly expanded in time (by repetitions of its elements), and the second one is the weighted convolution of an expanded sequence with a subsequence of $Y$. The number of differences is given. We show that the problem is equivalent to that of approximation of the sequence $Y$ by an element of some exponentially sized set of sequences. Such a set consists of all the sequences of length $N$ which include, as subsequences, a given number $M$ of admissible quasiperiodic (fluctuating) repetitions of the sequence $U$. Each quasiperiodic repetition is generated by the following admissible transformations of the sequence $U$: (1) shifting $U$ in time, so that the differences between consecutive shifts do not exceed $T_{\max} \leqslant N$, (2) variable expansion of $U$ in time consisting in repeating each element of $U$, with variable multiplicities of the repetitions. The optimization objective is minimizing the sum of the squares of element-wise differences. We demonstrate that the optimization problem in combination with the corresponding approximation problem are solvable in polynomial time. Specifically, we show that there exists an algorithm which solves the problems in the time $\mathcal{O}(T^3_{\max}MN$). If $T_{\max}$ is a fixed parameter of the problem, then the algorithm running time is $O(MN)$. In the examples of numerical modeling, we show the applicability of the algorithm to solving applied problems of noise-robust analyzing electrocardiogram-like and photoplethysmogram-like signals.