Усевич Константин Дмитриевич АНАЛИЗ СИНГУЛЯРНОГО СПЕКТРА В ЗАДАЧАХ ОБРАБОТКИ ВРЕМЕННЫХ И ПРОСТРАНСТВЕННЫХ ДАННЫХ



Название:
Усевич Константин Дмитриевич АНАЛИЗ СИНГУЛЯРНОГО СПЕКТРА В ЗАДАЧАХ ОБРАБОТКИ ВРЕМЕННЫХ И ПРОСТРАНСТВЕННЫХ ДАННЫХ
Альтернативное Название: Усевич Костянтин Дмитрович АНАЛІЗ сингулярного СПЕКТРУ В ЗАДАЧАХ ОБРОБКИ ТИМЧАСОВИХ І ПРОСТОРОВИХ ДАНИХ Usevich Konstantin Dmitrievich ANALYSIS OF THE SINGULAR SPECTRUM IN TASKS OF PROCESSING TIME AND SPATIAL DATA
Тип: Автореферат
Краткое содержание: Основными объектами исследования являются временные ряды FN =
(/О, • • • , /лГ-l) Є CN И Двумерные МаССИВЫ F = (/m,n)m*n=6 "~ , fm,n Є С.
Рассмотрим базовый метод АСС для временных рядов. Пусть ряд явля-ется суммой компонент различной структуры F = F^ + ... + F^r>. На шаге вложения по ряду F/v и длине окна L составляется L-траекторная матри¬ца ряда, столбцами которой являются скользящие отрезки ряда длины L:

X = X

/ /о h h • • • Ік-і \ h /2/3 • • • /к
\ fb-l fb fb+1 ■ ■ ■ /лг-1 I

(і:

б

Траєкторная матрица имеет одинаковые значения на антидиагоналях, т.е. является ганкелевой матрицей. Затем производится сингулярное разложе¬ние (SVD) траекторной матрицы
d
X = $>tW, (2)
з=і
где (Т\ > ... > ad > 0 — сингулярные числа, a {Uj}d-=l и {Vj}dj=i — левые и правые сингулярные векторы, называемые также собственными и фактор-ными векторами. Набор (O~J}UJ}VJ) называется j-u собственной тройкой. Собственные векторы образуют базис пространства столбцов матрицы X,
£ (FN) = span(X), называемого траекторным пространством.
С помощью задания группировки, т.е. разбиения набора собственных троек на г групп {1,..., d] = J\ U ... U Jr, определяется разложение
х = £xJfc,
k=l где Xj = Yl \/\jUjV*. Посредством диагонального усреднения матрицы Xjk преобразуются в восстановленные ряды F^k>, что приводит к разложению
г
F = VF(fc). k=i
В теории метода АСС основным является вопрос о нахождении условий разде¬лимости компонент в исходной сумме F = F^l> -К .. + F^r\ т.е. возможности с помощью АСС найти восстановленные ряды F^k\ хорошо аппроксимиру¬ющие F^k\ или базисы {Uj}jGjk подпространств, аппроксимирующих траек¬торные пространства £(L)(FW). Кроме того, важна идентифицируемость компонент, т.е. возможность различить соответствующие собственные трой¬ки после шага разложения в методе АСС, для чего, в частности, количество собственных троек, соответствующих компоненте, должно быть небольшим и одинаковым для различных размеров окна. Идеальной моделью таких рядов являются ряды, траекторные матрицы которых имеют малый, не зависящий от размеров окна ранг, так называемые ряды конечного ранга.
Во введении обосновывается актуальность диссертации, формулируют¬ся цели и задачи работы, кратко описывается структура диссертации.
Глава 1 содержит обзор теории и основных понятий метода АСС. Вво-дятся определения, описываются модели и задачи, рассматриваемые в рамках данной диссертации.
7

