One Problem of the Sum of Weighted Convolution Differences Minimization, Induced by the Quasiperiodic Sequence Recognition Problem

One Problem of the Sum of Weighted Convolution Differences Minimization, Induced by the Quasiperiodic Sequence Recognition Problem Full article

Conference

Mathematical Optimization Theory and Operations Research
06-10 Jul 2020 , Новосибирск

Journal

Communications in Computer and Information Science
ISSN: 1865-0929

Output data

Year: 2020, Pages: 51-56 Pages count : 6 DOI: 10.1007/978-3-030-58657-7_6

Tags

Discrete optimization problem · Minimization · Weighted convolutions’ difference · Recognition · Quasiperiodic · Polynomial-time solvability

Authors

Khamidullin Sergey ¹ , Mikhailova Liudmila ¹

Affiliations

1	Sobolev Institute of Mathematics

We consider an unexplored discrete optimization problem of summing the elements of two numerical sequences. One of them belongs to the given set (alphabet) of sequences, while another one is given. We have to minimize the sum of M terms (M is unknown), each of them being the difference between the unweighted auto-convolution of the first sequence stretched to some length and the weighted convolution of this stretched sequence with the subsequence of the second one.We show that this problem is equivalent to the problem of recognizing a quasiperiodic sequence as a sequence induced by some sequence U from the given alphabet. We have constructed the algorithm which finds the exact solution to this problem in polynomial time. The numerical simulation demonstrates that this algorithm can be used to solve modeled applied problems of noise-proof processing of quasiperiodic signals

Khamidullin S. , Mikhailova L.
One Problem of the Sum of Weighted Convolution Differences Minimization, Induced by the Quasiperiodic Sequence Recognition Problem
Communications in Computer and Information Science. 2020. P.51-56. DOI: 10.1007/978-3-030-58657-7_6 Scopus OpenAlex

Scopus:	2-s2.0-85092105530
OpenAlex:	W3086071134

DB	Citing
OpenAlex	1