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

В работе рассматривается неизученная экстремальная задача суммирования элементов числовых последовательностей $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^3_{\max}MN$). Если $T_{\max}$ — фиксированный параметр задачи, то время работы алгоритма равно $\mathcal{O}(MN)$. Примерами численного моделирования проиллюстрирована применимость алгоритма к решению модельных прикладных задач помехоустойчивой обработки ECG- и PPG-подобных квазипериодических сигналов (electrocardiogram-like и photoplethysmogram-like signals).