Диссертация (1150844), страница 3
Текст из файла (страница 3)
С помощью построенной в главе 2 параметризации введён модифицированный шаг Гаусса-Ньютона (MGN). Найдено различиемежду шагом метода VPGN и шагом метода MGN. Построены алгоритмы вычисления базисов рядов, использующихся в методе MGN, указан порядок обусловленности при их вычислении. Приведено сравнение методов VPGN и MGNпо временной сложности при различных видах матрицы W.В четвёртой главе рассматривается матричный подход к решению задачи (3), заключающийся в применении метода Кэдзоу к задаче (4). Построенодоказательство сходимости метода Кэдзоу по подпоследовательностям. Доказано соотношение между весами W в пространстве рядов, и матрицами L и R,задающими косоугольное скалярное произведение в пространстве матриц, дляэквивалентности задач (3) и (4).
Сформулирована задача поиска положительноопределённых матриц весов L и R, дающих близкие к W0 = Σ−1 веса, доказана эквивалентность сформулированной задачи более простой задаче поискавесов по евклидовой метрике при некоторых условиях. Построена теория эффективного решения задачи поиска весов с использованием метода квадратичного программирования и с помощью оптимизации гладкой функции в параллелепипеде. Создана быстрая реализация метода Кэдзоу, указана её временнаясложность. Найден вид ошибок первого порядка по соотношению сигнал/шум14при использовании оценки сигнала S методом Кэдзоу.В пятой главе проведены численные эксперименты. Показано, что построенная итерация модифицированного метода Гаусса-Ньютона MGN обладает большей устойчивостью, чем шаг метода VPGN при вычислении точки локального минимума. С помощью статистического моделирования подтверждены результаты о величине ошибок первого порядка для проекции на множестворядов ранга и линеаризованного метода Кэдзоу.
Приведены примеры применения модифицированного метода Гаусса-Ньютона MGN к данным экспрессиигенов и к временному ряду с неизвестной ковариационной матрицей шума.15Используемые обозначенияR Множество вещественных чиселC Множество комплексных чиселi Мнимая единицаS, X, Y Временные ряды, , Множества∅ Пустое множество Замыкание множества X, Y Матрицы, Векторы : R → R×( −+1) Оператор вложения : R× → R Оператор векторизации, Случайные векторыΞ, Распределения случайных векторов() ⇒→0 Слабая сходимость (распределений) случайных векторовE Математическое ожидание случайного вектора P(‖‖ < 1) Вероятность событияcov() Ковариационная матрица случайного вектора ∈ R -й орт161 ∈ R Вектор из единиц0, ∈ R× Нулевая матрица0 ∈ R Нулевой векторoZ→0 ( (Z)) «о» малое от функции при Z → 0e, ∈ R× (, )-й матричный орт с 1 на позиции (, )FT Транспонирование матрицы FI ∈ R × Единичная матрица размера × rank F Ранг матрицы Fcolspace F Пространство столбцов матрицы Frowspace F Пространство строк матрицы F Вектор с индексами из множества span(1 , .
. . , ) Линейная оболочка векторов 1 , . . . , othonorm(F) Ортонормализация матрицы F по столбцамG, : Матрица из строк матрицы G с индексами из множества G :, Матрица из столбцов матрицы G с индексами из множества (F)†W = (FT WF)−1 FT W Взвешенная псевдообратная матрицаF† = (F)†I Псевдообратная матрицаΠF,W = F (F)†W Взвешенный проектор на пространство colspace FΠ,W = ΠZ,W Взвешенный проектор на линейное подпространство , где матрица Z содержит произвольный базис 17Π Оператор проектирования на множество -й элемент упорядоченного множества ℱ , ℱ−1 Прямое и обратное дискретное преобразование Фурье * Ациклическая свёртка двух векторов2 = * Ациклическая свёртка вектора c самим собойX * Y Ациклическая свёртка двух матрицcond A Число обусловленности матрицы Atr A След матрицы Adiag(A) Главная диагональ матрицы AdiagA () -я диагональ матрицы Adiag() Диагональная матрица с вектором на главной диагонали⟨, ⟩W = T W Скалярное произведение векторов , по косоугольнойевклидовой норме с весами W‖‖W =√︀⟨, ⟩W Косоугольная евклидова норма⟨X, Y⟩L,R = tr(LXRYT ) Скалярное произведение матриц X, Y по взвешеннойматричной норме с матрицами весов L, R⟨X, Y⟩F = ⟨X, Y⟩I ,I Фробениусово скалярное произведение матриц X, Y‖X‖L,R =√︀⟨X, X⟩L,R Взвешенная матричная норма18Глава 1Сведения из теории временных рядов конечногоранга и теории оптимизации1.1.
Линейные рекуррентные формулыОсновным объектом работы является временной ряд S ∈ R — векторстолбец длины . В дальнейшем, под термином «ряд» будем понимать именновременной ряд. Формально определим упомянутые во введении объекты.Определение 1.1.1. Ряд S имеет ранг , если rank (S) = < /2 длялюбого такого, что min(, − + 1) > , где — оператор вложения,определённый в (2).Определение 1.1.2. Множество рядов ранга :, = = {X ∈ R : rank(+1 (X)) = },где > 2. — замыкание множества по евклидовой норме.Хорошо известно [31], что любой временной ряд вида (1) при достаточно большой длине ряда управляется линейной рекуррентной формулой (ЛРФ)некоторого порядка : =∑︁=1 − , ̸= 0, = 1, .
. . − .(1.1)Один и тот же ряд может управляться многими различными ЛРФ разногопорядка. ЛРФ минимального порядка (при том единственная) называетсяминимальной, при этом соответствующий ей временной ряд имеет ранг . Минимальная ЛРФ вместе с начальными значениями ряда однозначно определяетвид и параметры модели (1).19Равенства (1.1) можно переписать в векторном виде как T +1 (S) = 0T − ,где = ( , . .
. , 1 , −1)T ∈ R+1 . Вектор , соответствующий минимальнойЛРФ, и первые значений ряда S однозначно задают полный временной рядS. Следовательно, коэффициентов ЛРФ порядка и первые значений ряда(вместе 2 параметров) можно выбрать как параметры ряда ранга .Однако эта параметризация не покрывает всё множество [8, Theorem5.1].Давайте обобщим понятие ЛРФ.Определение 1.1.3. Ряд S управляется обобщённой ЛРФ (ОЛРФ) порядка ,+1, ̸= 0+1 .если T +1 (S) = 0T − для некоторой ∈ RТакже мы рассмотрим ОЛРФ минимального порядка. Ключевая разница между ОЛРФ и обычной ЛРФ состоит в том, что последний коэффициентОЛРФ не обязательно ненулевой, соответственно, формула не является «рекуррентной» в прямом смысле, она не обязана выражать последний элементчерез предыдущие.
Тем не менее, по крайней мере один коэффициент ОЛРФдолжен быть ненулевым. Идея использовать произвольный ненулевой вектор для задания соотношения, которому удовлетворяет ряд, используется в работах[16, 17].Определение 1.1.4. Характеристический многочлен ОЛРФ() порядка —∑︀это комплексный многочлен () = =0 +1 , у которого ведущие коэффициенты могут быть нулевыми [8].Сигнальные корни ряда S — корни многочлена (), соответствующегоминимальной ОЛРФ(), которая управляет рядом S.Следующая теорема предъявляет эквивалентный вид ряда, управляемогоОЛРФ() с ненулевыми значениями на краях вектора (что эквивалентноЛРФ с ̸= 0).20Теорема 1.1.1.
[8, Theorem 5.3] Вещественный ряд S = (1 , . . . , )T управляется ОЛРФ(), = (1 , . . . , +1 )T с 1 ̸= 0, +1 ̸= 0 тогда и только тогда,когда S имеет следующий вид: =∑︁ () ,=1где 1 , . . . , — сигнальные корни ряда S с кратностями 1 , . . . , ,∑︀=1 = , () — комплексный многочлен степени , при этом коэффициенты многочленов 1 , . .
. , задаются первыми значениями ряда 1 , . . . , .Введём следующее определение, необходимое для дальнейшей работы.Определение 1.1.5. () = () = {S ∈ R : T +1 (S) = 0T − } —подпространство временных рядов, управляемых ОЛРФ(), ∈ R+1 .Рассмотрим эквивалентный вид (). Под Q, будем обозначать оператор R+1 → R ×( −) , определённый следующим⎛10 ...⎜⎜⎜ 210⎜⎜ ....⎜ ..2⎜⎜....Q, () = ⎜.⎜+1 .⎜.⎜⎜ 0 +1 . .⎜⎜ ....⎜ ..0⎝0 ... 0образом:⎞0.. ⎟⎟.
⎟⎟⎟0 ⎟⎟⎟1 ⎟⎟,⎟⎟2 ⎟⎟.. ⎟. ⎟⎠(1.2)+1где = (1 , . . . , +1 ) ∈ R+1 [32]. Тогда () = () можно представить вдругом виде как() = {S ∈ R : QT ()S = 0 − },где Q = Q, .(1.3)21Будем использовать следующие обозначения: () = colspace(Q()), ипод Z() мы определяем некоторую матрицу, столбцы которой составляют базис ().1.2. Независимость ранга временного ряда от длины окнаДля построения параметризации множества необходимо указать несколько лемм, устанавливающие свойства множества рядов ранга и его замыкания .Предложение 1.2.1. Временной ряд S имеет ранг тогда и только тогда,когда существует , min(, − + 1) > , такое, что rank (S) = .Доказательство. Это следствие из [33, Prop.
5.4].Следствие 1.2.1. Временной ряд S имеет ранг тогда и только тогда, когдаrank +1 (S) = .Замечание 1.2.1. Если временной ряд S имеет ранг , то rank * (S) = *для любого * ≤ .В дальнейшем, когда мы говорим о временном ряде S ∈ и управляющейей ОЛРФ(), мы имеем в виду минимальную ОЛРФ, то есть ∈ R+1 .Таким образом, указанные свойства устанавливают независимость понятия ранга ряда от длины окна при достаточно больших значениях и − + 1.221.3.
Методы оптимизации для нелинейной задачинаименьших квадратов1.3.1. Взвешенный метод Гаусса-НьютонаЗадача (3) взвешенного метода наименьших квадратов (МНК) с матрицейвесов W может быть переписана как общая задача видаarg min ‖ − ( )‖2W ,(1.4)где ∈ R — вектор параметров, : R → R — некоторая параметризация подмножества в R , в котором ищется ближайшая к ∈ R точка, приэтом ( ) — дифференцируемая по функция, W ∈ R × — симметричнаяположительно определённая матрица.Если задача (1.4) нелинейна, то часто используются итеративные методыс линеаризацией на каждом шаге.Определим взвешенную псевдообратную матрицу к F [34]:(F)†W = (FT WF)−1 FT W,(1.5)которая возникает при решении линейной задачи взвешенных наименьших квадратов min ‖Y−F ‖2W с F ∈ R × , так как её решением является * = (F)†W Y.В частном случае W = I (то есть случае обычной псевдообратной матрицы)(F)†I будем обозначать просто как F† .Заодно будем обозначать проектор на линейную оболочку столбцов матрицы F как ΠF,W = F (F)†W .Одна итерация алгоритма Гаусса-Ньютона с шагом выглядит следующим образом:+1 = + (J ( ))†W ( − ( )),где J ( ) — матрица Якоби вектор-функции ( ) в точке .23Выбор шага — отдельная задача.
Например, можно начать с = 1,и уменьшать шаг, если следующее значение хуже текущего (то есть значениефункционала увеличивается).Подробно теория метода Гаусса-Ньютона дана в [35].В нашем случае наибольший интерес в задаче взвешенного метода наименьших квадратов представляет нахождение ( * ), где * — решение (1.4).Рассмотрим метод как последовательность ( ), и мы получаем:(+1 ) = ( ) + (J ( ))†W ( − ( )).(1.6)Следующее замечание объясняет подход, который будет использоваться вглаве 3 в предложенном там модифицированном методе Гаусса-Ньютона.Замечание 1.3.1. Мы можем рассмотреть модификацию метода (1.6) пу̃︀ +1 ), где ‖ − (̃︀ +1 )‖W ≤ ‖ − (+1 )‖W .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
