Minimization Problem for Sum of Weighted Convolution Differences: The Case of a Given Number of Elements in the Sum

A. V. Kel’manov, L. V. Mikhailova, P. S. Ruzankin, S. A. Khamidullin

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование


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.

Язык оригиналаанглийский
Страницы (с-по)103-116
Число страниц14
ЖурналNumerical Analysis and Applications
Номер выпуска2
СостояниеОпубликовано - 1 июн. 2020


Подробные сведения о темах исследования «Minimization Problem for Sum of Weighted Convolution Differences: The Case of a Given Number of Elements in the Sum». Вместе они формируют уникальный семантический отпечаток (fingerprint).