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

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

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

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

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

где Y_n = (y_n,...,y_n+q-1),  n = 0,...,N - q, при ограничениях:

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

(μ₁,..., μ_L) Î Δ_L(M).

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

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