Диссертация (1150844), страница 4
Текст из файла (страница 4)
Этотём замены (+1 ) на (̃︀ +1 ) вычисляется быстрее и/или устойчиоправдано в том случае, если (вее, чем (+1 ).1.3.2. Принцип Variable projection⎛ ⎞Пусть = ⎝ ⎠ ∈ R , ∈ R1 , ∈ R2 , 1 + 2 = . Тогда задачу(взвешенного) метода наименьших квадратов (1.4) с( ) = G(),(1.7)где G : R1 → R ×2 — гладкая функция, можно рассмотреть как задачу проектирования вектора данных на заданное множество:⎛ ⎞min ‖ − ‖2W с = {G()| ⎝ ⎠ ∈ R }. ∈24Под обозначением {() | ∈ } подразумевается множество значений ()для ∈ . Воспользуемся тем, что нам известно решение подзадачи * () = arg min ‖ − G()‖2W ,а именно * () = (G())†W .Обозначим * () = G() * (), () = {G()| ∈ R2 }. Отсюда следует, что * () = arg min ‖ − ‖2W .(1.8)∈()Таким образом, мы можем свести задачу к проекции на подмножество* ⊂ и тем самым к задаче минимизации только по части параметров, входящих в ( ) нелинейно:min* ‖ − ‖2W c * = { * ()| ∈ R1 }.
∈(1.9)Этот подход называется принципом «Variable projection» (см. [36] для случая евклидовой нормы).1.3.3. Принцип Variable projection в задаче аппроксимации рядомконечного рангаВ [16, 17] применением принципа Variable projection была получена следующая эквивалентная (3) задача проекции на подмножество * ⊂ :Y* = arg min ‖X − Y‖W где * = {Π(),W X| ∈ R+1 },Y∈*что было переписано в виде задачи поиска ОЛРФ, управляющей рядом S* :* = arg min ‖X − S* ()‖W ,∈где S* () = Π(),W (X), при этом рассматривались следующие варианты :единичная -мерная сфера [16] и -мерное аффинное многообразие [17]. Полученная минимизационная задача решалась различными методами, в частности,25методом Гаусса-Ньютона. В удобных для данной работы терминах этот подходрассмотрен в главе 3.Ниже приведена таблица обозначений этой работы и обозначений работ[16, 17], которая может быть удобна для сопоставления методов.Таблица 1.1.
Соответствие обозначенийЭта работаX + 1 1 − W Γ()Usevich & Markovsky Γ1.4. Непараметрический метод КэдзоуОдин из стандартных численных методов решения задачи (4) — методитераций Кэдзоу [1], принадлежащий классу методов попеременных проекций.Определим следующую последовательность матриц, начинающуюся с заданнойматрицы X:X0 = X,X+1 = Πℋ Πℳ X , ≥ 0,где Πℋ и Πℳ — проекторы на соответствующие множества по норме ‖ · ‖L,R .Изначально метод рассматривался только для случая фробениусовскойнормы ‖ · ‖F = ‖ · ‖I ,I . Первые обобщения на случай диагональных матриц L,R вместе с методами их подбора для соответствия задач (3) и (4) при W = Iразобраны в [22].
Доказательство сходимости метода Кэдзоу по подпоследовательностям для случая фробениусовской нормы приведено в [1].Решение задачи (4) не всегда можно использовать для (3). Известно, чтодаже в случае диагональной матрицы W = I , не существует положительноопределённых диагональных матриц L и R таких, что ‖ (Z)‖L,R = ‖Z‖W длялюбого Z [37]. Таким образом, при использовании метода Кэдзоу для решениязадачи (3) необходимо решать задачу подбора матриц L и R, приближённодающих требуемую норму.261.5. Метод квадратичного программирования «Active Set»Для решения задачи поиска весов, использующихся в алгоритме Кэдзоу,используется так называемый «Primary Active Set» метод решения задач квадратичного программирования, описанный в [35].В общем случае, задача квадратичного программирования выглядит следующим образом:Задача 1.5.1.1min T G − T ,∈ 2{︀ = | T ∈ ; = ,}︀T≥,∈,(1.10)(1.11)где G ∈ R× — произвольная положительно определённая матрица, ∈ R— произвольный вектор, и — множества индексов, вектора ∈ R вместес ∈ R задают ограничения.Суть любого «Active Set» метода состоит в последовательном перебореподмножества ограничений, которые выполняются как равенство для промежуточной точки-кандидата в решение задачи квадратичного программирования.
Такое множество называется рабочим множеством, и обозначается, как ⊂ ∪ , при этом всегда ⊂ , а ограничения, лежащие в рабочем множестве, называются активными. Ниже представлена схема этого метода длярешения задачи 1.5.1.Алгоритм 1.5.1 ([35], стр. 472). Вход: параметры задачи квадратичного программирования: матрица G, вектор , множества , и коэффициентыусловий , .1:Найти начальную точку 0 , удовлетворяющую условиям задачи (1.10),(1.11), и положить 0 — множество активных ограничений в этой точке.272:Положить = 03:Положить = − G4:Решить подзадачу квадратичного программирования и найти множители Лагранжа , ∈ :1⋆ = arg min T G − T , ∈ 2(1.12) = { | T = 0,(1.13) ∈ },после чего находятся из системы уравнений5:6:∑︀∈if ⋆ = 0 , и все ≥ 0, ∈ ∩ thenreturn ⋆ = — решение задачи 1.5.1.7:end if8:if ⋆ = 0 , но существует такое, что < 0 then9: = G⋆ − .Взять = arg min∈ ∩ , положить +1 = ∖ {}, увеличить на единицу и перейти к п.
3.10:end if(︁ −T ⋆ <0 = min 1, min∈⋆/ , TT +1 = + ⋆ .11:Положить12:Положить13:if < 1 thenT14:16:. − ⋆Положить = arg min∈и +1 = ∪ {}./ , TT ⋆ <015:)︁elseПоложить +1 = .17:end if18:Положить = + 1 и перейти к пункту 3.28Глава 2Свойства задачи аппроксимации временныхрядов рядами конечного ранга2.1. Необходимые свойства и Для построения параметризации необходимо доказать несколько лемм,устанавливающих свойства множества рядов ранга и его замыкания .Предложение 2.1.1.
S ∈ тогда и только тогда, когда S управляетсяминимальной ОЛРФ(), ∈ R*+1, * ≤ .Доказательство. Доказательство проведём в два шага. Первый — мы покажем, что из того, что S ∈ , следует, что S управляется минимальной ОЛРФпорядка не больше . Второй шаг — мы покажем, что любой ряд, управляющийся ОЛРФ порядка не больше − 1, можно сколь угодно близко приблизитьрядом из , что означает, что он лежит в .Рассмотрим множество матриц ℳ ⊂ R× ранга, не превышающего , имножество ℳ= матриц ранга ровно , где мы полагаем = +1, = −+1.Известно, что замыкание ℳ= = ℳ , см.
[38]. Равенство −1 (ℳ= ∩ ℋ) = выполняется по определению множества 1.1.2 и следствию 1.2.1. Следовательно, = −1 (ℳ= ∩ ℋ) = −1 (ℳ= ∩ ℋ) ⊂ −1 (ℳ= ∩ ℋ) = −1 (ℳ ∩̂︀ . Получаем, что ̂︀ = {X : rank +1 (X) ≤ }. По предложению 1.2.1ℋ) = ̂︀ = ⋃︀ . Первый шаг завершён.получаем, что ⊂ 0≤≤̂︀ . Нам необходимо покаПерейдём ко второму шагу: докажем, что = ̂︀ временным рядом X ∈ зать, что мы можем приблизить любой ряд S ∈ с произвольной точностью. Для этого достаточно показать, что мы можем аппроксимировать S ∈ * с помощью X ∈ * +1 сколь угодно близко, * + 1 ≤ ,29а затем продолжить процесс по индукции, если это необходимо.Пусть S управляется ОЛРФ(* ), * ∈ R*+1, * = (1 , .
. . , * +1 )T . Мыстроим линейно независимых экспоненциальных рядов S длины , S =( , 2 , . . . , )T , управляемых ОЛРФ( ), = ( , −1)T , где все различны, и выбираем ряд S* , который не управляется ОЛРФ(* ). Тогда длялюбого положительного сколь угодно малого числа мы получаем X() =̂︀* +1 , так как ряд X() управляется ОЛРФ(* ), * = (* 1 , * 2 −S+S* ∈ 1 , * 3 − 2 , .
. . , * * +1 − * , −* +1 )T ∈ R*+2.̂︀* , что означает, что X() ∈ * +1 .Давайте теперь покажем, что X() ∈/Согласно замечанию 1.2.1, достаточно показать, что rank * +1 (X()) = * +1. Известно, что rank * +1 (S* ) = 1. Более того, заметим, что вектор ∈colspace * +1 (S) тогда и только тогда, когда T * = 0, и ∈ rowspace * +1 (S)тогда и только тогда, когда T Q −*,*(* ) = 0T −2 .Нам известно, что ( * )T * ̸= 0, и ( * )T Q −*,**(* ) ̸= 0T −2 , где — произвольный столбец матрицы * +1 (S* ), * — произвольный столбец матрицыT* +1 (S* ). Следовательно,rowspace * +1 (S) ∩ rowspace * +1 (S* ) = ∅,colspace * +1 (S) ∩ colspace * +1 (S* ) = ∅.По [39, Theorem 2] мы получаем rank * +1 (X()) = * + 1.
Доказательствопредложения завершено.Замечание 2.1.1. Для комплексного случая данное предложение было доказано в [40, Remark 1.46].Это предложение означает эквивалентность определения как замыкания и как множества рядов ранга не более в постановке задачи (3).Нам потребуются следующие свойства:30∙ Согласно следствию 1.2.1 и замечанию 1.2.1, Y ∈ тогда и только тогда,когда существует ОЛРФ() порядка , которая управляет Y.∙ = {Y : ∃ ∈ R+1 , ̸= 0+1 : T +1 (S) = 0T − }, т.е.
Y ∈ эквивалентно существованию ОЛРФ() порядка , которая управляет Y. Этосвойство следует из предложения 1.2.1 и предложения 2.1.1. Более того,⋃︀это означает, что =(), где () — подпространство рядов,̸=0+1управляемых ОЛРФ().2.2. Параметризация множества 2.2.1. Конструкция параметризацииРассмотрим временной ряд S0 ∈ , управляемый минимальной ОЛРФ(0 )(0)(0)порядка , заданной ненулевым вектором 0 = (1 , . . . , +1 )T . Рассмотрим ин(0)декс такой, что = −1.
Если ОЛРФ(0 ) ненулевая, то перенормировкойвектора 0 такой индекс всегда можно найти, так как ОЛРФ(0 ) инвариантнаотносительно умножения на константу. Давайте рассмотрим параметризацию,которая будет зависеть от индекса .Вместо значений в начале ряда, то есть начальных данных, которыерассматриваются в случае обычной ЛРФ, мы рассмотрим − 1 значений вначале, и + 1 − значений в конце ряда. Определим ℐ( ) = {1, . . . , } ∖{, . . . , − − 1 + } и ( ) = {1, . . . , + 1} ∖ { } — два множества индексовразмера .
Множество ℐ( ) содержит индексы элементов ряда (которые мыназовём краевыми значениями), которых достаточно для того, чтобы найти всеэлементы ряда при помощи ОЛРФ() (или, если точнее, с помощью элементов с индексами из ( )).Пусть G, : обозначает матрицу состоящую из строк G с индексами из , аG :, — матрицу, состоящую из столбцов матрицы G с индексами из . В случае31векторов обозначает вектор, состоящий из элементов вектора с номерамииз .Например, Zℐ( ), : ∈ R× обозначает матрицу, состоящую из строк матрицы Z ∈ R × с номерами из ℐ( ), ( ) ∈ R обозначает вектор состоящий изэлементов вектора ∈ R+1 под номерами из ( ).Следующая теорема определяет параметризацию, которая будет использоваться далее в работе.
Начиная с текущего момента одно и тоже обозначение Sбудет использоваться как параметризующее отображение, так и как временнойряд.Теорема 2.2.1. Пусть S0 ∈ — ряд, управляемый ОЛРФ(0 ), где 0 ∈ R+1 ,(0) = −1. Между окрестностью точки ((S0 )ℐ( ) , (0 )( ) )T ∈ R2 и пересечением окрестности точки S0 со множеством единственным образом определено взаимно-однозначное отображение S : R2 → , которое строит повектору параметров (( ) , ( ) )T ряд S, и удовлетворяет следующим условиям для S = S(( ) , ( ) ): (S)ℐ( ) = ( ) , S ∈ и управляется ОЛРФ() такой,что ( ) = ( ) и = −1.Предъявим явно такое отображение S, которое удовлетворяет упомянутымв теореме 2.2.1 свойствам, тем самым, докажем заодно и теорему 2.2.1.(0)Предложение 2.2.1. Пусть 0 ∈ R+1 , = −1, Z0 ∈ R × — матрица, столбцы которой составляют базис пространства рядов, управляемыхОЛРФ(0 ).1. Рассмотрим (( ) , ( ) )T ∈ R2 , и определим такое , что ( ) = ( ) , = −1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
