Задача минимизации суммы разностей взвешенных сверток

В работе рассматривается неизученная экстремальная задача суммирования элементов числовых последовательностей $Y$ длины $N$ и $U$ длины $q \leqslant N$. В задаче требуется минимизировать сумму разностей взвешенных сверток последовательностей переменной длины (не менее $q$). В каждой разности первая невзвешенная свертка – автосвертка растянутой на переменную длину последовательности $U$ (путем кратных повторов ее элементов), вторая – взвешенная свертка этой растянутой последовательности с подпоследовательностью из $Y$. Анализируется вариант задачи с оптимизируемым числом суммируемых разностей. Показано, что задача эквивалентна одной из проблем аппроксимации последовательности $Y$ элементом $X$ из экспоненциального по мощности множества последовательностей. Это множество объединяет все последовательности длины $N$, которые в качестве подпоследовательностей включают переменное число $M$ допустимых квазипериодических (флуктуационных) повторов последовательности $U$. Каждый квазипериодический повтор порождается допустимыми преобразованиями последовательности $U$. Этими преобразованиями являются: 1) сдвиг $U$ на переменную величину, которая между соседними повторами не превышает ${{T}_{{max}}} \leqslant N$, 2) переменное растягивающее отображение $U$ в последовательность переменной длины, которое определяется в виде повторов элементов из $U$, кратность этих повторов – переменная величина. Критерием аппроксимации является минимум суммы квадратов расстояний между элементами последовательностей. Доказано, что рассматриваемая экстремальная задача и вместе с ней задача аппроксимации разрешимы за полиномиальное время. А именно, показано, что существует точный алгоритм, который находит решение задачи за время $\mathcal{O}(T_{{max}}^{3}N)$. Если ${{T}_{{max}}}$ – фиксированный параметр задачи, то время работы алгоритма линейно. Примерами численного моделирования проиллюстрирована применимость алгоритма к решению модельных прикладных задач помехоустойчивой обработки ECG-подобных и PPG-подобных квазипериодических сигналов (electrocardiogram-like and photoplethysmogram-like signals). Библ. 13. Фиг. 4.