Задача минимизации суммы разностей взвешенных сверток, случай заданного числа элементов в сумме
А.В. Кельманов1,2, Л.В. Михайлова1, П.С. Рузанкин1,2, С.А. Хамидуллин1
1Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Новосибирск, Россия
mikh@math.nsc.ru
2Новосибирский национальный исследовательский государственный университет, Новосибирск, Россия
ruzankin@math.nsc.ru
Ключевые слова: числовые последовательности, разность взвешенных сверток, переменная длина свертки, минимум суммы, точный полиномиальный алгоритм, численное моделирование, ECG-подобный сигнал, PPG-подобный сигнал, numerical sequences, difference of weighted convolutions, variable length convolution, minimum of sum, exact polynomial-time algorithm, numerical modeling, electrocardiogram-like signal, photoplethysmogram-like signal
Страницы: 127-142
Аннотация
В работе рассматривается неизученная экстремальная задача суммирования элементов числовых последовательностей 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).
DOI: 10.15372/SJNM20200202 |
