Автореферат (1150842), страница 3
Текст из файла (страница 3)
Тогда параметризация S(( ) , ( ) ), введённая в теореме 1 — гладкий диффеоморфизм между окрестностью вектора ((S0 )ℐ( ) , (0 )( ) )T ∈R2 и пересечением окрестности S0 с .Таким образом, теорема 2 предъявляет гладкую параметризацию в окрестности S0 , что означает, что множество является гладким многообразием.Далее рассмотрены производные, соответствующие этой параметризации. JS = JS (( ) , ( ) ) ∈ R ×2 обозначает матрицу Якоби отображенияS(( ) , ( ) ).
По определению, касательное подпространство к в точке S —это colspace JS (( ) , ( ) ), где S = S(( ) , ( ) ). Через 2 обозначим ацикличе∑︀min(,+1)(2)(2)скую свёртку самим с собой: 2 = ( ) ∈ R2+1 , = =max(1,−) −+1 .Теорема 3. Касательное подпространство к в точке S, управляемойОЛРФ(), имеет размерность 2 и равно (2 ).11Доказано, что всё множество не является гладким многообразием.Найдены условия локального минимума решения задачи аппроксимации временного ряда рядом конечного ранга (3).В конце главы найден вид ошибок первого порядка по соотношению сигнал/шум при оценивании сигнала проекцией на множество .
Рассмотримслучайный временной ряд S0 +, где сигнал S0 ∈ управляется ОЛРФ(0 ), — случайный вектор, имеющий распределение Ξ, — малое вещественноечисло. Нас интересует распределение оценки сигнала ̂︀S():(S )̂︀S() = Π0 (S0 + ) = S0 + Π(20 ),W () + (),(6)где проектор на линейную оболочку столбцов некоторой матрицы F обозна(S0 )чен как ΠF,W = F (F)+W , Π (X) — проектор на в окрестности точкиS0 .Теорема 4. Пусть S0 ∈ и управляется ОЛРФ(0 ), — случайный вектор, имеющий распределение Ξ.
Тогда имеет место следующая слабая сходимость случайных величин: () ⇒→0 0, где () определена в (6).Таким образом, () представляет из себя малую относительно стремящегося к нулю случайную величину, где задаёт соотношение сигнал/шум.Результаты второй главы опубликованы в работе [3].Третья глава посвящена алгоритмам решения задачи (3). Приведёнвид шага метода Гаусса-Ньютона для решения задачи (3) с помощью прямойподстановки введённой во второй главе параметризации S(( ) , ( ) ) в метод(5), = (( ) , ( ) ).Приведён вид итерации уже известного принципа Variable Projection [13]в обозначениях работы в форме, удобной для реализации и сравнения. Таккак итерация Variable Projection Гаусса-Ньютона (VPGN) является неустойчивой и затратной по времени в ряде случаев, нас интересует построениеиной итерации.
Шаг (5) модернизируется путём замены точки S( ) на болееблизкую к X, что приводит к итерации следующего вида (Модифицированнаяитерация Гаусса-Ньютона, MGN):(+1)( )()T()= ( ) + M+ Q ( )Π((() )2 ),W (X − Π(() ),W (X)),(7)(︀)︀,S=Πгде M = −ST() ),W X , G :, обозначает матрицу, состо+1(( ), :ящую из столбцов произвольной матрицы G с индексами из .
Ключеваяособенность состоит в том, что итерация MGN сводится к вычислению проекторов на () и (2 ), в отличие от итерации VPGN.12С помощью использования преобразования Фурье построены алгоритмы вычисления базисов пространств временных рядов () и (2 ), необходимых в шаге (7), за счёт чего был достигнут выигрыш по трудоёмкостии устойчивости относительно метода VPGN. Обозначим ℱ и ℱ−1 прямоеи обратное дискретное преобразование Фурье длины . Для ℱ () = ,, ∈ C , = (0 , . . . , −1 )T , = (0 , .
. . , −1 )T выполняется =∑︀ −1i2√1=0 exp(− ). При этом доопределим преобразование Фурье от матрицы как ℱ (X) = [ℱ (1 ) : . . . : ℱ ( )], где X = [1 : . . . : ],и ℱ−1 (Y) аналогично. Также определим комплексный многочлен () =∑︀нулевыми, мно=0 +1 , у которого ведущие коэффициенты могут(︀ быть(︀ 2)︀)︀()()жество () = { , = 0, . . . , −1}, где = exp i − , матрицуT () = diag((1, i , . . . , i( −1) ))T , — единичный орт. Ниже приведён алгоритм вычисления матрицы Z(), составленной из базисных векторов ().Алгоритм 1.
Вход: число , вектор коэффициентов ∈ R+1 .1:2:3:4:5:6:Найти 0 = arg max−/ ≤</ min∈() | ()| с помощью одномерногочисленного метода оптимизации.Вычислить вектор = (,0 , . . . , , −1 )T как , = (exp(i( 2 − 0 )), = 0, . . . , − 1.Вычислить матрицы R = ℱ ([ −+1 : . . . : ]), L = A−1 R , гдеA = diag .Найти матрицу U ∈ C × , состоящую из ортонормированных столбцов матрицы L (например, U может состоять из левых сингулярных векторов L ).̃︀ = ℱ −1 (U ).Вычислить Z̃︀ столбцы которой образуют ортоreturn Матрица Z = (T (−0 ))Z,нормированный базис ().Завершается глава сравнением методов VPGN и MGN (7) по временнойсложности. Показано, что для (2 + 1)-диагональной матрицы W, соответствующей процессу авторегрессии порядка (AR()), предложенный методMGN требует ( ( + )2 + log ) времени для итерации, в то время каку VPGN нет быстрой реализации.
Результаты третьей главы опубликованыв работе [3].В четвёртой главе рассматривается матричный подход к решению задачи (3), заключающийся в применении метода Кэдзоу к задаче (4). Доказанасходимость метода Кэдзоу по подпоследовательностям.Получено соотношение между весами W в пространстве временных рядов и матрицами L и R, задающими косоугольное скалярное произведение13в пространстве матриц, для эквивалентности задач (3) и (4). Определимациклическую свёртку двух векторов = * , = (1 , . .
. , )T , =∑︀ . Обозначим -ю диа(1 , . . . , )T , = (1 , . . . , + −1 )T : =,:+−1= ×гональ матрицы A ∈ Rдлины −||, состоящую из элементов с индексами (, ), удовлетворяющих равенству − = , как diagA (), нулевой векторпроизвольной длины как 0 ∈ R .Теорема 5. ‖ (Z)‖L,R = ‖Z‖W для любого временного ряда Z тогда итолько тогда, когда W = L * R, где -я диагональ L * R определена как⎛⎞∑︁ ⎜ 0(||+||−|+|)/2 ⎟diagL*R () =⎝diagL () * diagR ()⎠ ,+=0(||+||−|+|)/2 = −, . . . , .Далее изучен случай, когда ковариационная матрица шума Σ = Σявляется автоковариационной матрицей процесса AR().
К сожалению, ужедля диагонального случая = 0 не существует таких невырожденных L, R,что W(L, R) = L * R была бы равна единичной матрице [15]. Поэтому необходимо поставить задачу поиска L и R, которые бы дали W(L, R), близкуюк W0 = Σ−1 .Для упрощения поиска L, R таких, что W(L, R) ≈ W0 , мы зафиксируем левую матрицу L = Σ−1 равной обратной автоковариационной матрицепроцесса AR(), с теми же коэффициентами, что и у Σ . Задача cформулирована следующим образом:R⋆KL2 = arg min KL2 (Σ , W−1 ),(8)cond R≤1/W=Σ−1 *RR=diag()где 0 < ≤ 1 задаёт ограничение на число обусловленности матрицы R,KL2 — разложение дивергенции Кульбака-Лейблера между многомерныминормальными распределениями с ковариационными матрицами Σ и W−1 вряд Тейлора до второго порядка:1tr(WW0−1 WW0−1 ) − tr(WW0−1 ) + .22Кроме того, введена более простая задача поиска весов по эвклидовой норме:KL2 (N(0, W0−1 )‖N(0, W−1 )) =1‖1 * − 1 ‖2 ,cond R≤1/ 2R⋆dist = arg minR=diag()(9)14где 1 обозначает вектор из единиц.Теорема 6.
Если или = 0, или > 0 и ≥ + − 1, то задачи (8) и(9) эквивалентны, то есть минимум функционалов достигается на однойи той же R.Построена теория эффективного решения задачи (9) с использованиемметода квадратичного программирования и с помощью оптимизации гладкойфункции в параллелепипеде. Предложена быстрая реализация метода Кэдзоус временной сложностью итерации (( log + 1 + 2 ) + (1 + 2 ) ),где матрица L — (21 + 1)-диагональная, R — (22 + 1)-диагональная, = + − 1.В конце главы найден вид ошибок первого порядка при использованииоценки сигнала линеаризацией метода Кэдзоу. Рассмотрим случайный временной ряд X = S0 + , где сигнал S0 ∈ , — случайный вектор с распределением Ξ. Определим матрицу оператора, задающего один шаг линеаризованного метода Кэдзоу, какPS0 = −1 Πℋ Π ( (S0 )) ,(10)где ( (S0 )) обозначает касательное подпространство к пространству ℳматриц ранга в точке (S0 ).Лемма 1.
Пусть S0 ∈ и управляется ОЛРФ(0 ), — случайный вектор с распределением Ξ. Рассмотрим оценку сигнала ̃︀S = PS0 (S0 + ), полученную линеаризованным алгоритмом Кэдзоу в модели X = S0 + , PS0определена в (10). Тогда имеет место следующая слабая сходимость распределений:̃︀S ⇒→+∞ S0 + Π(20 ),W(L,R) .(11)Результаты четвёртой главы опубликованы в работaх [1, 2, 4].В пятой главе проведены численные эксперименты. Показано, что построенная итерация метода Гаусса-Ньютона MGN (7) обладает большей устойчивостью, чем шаг VPGN при вычислении точки локального минимума.
Спомощью статистического моделирования подтверждены результаты о величине ошибок первого порядка для проекции на множество временных рядовранга и линеаризованного метода Кэдзоу. Приведены примеры примененияметода модифицированного метода Гаусса-Ньютона MGN к данным экспрессии генов и к временному ряду с неизвестной ковариационной матрицей шума.15В Заключении подведены основные итоги диссертационной работы.Отмечено, что в диссертации были предложены новые методы для решенияшироко используемых на практике задач оценки сигнала и его параметровв классе сигналов конечного ранга.
Перечислены ключевые результаты. Аименно, указано, что получено теоретическое обоснование модифицированного метода Гаусса-Ньютона и метода Кэдзоу для решения задач (3) и (4),а также их свойств, построены эффективные (быстрые и устойчивые) реализации. Это позволяет существенно расширить круг решаемых проблем наслучай авторегрессионного шума и улучшить точность их решения.Список публикаций1. Звонарев Н.
К. Поиск весов в задаче взвешенной аппроксимации временным рядом конечного ранга // Вестник Санкт-Петербургского университета. Серия 1. Математика. Механика. Астрономия. 2016. Т. 3, № 4.2. Zvonarev N., Golyandina N. Iterative algorithms for weighted and unweightedfinite-rank time-series approximations // Statistics and Its Interface. 2017.Vol. 10, no. 1. P.
5–18.3. Zvonarev N., Golyandina N. Modified Gauss-Newthon method in low-ranksignal estimation. arXiv:1803.01419.4. Звонарев Н., Голяндина Н. Итеративные алгоритмы взвешенной аппроксимации рядами конечного ранга // System Identification And ControlProblems. SICPRO’15. 2015. P. 1371–1394.Цитированная литература5. Cadzow J. A. Signal enhancement: a composite property mappingalgorithm // IEEE Trans. Acoust. 1988. Vol. 36, no.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