Первый раздел посвящен описанию базового метода АСС в комплексном варианте и обсуждению основных шагов алгоритма.
Второй раздел посвящен краткому обзору модели рядов конечного ранга. Ряд F/v Є CN называется рядом конечного ранга d) если ранг У^ь"> равен некоторому числу d < N/2 для любых L, dР-\
fn+p = 2_^ akfn+k (3)
k=0
для 0Третий раздел посвящен понятию разделимости рядов в методе АСС. Два ряда
F(D и F(2)
называются слабо L-полураз делимыми, если пространства столбцов их траекторных матриц ортогональны £(L\F^) _L C^^F^). Если
к тому же
£W(F«)±£W(F(2))
d\ d,2
3=1 3=1
х = Xl + x2 = Y, o,v?\v$l)Y + £ ajvpiyj
, то ряды называются слабо Ь-разделимыми. Ряды слабо L-разделимы тогда и только тогда, когда сумма сингулярных раз¬ложений траекторных матриц отдельных рядов
является сингулярным разложением матрицы X. В разделе также приводят¬ся основные сведения о точной и приближенной разделимости [6].
В четвертом разделе содержится обзор теории бесконечных рядов, удовле¬творяющих ЛРФ. Ряд Foo = (/о, • • •, /п, • • •)> /п є £, гДе £ — поле> Удовле¬творяет ЛРФ (3), если равенство (3), при ао,... ,ар-і Є /С, выполняется для
всех п Є No = N U {0}. Каждой ЛРФ (3) сопоставляется характеристиче-
p~l k ский многочлен A{z) = zp — ^2 ct,kZ ■ Существует минимальный многочлен
k=0
P{z) = pdZd + ... +p\Z +po, такой что характеристический многочлен любой ЛРФ делится на P(z). Известно, что в случае комплексного поля, К, = С, такие ряды имеют единственное представление
т v§ — \
/п = ^адп)А£ + ^>ад, (4)
k=l j=0
где Qk — ненулевые многочлены степени Vk~ 1, Cj — комплексные константы, cVo-\ Ф 0, 5j(n) — символ Кронекера, т.е. 5j(n) = 1 если п = j и Sj(n) = 0

