Abstract: В работе рассматривается неизученная экстремальная задача суммирования элементов числовых последовательностей Y длины N и U длины q ≤ N . В задаче требуется минимизировать сумму разностей взвешенных сверток последовательностей переменной длины (не менее q ). В каждой разности первая невзвешенная свертка - автосвертка растянутой на переменную длину последовательности U (путем кратных повторов ее элементов), вторая - взвешенная свертка этой растянутой последовательности с подпоследовательностью из Y. Анализируется вариант задачи с заданным на входе числом суммируемых разностей. Мы показываем, что задача эквивалентна одной из проблем аппроксимации последовательности Y элементом X из экспоненциального по мощности множества последовательностей. Это множество объединяет все последовательности длины N , которые в качестве подпоследовательностей включают M допустимых квазипериодических (флуктуационных) повторов последовательности U . Каждый квазипериодический повтор порождается допустимыми преобразованиями последовательности U . Этими преобразованиями являются: 1) сдвиг U на переменную величину, которая между соседними повторами не превышает Tmax ≤ N ; 2) переменное растягивающее отображение U в последовательность переменной длины, которое определяется в виде повторов элементов из U , кратность этих повторов - переменная величина. Критерием аппроксимации является минимум суммы квадратов расстояний между элементами последовательностей. Мы доказываем, что рассматриваемая экстремальная задача и вместе с ней задача аппроксимации разрешимы за полиномиальное время. А именно, мы показываем, что существует точный алгоритм, который находит решение задачи за время O(T3max M N ). Если Tmax - фиксированный параметр задачи, то время работы алгоритма равно O( M N ). Примерами численного моделирования проиллюстрирована применимость алгоритма к решению модельных прикладных задач помехоустойчивой обработки ECG- и PPG-подобных квазипериодических сигналов (electrocardiogramlike и photoplethysmogram-like signals).

Cite: Кельманов А.В. , Михайлова Л.В. , Рузанкин П.С. , Хамидуллин С.А.
Задача минимизации суммы разностей взвешенных сверток, случай заданного числа элементов в сумме
Сибирский журнал вычислительной математики. 2020. Т.23. №2. С.127-142. DOI: 10.15372/sjnm20200202 РИНЦ OpenAlex

Translated: Kel’manov A.V. , Mikhailova L.V. , Ruzankin P.S. , Khamidullin S.A.
Minimization Problem for Sum of Weighted Convolution Differences: The Case of a Given Number of Elements in the Sum
Numerical Analysis and Applications. 2020. V.13. N2. P.103-116. DOI: 10.1134/s1995423920020020 WOS Scopus OpenAlex

Identifiers:

Elibrary:	42869904
OpenAlex:	W4247841035

Citing: Пока нет цитирований

Altmetrics: