Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой

Задача  распознавания последовательности, включающей повторяющийся набор эталонных фрагментов

(число фрагментов неизвестно)

Эта задача редуцируется к следующей экстремальной задаче.

Дано: вектор Y Î R^N, словарь W, включающий наборы ненулевых векторов из R^q, причем  |W| = J,  натуральные числа N^–, N⁺, T_min и T_max.

Найти: (U₁,...,U_L) Î W  такой, что

где $$l(m|L) = (m-$1) mod$L+1; Y_n = (y_n,...,y_n+q-1),  n = 0,...,N - q, при ограничении

 (n₁,...,n_M) Î Ω.

Задача разрешима за полиномиальное время. Алгоритм, имеющий временную сложность

O[JL_max(N - q + 1)(T_max - T_min + q)] = O(JL_max N ²) = O(JN ³),