The minimization problem for the sum of weighted convolution differences: the case of a given number of elements in the sum
A.V. Kel’manov1,2, L.V. Mikhailova1, P.S. Ruzankin1,2, S.A. Khamidullin1
1Sobolev Institute of Mathematics, Novosibirsk, Russia
2Novosibirsk State University, Novosibirsk, Russia
Keywords: числовые последовательности, разность взвешенных сверток, переменная длина свертки, минимум суммы, точный полиномиальный алгоритм, численное моделирование, ECG-подобный сигнал, PPG-подобный сигнал, numerical sequences, difference of weighted convolutions, variable length convolution, minimum of sum, exact polynomial-time algorithm, numerical modeling, electrocardiogram-like signal, photoplethysmogram-like signal
Abstract
We consider an unstudied optimization problem of summing the elements of the two numerical sequences: Y of length N and U of length q ≤ 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 Tmax ≤ N , 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 O(T3max M N ). If Tmax is a fixed parameter of the problem, then the algorithm running time is O( M N ). 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.
|
