Диссертация (1150844)
Текст из файла
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиЗвонарев Никита КонстантиновичСтруктурные аппроксимации временных рядов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 approximation (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].
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
