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

На правах рукописиЗвонарев Никита КонстантиновичСтруктурные аппроксимации временных рядовСпециальноть 01.01.07 –вычислительная математикаАвторефератдиссертации на соискание учёной степеникандидата физико-математических наукСанкт-Петербург – 2018Работа выполнена в федеральном государственном бюджетномобразовательном учреждении высшего образования«Санкт-Петербургский государственный университет».Научный руководитель:Голяндина Нина Эдуардовна,кандидат физико-математических наук, доцентОфициальные оппоненты: Шевляков Георгий Леонидович,доктор физико-математических наук, профессор,Санкт-Петербургский политехнический универ­ситет Петра Великого, профессор кафедры при­кладной математикиАнтонов Антон Александрович,кандидат физико-математических наук, финан­совый математик в ООО «Эксперт-Система»Ведущая организация:Федеральное государственное бюджетное образо­вательное учреждение высшего образования«Вологодский государственный университет»Защита состоится «14» июня 2018 г.

в 11 часов 00 минут на заседании диссер­тационного совета Д 212.232.49 на базе Санкт-Петербургского государствен­ного университета по адресу: 198504, Санкт-Петербург, Старый Петергоф,Университетский пр., д. 28, ауд. 405.С диссертацией можно ознакомиться в Научной библиотеке им. М. Горько­го Санкт-Петербургского государственного университета по адресу: 199034,Санкт-Петербург, Университетская наб., 7-9 и на сайте:https://disser.spbu.ru/files/disser2/disser/bprpwWD9w4.pdf.Автореферат разослан «»Ученый секретарь диссертационного совета,доктор физико-математических наук2018 г.Чурин Ю.В.3Общая характеристика работыАктуальность темы.

Временные ряды встречаются во многих обла­стях науки. Чаще всего, временной ряд — последовательно измеренный черезравноотстоящие промежутки времени вещественный показатель некоторогопроцесса. Кроме того, название временной ряд сохраняется и в том случае,когда измерения сделаны не во временных точках, а равномерно вдоль про­странственной координаты. Будем представлять временной ряд длины ≥ 2как вектор-столбец X = (1 , .

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

, )T — шумовая составляющая (или про­сто шум). Предполагается, что сигнальная составляющая имеет некоторуюструктуру, а шумовая составляющая является реализацией некоего случай­ного процесса с нулевым математическим ожиданием.Рассмотрим следующий параметрический вид сигнала S в виде конечнойсуммы:∑︁ = () exp( ) sin(2 + ),(1)где () — многочлены от степени . Такой вид сигнала используетсяво многих приложениях, например, в теории обработки сигнала [5], в задачахидентификации линейных систем [6], задачах распознавания речи [7] и мно­гих других. В приложениях к теории обработки сигнала часто считается, чтосигнал S в представлении (1) является суммой синусоид [5] или экспоненци­ально-модулированных синусоид [6].Важной задачей анализа временных рядов является оценка сигнала Sпо ряду наблюдений X.

Полученную оценку сигнала можно использовать дляоценивания параметров сигнала, построения оценки прогноза сигнала и раз­ложения сигнала на аддитивные составляющие [8].Часто явный вид сигнала (1) неизвестен, то есть неизвестно количествоненулевых слагаемых , количество ненулевых частот и так далее. Вместоэтого фиксируют так называемый ранг ряда S, определённый следующимспособом. Для заданного натурального числа , 1 < < , называемого4длиной окна, определим оператор вложения : R → R×( −+1) как⎞⎛1 2 .

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

Выбор значе­ния ранга сигнала — отдельная задача и в данной работе не рассматривается.В дальнейшем считаем ранг временного ряда известным.Множество всевозможных временных рядов ранга обозначим как .Тогда для решения задачи оценивания сигнала можно использовать решениеследующей нелинейной задачи взвешенных наименьших квадратов:Y⋆ = arg min ‖X − Y‖2W ,(3)Y∈где ‖Z‖2W = ZT WZ — квадрат косоугольной евклидовой нормы, W ∈ R ×— положительно определённая матрица весов, — замыкание множества .

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

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

Несмотря на свои достоинства (самые главные изкоторых — сходимость к локальному минимуму и большая эффективностьпо времени работы в случае диагональной W), методы обладают рядом недо­статков. Первый — методы чувствительны к форме матрицы W, то есть, на­пример, если W является хотя бы трёхдиагональной, то быстрая реализацияметода невозможна.

Второй недостаток — методы проявляют неустойчивостьв ряде случаев, например, когда S является полиномиальным сигналом.Второй подход — непараметрический метод итераций Кэдзоу, входящийв класс алгоритмов попеременных проекций (Alternating Projections) [5]. Ме­тод решает задачу HSLRA в матричном виде:Y⋆ = arg min L,R (Y), L,R (Y) = ‖X − Y‖2L,R ,(4)Y∈ℳ ∩ℋ‖X‖L,R — порождённая скалярным произведением ⟨X, Y⟩L,R = tr(LXRYT )матричная норма, ℋ = ℋ, — пространство ганкелевых матриц размера × , ℳ ⊂ R× — множество матриц ранга, не превосходящего , а X, Y— матрицы, связаные с задачей (3) соотношениями X = (X) и Y = (Y).Теория метода Кэдзоу тесно связана с теорией так называемых subspace­based методов и метода SSA (Singular Spectrum Analysis, анализ сингулярногоспектра) [8]. Метод можно распространить на случай косоугольной нормы,отличной от евклидовой [14]. Основные проблемы метода — локальные свой­ства предельной точки, полученной методом Кэдзоу, неизвестны; к тому же,в большинстве случаев метод решает задачу (4) с матрицами весов L, R, недающими W в постановке (3) (что ведёт к тому, что метод не может обеспе­чить ОМП даже в случае белого гауссовского шума [15]).

Вопрос выбора под­ходящих матриц L, R, дающих матрицу весов W, близкую к Σ−1 , остаётсяоткрытым. Также, быстрая реализация метода Кэдзоу была создана толькодля диагональной W.Асимптотические свойства ошибок оценки сигнала с помощью решения6задачи (3) рассматривались в работах [9, 16, 17]. Однако полученные в этихработах утверждения либо не учитывают вид матрицы W [16], либо множе­ство таких матриц W сильно ограничено [17]. Для алгоритма Кэдзоу известнанеоптимальность полученных им оценок: в смысле недостижения алгоритмомлокального минимума [18] и в смысле качества оценки сигнала [9]. Однаконет результата о том, насколько критично для оценивания сигнала то, чтолокальный минимум в задаче (4) точно не находится, и можно ли улучшитькачество оценки путём выбора весов L, R.В диссертации рассматривается и развивается как параметрический, таки непараметрический подход.

Предлагаются новый метод локального поиска,базирующийся на одном из стандартных для нелинейной задачи наименьшихквадратов методе Гаусса-Ньютона, и расширение непараметрического методаКэдзоу. Ключевыми факторами при выборе методов для исследования явля­лись: возможность построить эффективную по времени реализацию каждогоиз методов, возможность использовать метод для недиагональных матриц ве­сов и находить асимптотические свойства оценок, полученных методами приоценивании сигнала в широком классе сигналов ранга . Более того, необ­ходимость изучения как непараметрического, так и параметрического подхо­да объясняется тем, что для решения задачи (3) с использованием методовлокального поиска требуется начальное приближение, близкое или лежащеев окрестности глобального минимума.