иначе. При этом А& являются корнями P(z) с кратностями z/&, щ — кратность корня 0, и VQ + . . . + vm = d. Для вещественнозначных рядов представление (4) соответствует сумме произведений полиномов, экспонент и косинусов. Если <2о 7^ 0 или5 чт0 т0 же самое, щ = 0, ряд F^ называется реверсивным рядом размерности d. Конечный отрезок F/v такого ряда i7^ называется реверсив¬ным рядом размерности d, если N > 2d.
В пятом разделе рассматриваются методы прогнозирования компонент разложения в методе АСС. Пусть FN = Fjy + ідг , компонента F^ явля¬ется реверсивным рядом размерности d и имеет представление (4), а также d < L < N — d+1. Тогда по подпространству Л = spanjL^,..., Ujd} Є CL, со-ответствующему компоненте F^r В разложении, если е^ = (0,..., 0,1)т ¢. Л, коэффициенты ао,... ,аь-2 ЛРФ прогноза определяются с помощью проек¬ции еь на сопряжение ортогонального дополнения R = A_L подпространства:
(&о,---A-i) = nReL
Т _ (и h \Т
(а0,... ,аь-г) = (6о, •--,^-2)/(-^-1)-
В случае точной разделимости, когда JC(F^ ) = А, корнями характери-стического многочлена A(z) ЛРФ прогноза являются d корней минимально¬го многочлена P(z) и L — d — 1 побочных корней. В случае приближенной разделимости корни A(z) являются приближениями корней минимального многочлена и побочных корней, что позволяет использовать ЛРФ прогноза
77(1)
для оценки параметров ряда г^.
В шестом разделе описываются модификации метода АСС. Рассматрива-ются некоторые методы оценки параметров сигналов. Подробно обсуждается модификация метода АСС над конечным полем для анализа категориальных данных. В рамках этой модификации ставится задача о нахождении вероят-ности случайной классификации с точностью до инверсии. Пусть на некото-ром вероятностном пространстве (Г2, J7, Р) заданы случайные вектор V Є F2 и случайная ганкелева L х К матрица с элементами из F2, независимые и имеющие равномерное распределение. Требуется найти вероятность
FT1(0) = Р(У Є span(X) или V + 1L Є span(X)),
где її = (1,..., 1)т. Эту вероятность можно выразить как
FT1(0) = 2Р(У Є span(X)) - P(1L Є span(X) и V Є span(X)),
и для нахождения каждого из слагаемых достаточно найти величины
Г^хК = #{Х Є fiLxK : rankX = г},
Г^*'1 = #{Х Є fiLxK : rankX = г, 1L Є span(X)},
9

где S)LxK — множество ганкелевых матриц размера L х К.
В седьмом разделе описывается двумерный вариант метода АСС [2]. Для
двумерного массива данных (матрицы) F = (fn,m)nxm=o v (Lx, Ьу)-траектор-ная матрица W = W^'1^ формируется по двумерному скользящему окну размера LxxLy. Столбцы W (векторы вложения) являются векторизациями
подматриц Fkj = (fn+k,m+i)n^J0 У~ , где 1 < к + 1 < Кх = Nx - Lx + 1,
1 Матрица W является блочно-ганкелевой с ганкелевыми блоками
В разделе также описывается класс методов анализа текстурных изоб-ражений, основанных на этапе разложения метода АСС. Кроме того, как частный случай двумерного АСС, рассматривается вариант метода АСС для одновременного анализа нескольких временных рядов.
Во второй главе излагается необходимая алгебраическая теория. В первом разделе излагаются необходимые факты из алгебраической тео¬рии ганкелевых матриц [7]. Для фиксированного ряда F/v Є 1CN изучается зависимость от L структуры ганкелевой матрицы Х1^, т.е. ранга матрицы и структуры ее левого ядра
тЩ = 9^)(FW) tf {X є KL : XTX^ = (0,..., 0)}.
Показано, что либо ряд имеет конечный ранг, либо матрица Х^ имеет пол-ный ранг для любого L. Пусть ранг ряда равен d. Тогда dim-Dv^ = 0 для L < d, а для d < L < N — d + 1 базисом %v-L> являются столбцы матрицы
/ ро ... pd 0 0
Рт<м і .__ . о | eK-Lx(L-d)^ (5)
\ 0 0 ро ... pd
т.е. сдвиги характеристического вектора Р = (ро,... ,Pd)T, определенного однозначно с точностью до умножения на константу. Для L > N — d+І базис левого ядра образован сдвигами двух характеристических векторов. Также приводятся результаты о поведении ранга и структуры ряда при расширении
ряда: FN+i(a) = (/0,..., Дг-ъ а)-
Во втором разделе содержится обзор теории /^-последовательностей [4] для случая k = 2 (называемых в диссертации двумерными массивами), свя-занных линейными рекуррентными соотношениями. Бесконечная матрица J7 = (/n,m)nm=o называется двумерным бесконечным массивом. Линейные рекуррентные соотношения между элементами Т
-00
У^ a(p,r)fn+P,m+T = 0 для любых п,т Є No, (6)
р,т=0
10

