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

Autor: Kel'manov, A. V., Mikhailova, L. V., Ruzankin, P. S., Khamidullin, S. A.
Zdroj: Numerical Analysis & Applications; Jun2020, Vol. 13 Issue 2, p103-116, 14p
Abstrakt: 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 T max ≤ 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 problem and the respective approximation problem are solvable in a polynomial time. Specifically, we show that there exists an exact algorithm that solves the problem in the time 𝒪 (T max 3 M N) . If T max is a fixed parameter of the problem, then the time taken by the algorithm is 𝒪 (M N) . 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. [ABSTRACT FROM AUTHOR]
Databáze: Complementary Index
Externí odkaz: