Диссертация (Структурные аппроксимации временных рядов)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиЗвонарев Никита КонстантиновичСтруктурные аппроксимации временных рядов01.01.07 – Вычислительная математикаДИССЕРТАЦИЯна соискание ученой степеникандидата физико-математических наукНаучный руководитель — кандидатфизико-математических наук, доцентГоляндина Нина ЭдуардовнаСанкт-Петербург – 20182ОглавлениеВведение . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .4Используемые обозначения . . . . . . . . . . . . . . . . . . . . . . . .15Глава 1.Сведения из теории временных рядов конечного рангаи теории оптимизации . . . . . . . . . . . . . . . . . .

. . . . . . . .181.1. Линейные рекуррентные формулы . . . . . . . . . . . . . . . . . .181.2. Независимость ранга временного ряда от длины окна . . . . .211.3. Методы оптимизации для нелинейной задачи наименьших квад­ратов . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .221.4. Непараметрический метод Кэдзоу . . . . . . . . . . . . . . . . . .251.5. Метод квадратичного программирования «Active Set» . . . . . .26Глава 2.Свойства задачи аппроксимации временных рядов ря­дами конечного ранга . . . . . . . . . . . . .

. . . . . . . . . . . . .282.1. Необходимые свойства и . . . . . . . . . . . . . . . . . . . .282.2. Параметризация множества . . . . . . . . . . . . . . . . . . .302.3. Дополнительные свойства . . . . . . . . . . . . . . . . . . . . .372.4. Условия минимума в задаче аппроксимации рядами конечногоранга . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .382.5. Задача аппроксимации как задача оценивания сигнала . . . . . .41Глава 3.Численные методы решения задачи аппроксимации вре­менных рядов рядами конечного ранга . . . . . . . . . . . . . . .473.1. Методы локальной оптимизации . . . . . . . . . . . . . . . . . . .473.2. Вычисление базисов пространств () и (2 ) . . . . .

. . . . .553.3. Алгоритмы решения задачи . . . . . . . . . . . . . . . . . . . . .663Глава 4.Матричный подход к задаче аппроксимации временногоряда рядами конечного ранга (метод Кэдзоу) . . . . . . . . . . .734.1. Сходимость метода Кэдзоу по подпоследовательностям . . . . . .744.2. Постановка задачи поиска весов . . . . . . .

. . . . . . . . . . . .784.3. Применение квадратичного программирования к поиску весов . .864.4. Поиск весов с помощью минимизации гладкой функции . . . . .964.5. Быстрая реализация алгоритма Кэдзоу . . . . . . . . . . . . . . .984.6. Применение метода Кэдзоу к решению задачи аппроксимациивременных рядов рядами конечного ранга . . . . . . .

. . . . . . 1034.7. Применение алгоритма Кэдзоу к задаче оценивания сигнала . . . 106Глава 5.Результаты численных экспериментов по устойчивостии применимости модифицированного метода Гаусса-Ньютона иметода Кэдзоу . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . 1165.1. Исследование устойчивости алгоритмов . . . . . . . . . . . . . . . 1165.2. Исследование свойств оценок сигнала с помощью статистическо­го моделирования . . . . . . . . . . . . . . . . . . . . . . . . . . .

1235.3. Применение модифицированного метода Гаусса-Ньютона к дан­ным экспрессии генов . . . . . . . . . . . . . . . . . . . . . . . . . 1315.4. Аппроксимация временными рядами конечного ранга при неиз­вестных параметрах авторегрессионного шума . . . . . . . . . . . 137Заключение . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . 144Список литературы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1464ВведениеАктуальность темыВременные ряды встречаются во многих областях науки. Чаще всего, вре­менной ряд — последовательно измеренный через равноотстоящие промежуткивремени вещественный показатель некоторого процесса. Кроме того, названиевременной ряд сохраняется и в том случае, когда измерения сделаны не во вре­менных точках, а равномерно вдоль пространственной координаты.

Будем пред­ставлять временной ряд длины ≥ 2 как вектор-столбец X = (1 , . . . , )T ∈R .Для того чтобы дальнейшее исследование временных рядов стало возмож­ным, строится модель их представления. Предположим, что временной ряд име­ет следующий вид: = + , = 1, 2, . . . , ,где X — ряд наблюдений, S = (1 , . . . , )T — сигнальная составляющая (илипросто сигнал) и = (1 , . . . , )T — шумовая составляющая (или простошум).

Предполагается, что сигнальная составляющая имеет некоторую струк­туру, а шумовая составляющая является реализацией случайного процесса снулевым математическим ожиданием.Рассмотрим следующий параметрический вид сигнала S в виде конечнойсуммы: =∑︁ () exp( ) sin(2 + ),(1)где () — многочлены от степени .

Такой вид сигнала используетсяво многих приложениях, например, в теории обработки сигнала [1], в задачахидентификации линейных систем [2], задачах распознавания речи [3] и многихдругих. В приложениях к теории обработки сигнала часто считается, что сигнал5S в представлении (1) является суммой синусоид [1] или экспоненциально-моду­лированных синусоид [2].Важной задачей обработки временных сигналов является оценка сигналаS по ряду наблюдений X.

Полученную оценку сигнала можно использовать дляоценивания параметров сигнала [4, 5, 6, 7], построения оценки прогноза сигнала[8, 9, 10] и разложения сигнала на аддитивные составляющие [8, 5, 11].Часто явный вид сигнала (1) неизвестен, то есть неизвестно количествоненулевых слагаемых , количество ненулевых частот и так далее.

Вместоэтого фиксируют так называемый ранг ряда S, определённый следующим спо­собом: для заданного натурального числа , 1 < < , называемого длинойокна, определим оператор вложения ⎛1 2⎜⎜⎜ 2 3 (S) = ⎜⎜ ....⎜..⎝: R → R×( −+1) как⎞. . . −+1.. ⎟⎟.... ⎟⎟.⎟. . . −1 ⎟⎠ +1 . . .(2)Скажем, что ряд S имеет ранг , если rank (S) = < /2 для любого такого, что min(, − + 1) > [8]. Например, сумма двух экспонент, как исинусоидальный сигнал или линейная функция, имеет ранг 2. Матрица (S)называется траекторной матрицей ряда S.Матрица (S) является ганкелевой, то есть элементы на её побочных диа­гоналях равны. Перестановкой строк или столбцов матрицы (S) в обратномпорядке можно добиться равенства элементов на её диагоналях, то есть приве­сти её к эквивалентному тёплицевому виду.

Модель данных, где соответству­ющая сигналу S ганкелева матрица (S) имеет конечный ранг, встречаетсяв теории обработки сигналов [1, 12], задачах распознавания речи [3], теорииуправления и теории стохастических систем [2, 13]. Выбор значения ранга сиг­нала — отдельная задача и в данной работе не рассматривается. В дальнейшем6считаем ранг ряда известным.Множество всевозможных рядов ранга обозначим как . Тогда длярешения задачи оценивания сигнала можно использовать решение следующейнелинейной задачи взвешенных наименьших квадратов:Y⋆ = arg min ‖X − Y‖2W ,(3)Y∈где ‖Z‖2W = ZT WZ — квадрат косоугольной евклидовой нормы, W ∈ R ×— положительно определённая матрица весов, — замыкание множества .Общепринятое название данной задачи — Hankel structured low-rank approxima­tion (HSLRA) [13, 14].

Для определённости, будем называть (3) задачей HSLRAв векторном виде.Если — гауссовский шум с нулевым средним и ковариационной матри­цей Σ, то решение задачи (3) с матрицей весов W = Σ−1 является оценкоймаксимального правдоподобия (ОМП) сигнала S. Заметим, что для того чтобыоценка была ОМП, достаточно знать матрицу Σ с точностью до константы,так как решение задачи (3) не зависит от умножения W на положительнуюконстанту.Задача (3) сформулирована как задача поиска глобального минимума, ноизвестно, что целевая функция является невыпуклой [15], следовательно, мо­жет содержать множество локальных минимумов. Для решения такой задачиможно либо использовать методы глобального поиска, либо локальный поискс выбором достаточно близкого к оптимальному начального приближения.

Вработе разрабатываются методы локального поиска; также рассматривается ивопрос выбора начального приближения.Для решения задачи (3) применяются численные методы. Для их постро­ения используются два основных подхода. Первый — так называемый принципVariable projection, рассмотренный в работах [16, 17] для более общего, чем в (3),случая произвольной аффинной структуры. В [17] после применения принципа7Variable projection используются методы Гаусса-Ньютона и Левенберга-Марк­вардта (регуляризованная версия метода Гаусса-Ньютона), которые являютсяметодами локального поиска, но основаны на параметризации, отличной от (1).Несмотря на свои достоинства (самые главные из которых — сходимость к ло­кальному минимуму и большая эффективность по времени работы в случаедиагональной W), методы обладают рядом недостатков.

Первый — методы чув­ствительны к форме матрицы W, то есть, например, если W является хотя бытрёхдиагональной, то быстрая реализация метода невозможна. Второй недо­статок — методы проявляют неустойчивость в ряде случаев, например, когда Sявляется полиномиальным сигналом.Второй подход — непараметрический метод итераций Кэдзоу, входящий вкласс алгоритмов попеременных проекций (Alternating Projections) [1].