где множество {(р, т) : <2(АТ) Ф 0} конечно, ассоциируются с многочленами
+оо
р(х,у) = ^2 а(рт)%рУт- Множество многочленов Х{Т\ для которых выпол-
р,т=0
няется (6), называется аннулягпором J- и является идеалом [3] в кольце мно-гочленов С [ж, у] от двух переменных.
Известно, что линейное пространство £(37), образованное сдвигами Tk,i = (/n+fc,m+i)nm=oi конечномерно тогда и только тогда, когда идеал 1-(77) нуль-мерен, т.е. многообразие [3] (множество корней) идеала 1-(77) конечно:
У(Х(7-)) = {(АьМ1),...,(Лг,Мг)}.
В этом случае массив Т имеет единственное биномиальное представление
л,- = І £ € ft) (І) *㻴, en
k=l (а,/3)єМ§ V J V У
гДе (a):(/3) — биномиальные коэффициенты и количество ненулевых коэф-фициентов Ъа о конечно.
В теории к-линейных последовательностей [4] ставится вопрос об оценке
линейной сложности массива rftF) = dim £(.77) по его биномиальному пред-ставлению [4]. Основным способом оценки линейной сложности является сле-дующий способ. Определим носитель массива В как как Supp£> = {(а,/3) Є NQ : Ъаф т^ 0}- Множество индексов 21 С NQ называется диаграммой Ферре, если ((-1,0) + 21) П NQ С 21 и ((0, -1) + 21) П NQ С 21, где операция сдвига
множества индексов определяется как (а, (5) +21 = {(а + к,/3 + 1),(к,1) Є 21}.
Предложение [4, Предл. 23]. Если массив Т имеет представление с одним корнем (А,/І)
(<*,/з)єм§ W \ /
£> = (fra,/?)a/}Lo — массив коэффициентов и $ — наименьшая диаграмма Фер-ре, содержащая Supp£>, то г (J7) < ##.
В третьей главе излагаются теоретические результаты диссертации для временных рядов, полученные с помощью теории ганкелевых матриц.
В первом разделе на основе алгебраической теории ганкелевых матриц производится систематизация типов рядов с точки зрения АСС: конечного ранга, неполного ранга, реверсивных. Естественным образом определяется
11

класс продолжимых рядов. Устанавливаются точные связи между типами, в том числе уточняются результаты из [1] и [6].
Во втором разделе исследуется слабая разделимость рядов. Для полураз-делимости предлагается следующее условие.
Теорема 3.2.1. Пусть F^ ф 0 и {Uh ..., Ur} — базис C^(F^]), a F^] является реверсивным рядом размерности d < N/2, и d < min(L — 1, К).
Ряды F^r И FJY L-полуразделимы тогда и только тогда, когда минималь-ный многочлен p(2>(z) ряда F^ является общим делителем производящих
многочленов Uj(z) = щ'+щ'г+.. .+it^i1zL_1, где Uj = (щ\щ\ ... ,W£-i)T-
Данное условие позволяет описать все случаи левой разделимости для достаточно широкого класса рядов.
Теорема 3.2.3. Реверсивные ряды FN и FN размерностей d\,d2 < N/2 L-полуразделимы тогда и только тогда, когда существуют а&,&/ Є С \ {0}, р > 0, со Є [0; 1/L) и различные rrik, Ы Є No, 0 < 77¾, Ы < L, такие что
fil) = Е аЛехр (2т (f + co)) )", tf] = £ hip-1 ехр (2т (| + со))
к=\ v 7 i=i v
Осуществляется полная классификация случаев полуразделимости при L < К. Представлен критерий и все случаи двусторонней разделимости.
В третьем разделе изучается поведение побочных корней ЛРФ прогноза. Пусть A(z) = P(z)Hn(z) — характеристический многочлен ЛРФ прогноза для длины окна L. Тогда вектор Нп: соответствующий п = L—d—1 побочным корням ЛРФ, является решением уравнения
(р(Ь)Гр(Ь)Яп = еп+1,
и многочлены Hn(z) образуют систему ортогональных многочленов на еди-ничной комплексной окружности с весом |P(z)|2. На языке ортогональных многочленов систематизируются известные результаты для побочных кор¬ней ЛРФ прогноза. Для описания асимптотического распределения корней используются современные результаты теории ортогональных многочленов. Четвертый раздел посвящен подсчету количества ганкелевых матриц над конечным полем. Формулы для Г^хК известны [5]. Для нахождения Г^хК,г используется алгебраическая теория ганкелевых матриц.
 


Обновить код

Заказать выполнение авторской работы:

Поля, отмеченные * обязательны для заполнения:


Заказчик:


ПОИСК ДИССЕРТАЦИИ, АВТОРЕФЕРАТА ИЛИ СТАТЬИ


Доставка любой диссертации из России и Украины