Диссертация (1150844), страница 12
Текст из файла (страница 12)
Известно, что обратная к Σ матрица W0 = Σ−1 — (2 +1)-диагональная [49]. Поэтому нам интересен случай (2 + 1)-диагональной W.81Приведём очевидные следствия из теоремы 4.2.1.Следствие 4.2.1. Рассмотрим матрицы L ∈ R× , R ∈ R× и W такие,что ‖ (Z)‖L,R = ‖Z‖W для любого Z. Пусть L будет (21 + 1)-диагональной,и R — (22 + 1)-диагональной. Тогда матрица весов W = L * R — (2 +1)-диагональная, где = 21 + 22 + 1 и -я диагональ diagW (), = −, . .
. , ,задана в (4.5).Важный частный случай — (2 + 1)-диагональная L и диагональная R,т.е. 1 = , 2 = 0.Следствие 4.2.2. Рассмотрим (2+1)-диагональную матрицу L и диагональную R = diag(). Тогда матрица весов W является (2 + 1)-диагональной,где diagW () = diagL () * , = −, . . . , .4.2.2. Эквивалентные формулировки задачи поиска весовНас интересует следующий вопрос: можно ли подобрать подходящие L иR для заданной обратной автоковариационной матрицы W0 = Σ−1 процессаавторегрессии порядка с коэффициентами 1 , . . . , так, что W0 = L * R.Тогда было бы возможно решать задачу (3) с весами, соответствующими авторегресcионному шуму, методами решения задачи (4).К сожалению, уже для диагонального случая = 0 не существует такихневырожденных L, R, что W(L, R) = L * R = I [23].
Поэтому необходимопоставить задачу поиска L и R, которые бы дали W(L, R), близкую к Σ−1 .Рассмотрим разумную меру между обратной ковариационной матрицейW0 = Σ−1 и матрицей весов W, которая не зависит от вида сигнала или егоранга. В качестве такой меры мы выбрали дивергенцию Кульбака-Лейблера[50] между многомерными нормальными распределениями с нулевыми средними и ковариационными матрицами Σ и W−1 . По определению, дивергенция82выглядит следующим образом [51]:KL (N(0 , W0−1 )‖N(0 , W−1 )) =)︀1 (︀tr(WW0−1 ) − − log(det(WW0−1 )) .2Тем не менее, данную формулу трудно использовать на практике из-за вычислительной сложности задачи её минимизации. Поэтому мы перепишемlog(det(WW0−1 )) = tr(log(WW0−1 )),и разложим log(WΣ) в ряд Тейлора в окрестности точки I до второго члена.Получим разложение дивергенции Кульбака-Лейблера второго порядка [52]:KL2 (N(0 , W0−1 )‖N(0 , W−1 )) =1tr(WW0−1 WW0−1 )−tr(WW0−1 )+ .
(4.6)22Для краткости, будем обозначать KL2 (N(0 , W0−1 )‖N(0 , W−1 )) какKL2 (W0−1 , W−1 ).Так как задача минимизации KL2 (W0−1 , W−1 ), где W = W(L, R), одновременно по L и R достаточно сложна, мы ограничимся случаем фиксированной матрицы L и поставим условие на невырожденность R. Мы ограничим еёчисло обусловленности cond R ≤ 1/, 0 < ≤ 1.В качестве матрицы L выберем L = Σ−1 — обратную автоковариационнуюматрицу процесса авторегрессии длины с теми же коэффициентами 1 , .
. . , ,что и у L = Σ−1 . Соответственно, по следствию 4.2.2, R ищется среди диагональных матриц.Замечание 4.2.1. Выбор L имеет следующее объяснение. В случае = 0 матрица L пропорциональна I , то есть эта матрица является наименее обусловленной среди матриц размера ×.
Более того, известно, что если кратно, то без ограничения на число обусловленности матрицы R = diag() можно добиться равномерных весов W0 = I [23]. При этом, согласно следствию4.2.2, задачу подбора весов можно представить как подбор такого вектора ,что 1 * ≈ 1 .83Если же рассмотреть случай > 0, то согласно [49] мы получим похожее соотношение для каждой из 2 + 1 диагоналей, лишь за исключением − значений на крае. Например, при = 1 с точностью до умножения на константу выполнено: diagΣ−1(0) = (1, 1 + 21 , . .
. , 1 + 21 , 1)T ∈ R ,(1) = (−1 , . . . , −1 )T ∈diagΣ−1(0) = (1, 1 + 21 , . . . , 1 + 21 , 1)T ∈ R , diagΣ−1R −1 , diagΣ−1(1) = (−1 , . . . , −1 )T ∈ R−1 , при этом мы хотим получитьdiagΣ−1(0) ≈ diagΣ−1(0) * , diagΣ−1(1) ≈ diagΣ−1(1) * .−1Таким образом, мы ставим задачу поиска весов для W0 = Σ−1 , L = Σв следующем виде:R⋆KL2 = arg min KL2 (Σ , W−1 ).(4.7)cond R≤1/W=Σ−1 *RR=diag()Заметим, что если шум белый, то автоковариационная матрица Σ пропорциональна единичной, и задача сводится к задаче минимизации евклидовогорасстояния между диагоналями матриц W0 и W, что приводит к следующейпостановке:1‖1 * − 1 ‖2 .cond R≤1/ 2R⋆dist = arg min(4.8)R=diag()Оказывается, задачи (4.7) и (4.8) эквивалентны во многих случаях, достаточно лишь, чтобы было немногим больше половины длины ряда .
Будемобозначать под 0, нулевую матрицу размера × .Теорема 4.2.2. Если или = 0, или > 0 и ≥ + − 1, то задачи (4.7) и(4.8) эквивалентны, то есть минимум функционалов достигается на однойи той же R.Доказательство. Так как условия на R в (4.7) и (4.8) совпадают, достаточнодоказать, что минимизируемые функционалы в (4.7) и (4.8) — одна и та же84квадратичная функция. Перепишем 1 * = Q, (1 ), где Q, определенов (1.2), и раскроем (4.8). Получим11‖1 * − 1 ‖2 = T S − 1T, +222(4.9)где S = (, ), , = − | − |, если | − | ≤ , и , = 0 в противном случае.∑︀Для того чтобы раскрыть (4.7), введём разложение W = =1 W таким же способом, которым это было сделано в предложении 4.2.1, с , = иW, = W :KL2 (W0−1 , W−1 ) =∑︁1 ∑︁ ∑︁−1−1= tr(W W0 W W0 ) − tr(W W0−1 ) + .
(4.10)2 =1 =12=1Представим W и W0−1 = Σ = Σ в виде блочных матриц (заметим, чторазмер блока зависит от ):⎛⎞00−1, 0−1,−⎜ −1,−1⎟⎜⎟−1W = ⎜ 0,−1Σ0,− ⎟ ,⎠⎝0−,−1 0−, 0−,−⎛⎜⎜Σ=⎜⎝Σ−1ΣleftΣtopΣΣbottomleft ΣbottomΣtoprightΣrightΣ−⎞⎟⎟⎟.⎠Обозначим значение автоковариационной функции процесса AR(p) с коэффициентами 1 , . . . , с лагом ; − = .
Тогда Σ = (− ). Также обозначим = (+−1 , . . . , )T ∈ R . Заметим, что Σ = [−+1 : . . . : 0 ], Σright =∑︀[1 : . . . : − ]. Из уравнений Юла-Уолкера [53] следует, что = =1 − ,∑︀ ≥ 1. Таким образом, = =1 − , = 1, . . . , − . В итоге, мы получили, что colspace Σright = span(1− , .
. . , 0 ). По аналогии и симметрии, имеемcolspace Σleft = span(−+1 , . . . , −+ ).85Произведение W и W0−1 = Σ имеет следующий вид:⎛⎞00−1, 0−1,−⎜ −1,−1⎟⎜ −1⎟−1−1W W0 = ⎜Σ ΣleftIΣ Σright ⎟ ,⎝⎠0−,−1 0−, 0−,−при этом выполняются соотношенияcolspace Σ−1 Σleft = span(1 , . . . , ),colspace Σ−1 Σright = span(−+1 , .
. . , ).Это означает, что только первые строк Σ−1, Σleft и только последние строкматрицы Σ−1, Σright ненулевые.Вернёмся обратно к разложению (4.10). Очевидно, что tr(W W0−1 ) = для любого = 1, . . . , . Равенствоtr(W W0−1 W W0−1 ) = ⟨W W0−1 , (W W0−1 )T ⟩Fозначает, что результат зависит от того, как перекрываются ненулевые частиW W0−1 и (W W0−1 )T , см. рисунок 4.1.
Когда ≥ + − 1, ненулевые части−1−1−1 TΣ−1 Σleft и Σ Σright внутри W W0 и (W W0 ) не перекрываются для любых1 ≤ , ≤ . Следовательно, tr(W W0−1 W W0−1 ) = , .В случае = 0, Σleft = 0,−1 и Σright = 0,− , мы получаемtr(W W0−1 W W0−1 ) = , для любого .Следовательно, мы доказали, что правая часть выражения (4.9) совпадаетс правой частью (4.10).Так как задачу (4.7) трудно решать, мы используем задачу (4.8) для нахождения весов для любого . В теореме 4.2.2 показано, что функционал (4.8) квадратичный. Следовательно, с добавлением вспомогательной переменной, задача(4.8) может быть решена, используя методы квадратичного программирования,что показано в разделе 4.3 и [27].86k−1pp1p1Σ−1L ΣrightΣ−1L Σlef t1111pi−1L1p1j−1K −k1pРис.
4.1. Схематичные изображения матрицы W W0−1 (слева) и перекрывающихся матрицW W0−1 и (W W0−1 )T (справа).4.3. Применение квадратичного программирования кпоиску весовВ этом разделе мы рассмотрим алгоритм решения задачи поиска весов(4.8). Будем считать, что < 1 в (4.8), так как случай = 1 тривиален (вектор состоит из одинаковых значений).4.3.1. Эквивалентные формулировкиПреобразуем задачу (4.8): множество ℛ = { : cond(diag R) ≤ 1/} из(4.8) запишем в виде набора линейных ограничений, а в эквивалентной целевойфункции (4.9) опустим константный член.
Получим следующую эквивалентнуюформулировку:Задача 4.3.1. ⋆ = min (),∈ℛ1где () = T S − 1T ,2ℛ = { | − ≥ 0, ̸= ,1 ≤ , ≤ } ,(4.11)(4.12)87где S = (, ), , = − | − | если | − | ≤ , и 0 в противном случае,1 = (1, . . . , 1)T , 1 ∈ R .Теперь задача 4.3.1 представлена в том виде, для которого разработанатеория квадратичного программирования (КП) [54, p.
111]. Справедливо следующее:Предложение 4.3.1.1. Задача 4.3.1 имеет единственное решение ⋆ .⋆ T) является палиндромом, то есть для лю2. Её решение ⋆ = (1⋆ , . . . , ⋆.бого индекса 1 ≤ ≤ : ⋆ = −+1Доказательство.1. Задача 4.3.1 — задача КП с набором из 2 линейныхограничений (4.12) и целевой функцией (4.11), квадратичная форма вкоторой положительно определена, поэтому решение такой задачи единственно [35, p. 452].⋆2.
Достаточно рассмотреть вектор ⋆⋆ = (, . . . , 1⋆ ) и заметить, что (⋆ ) = (⋆⋆ ) и ⋆⋆ ∈ ℛ в (4.12); значит, ⋆ = ⋆⋆ , что и требовалось доказать.Для решения задачи 4.3.1 можно использовать методы квадратичного программирования, но, к сожалению, 2 линейных ограничений являются серьёзной проблемой при решении задачи на практике. Рассмотрим ещё две эквивалентных формулировки, свойства которых используются при решении задачи.Сделаем дополнительное предположение: пусть в точке веса достигаютсвоего максимума (тем самым, снизим число линейных ограничений до линейного по размера), а само будем перебирать в цикле от 1 до ⌈/2⌉. При этомвоспользуемся тем фактом, что решение является палиндромом. Формально,задача выглядит следующим образом:88Задача 4.3.2.
⋆⋆ =min=1,...,⌈/2⌉⋆ ,(4.13)⋆ = min (),(4.14){︀ℛ = | = −+1 , = 1, . . . , ⌈/2⌉;(4.15) − ≥ 0, = 1, . . . , − 1, + 1, . . . , ⌈/2⌉;}︀ − ≥ 0, = 1, . . . , − 1, + 1, . . . , ⌈/2⌉(4.16)∈ℛ(4.17).Чтобы не перебирать все возможные , удобно уметь проверять, даёт липолученное на очередной итерации решение глобальный минимум. Для такойпроверки рассмотрим ещё одну эквивалентную формулировку задачи 4.3.1. Введём max — дополнительную переменную, хранящую максимальный вес, и перейдём к новым переменным ^ = max − , = 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
