The minimization problem for the sum of weighted convolution differences: the case of a given number of elements in the 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 ≤ 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 ﬁrst 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 (ﬂuctuating) 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<sub>max </sub>≤ 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. Speciﬁcally, we show that there exists an algorithm which solves the problems in the time O(T<sup>3</sup><sub>max </sub> M N ). If T<sub>max</sub> is a ﬁxed 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.