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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)103-116
Number of pages14
JournalNumerical Analysis and Applications
Issue number2
Publication statusPublished - 1 Jun 2020


  • difference of weighted convolutions
  • electrocardiogram-like signal
  • exact polynomial-time algorithm
  • minimum of sum
  • numerical modeling
  • numerical sequences
  • photoplethysmogram-like signal
  • variable length of convolution


Dive into the research topics of 'Minimization Problem for Sum of Weighted Convolution Differences: The Case of a Given Number of Elements in the Sum'. Together they form a unique fingerprint.

Cite this