Анализ сингулярного спектра в задачах обработки временных и пространственных данных

На правах рукописи

Усевич Константин Дмитриевич АНАЛИЗ СИНГУЛЯРНОГО СПЕКТРА В ЗАДАЧАХ ОБРАБОТКИ ВРЕМЕННЫХ И ПРОСТРАНСТВЕННЫХ ДАННЫХ 05.13.18 – Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург – 2011

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета

Научный консультант: кандидат физико-математических наук, доцент Голяндина Нина Эдуардовна

Официальные оппоненты: доктор физико-математических наук, профессор Егоров Владимир Алексеевич (Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”) кандидат физико-математических наук, старший научный сотрудник Васильев Николай Николаевич (Учреждение Российской академии наук Санкт-Петербургское отделение Математи ческого института им. В.А. Стеклова РАН)

Ведущая организация: Учреждение Российской академии наук Санкт Петербургский институт информатики и авто матизации РАН

Защита состоится “ ” 2011г. в часов на заседа нии диссертационного совета Д 212.232.51 по защите докторских и кандидат ских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д.

28, математико-механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке имени М.

Горького Санкт-Петербургского государственного университета по адресу:

199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан “ ” 201_г.

Ученый секретарь Даугавет И.К.

диссертационного совета

Общая характеристика работы

Актуальность темы Во многих естественных науках сложилось пред ставление о возможности описания природных процессов в виде суммы трен да (медленной нерегулярной составляющей), периодических компонент (воз можно, модулированных) и шума (обычно описываемого случайным процес сом). В анализе временных рядов одной из основных задач является разло жение наблюдаемого временного ряда на исходные составляющие. Для раз личных частных случаев этой задачи разработаны мощные теории, такие как теория аппроксимации и теория рядов Фурье. В общей постановке задачи, ко торая характерна для анализа реальных данных, при отсутствии априорной информации, применение этих методов наталкивается на ряд трудностей.

В течение 70х–80х гг. независимо в США, Великобритании и СССР по лучили распространение идеи о вложении временного ряда в многомерное пространство с последующим сингулярным разложением полученной ганке левой матрицы. Кульминацией этих идей стал метод анализа сингулярного спектра (АСС, Singular Spectrum Analysis, SSA, в отечественной литературе также известный под названием “Гусеница”) [6], который позволяет решать задачи выделения компонент временного ряда различной структуры и, кро ме того, решать для выделенных компонент задачи описания их структуры, прогнозирования, оценки параметров, обнаружения разладки в структуре.

Существует большое количество прикладных научных исследований, ис пользующих метод АСС, в таких областях как экономика, экспериментальная биология, медицина, науки о земле, и т. д. Также существует множество мето дов оценки параметров комплексных экспоненциальных сигналов (ESPRIT, MUSIC, и т.д.), основанных на этапе разложения метода АСС. Вариант мето да АСС для пространственных данных (двумерных массивов) служит осно вой для класса методов классификации и сегментации текстурных изображе ний. Также существуют методы оценки параметров двумерных комплексных экспоненциальных сигналов, основанные на разложении в методе АСС.

В теории методов типа АСС основными являются вопросы о нахождении условий, при которых исходные компоненты разделимы с помощью метода АСС, и об описании структуры, которой обладают разделимые компоненты.

Несмотря на большое количество приложений, данные вопросы практически не исследованы для двумерного варианта метода АСС.

К недостаткам методов, основанных на двумерном варианте АСС, тради ционно относят их вычислительную сложность. В связи с отсутствием эф фективных вычислительных алгоритмов для разложения в двумерном мето де АСС, обычно используются лишь небольшие размеры окна. В частности поэтому практически не исследован вопрос выбора параметров метода (раз меров окна) для лучшей разделимости массивов.

Основными целями работы являются комплексное исследование про блемы разделимости временных и пространственных данных в методе АСС, исследование свойств моделей данных конечного ранга и развитие методов обработки данных на основе метода АСС. Для достижения целей были по ставлены и решены следующие задачи:

1. Систематизация и уточнение известных (для рядов) и получение но вых (для массивов) результатов о структуре данных конечного ранга, определяемой линейными рекуррентными соотношениями.

2. Нахождение условий точной разделимости рядов и массивов в методе АСС.

3. Определение влияния параметров двумерного метода АСС на раздели мость детерминистической и шумовой составляющих с помощью мате матического моделирования;

разработка рекомендаций по выбору пара метров метода.

4. Разработка и эффективная реализация методов обработки двумерных массивов, основанных на методе АСС, исследование свойств методов с помощью численных экспериментов.

Методы исследования. В работе используются методы алгебраической теории ганкелевых матриц;

теории ортогональных многочленов;

теории k-ли нейных рекуррентных последовательностей;

теории идеалов в кольцах мно гочленов и их базисов Гребнера;

методы теории обыкновенных дифферен циальных уравнений и уравнений в частных производных. Для численного исследования свойств алгоритмов обработки данных, основанных на методе АСС применяются методы статистического моделирования. Для реализации алгоритмов используются среды программирования Visual C++, R.

Основные результаты, выносимые на защиту:

1. Для временных рядов систематизированы и уточнены соотношения меж ду рангом рядов и свойствами линейных рекуррентных формул (ЛРФ), которым они удовлетворяют;

на основе теории ортогональных многочле нов систематизированы свойства побочных корней ЛРФ. [A2].

2. Разработан критерий слабой полуразделимости рядов, позволяющий пе речислить все возможные случаи полуразделимости для L K и все случаи разделимости рядов [A2]. Получено необходимое и достаточное условие полуразделимости массивов конечного ранга.

3. Получено распределение ранга в подмножестве множества ганкелевых матриц над конечным полем, необходимое для нахождения вероятности случайной классификации с инверсией в модификации метода АСС над конечным полем [A7].

4. Описаны классы бесконечных массивов с точки зрения ранга их разло жения в методе АСС [A4, A6]. Описан класс функций, имеющих конеч ный ранг в непрерывном варианте разложения метода АСС [A1].

5. Получена новая оценка ранга (линейной сложности) полиномиального массива по набору коэффициентов его биномиального представления [A4, A8]. Расширена оценка множества допустимых размеров окна со случая сумм комплексных экспонент на общий случай массивов конеч ного ранга.

6. С помощью статистического моделирования для задачи восстановления зашумленного сигнала произведено сравнение двумерного метода АСС с другими методами обработки двумерных массивов, основанными на сингулярном разложении [A4]. На основе экспериментов выработаны рекомендации по выбору параметров в задаче восстановления, в том числе и для восстановления различных областей массива.

7. Разработаны и реализованы эффективные методы вычисления разложе ния в методе АСС. Разработаны и реализованы алгоритмы для решения задач фильтрации цифровых моделей рельефа [A3, A5] и анализа тек стурных изображений.

Научная новизна Все результаты, выносимые на защиту, являются но выми.

Теоретическая и практическая значимость В диссертационной рабо те был предложен алгебраический подход для решения широкого класса тео ретических задач в методе АСС;

была продемонстрирована эффективность предложенного подхода. Также в рамках данной работы были разработаны и эффективно реализованы алгоритмы решения различных задач обработки двумерных данных на основе метода АСС. На основе численных экспери ментов было показано, что разработанные алгоритмы могут быть успешно использованы для решения данных задач.

Апробация работы Основные результаты обсуждались на семинарах кафедры статистического моделирования математико-механического факуль тета СПбГУ, семинаре кафедры статистики в School of Mathematics, Cardi University (Великобритания, февраль 2008, 2009) и докладывались на меж дународных конференциях: 2nd International Conference on Matrix Methods and Operator Equations (Москва, 23–27 июля 2007 г.), Идентификация си стем и задачи управления SICPRO’08 (Москва, 28–31 января 2008 г.), 6th St.Petersburg Workshop on Simulation (Санкт-Петербург, 28 июня – 4 июля, 2009 г.), UK-China workshop on singular spectrum analysis and its applications (Кардифф, Великобритания, 16–18 сентября 2010 г.).

Работа над диссертацией была частично поддержана стипендией Прави тельства Российской Федерации для аспирантов за 2009–10 годы, грантами CRDF №№ RUB1-1643-ST-06 и RUB1-33015-ST-09 и грантами Правительства Санкт-Петербурга №№ 2.1/30-04/27, 2.1/29-04/021, 2.1/07-06/056.

Публикации. Материалы диссертации опубликованы в работах [A1, A2, A3, A4, A5, A6, A7, A8]. Из них работы [A1, A2] в списке журналов, реко мендованных ВАК.

Работы [A3, A4, A5, A6, A7, A8] выполнены в соавторстве. Соискателю в работах [A4, A6, A7, A8] принадлежат доказательства утверждений, в ра ботах [A3, A4, A5, A8] численные эксперименты и реализация алгорит мов. И.В. Флоринскому в работах [A3, A5] принадлежат постановки задач.

В работе [A7] А.О. Алексееву и Н.П. Алексеевой принадлежат постановки задач и способ вычисления вероятности классификации, Е.М. Подхалюзиной и П.В. Грачевой реализация алгоритмов и обработка данных. Научному руководителю Н.Э. Голяндиной в работах [A3, A4, A5, A6, A8] принадлежат постановки задач, методология применения метода АСС.

Структура и объем диссертации Диссертация состоит из введения, списка основных обозначений, 5 глав, заключения, библиографии и приложе ния. Общий объем диссертации 226 страниц. Библиография включает наименований на 14 страницах.

Содержание работы Основными объектами исследования являются временные ряды FN = Nx 1,N (f0,..., fN 1 ) CN и двумерные массивы F = (fm,n )m,n=0 y, fm,n C.

Рассмотрим базовый метод АСС для временных рядов. Пусть ряд явля ется суммой компонент различной структуры F = F (1) +... + F (r). На шаге вложения по ряду FN и длине окна L составляется L-траекторная матри ца ряда, столбцами которой являются скользящие отрезки ряда длины L:

f0 f1 f2... fK f1... fK f2 f X = X(L) =.. (1)......

........

fL1 fL fL+1... fN Траекторная матрица имеет одинаковые значения на антидиагоналях, т.е.

является ганкелевой матрицей. Затем производится сингулярное разложе ние (SVD) траекторной матрицы d j Uj Vj, (2) X= j= сингулярные числа, а {Uj }d и {Vj }d где 1... d 0 левые и j=1 j= правые сингулярные векторы, называемые также собственными и фактор ными векторами. Набор (j, Uj, Vj ) называется j-й собственной тройкой.

Собственные векторы образуют базис пространства столбцов матрицы X, def L(L) (FN ) = span(X), называемого траекторным пространством.

C помощью задания группировки, т.е. разбиения набора собственных троек на r групп {1,..., d} = J1... Jr, определяется разложение r X= XJk, k= j Uj Vj. Посредством диагонального усреднения матрицы где XJ = jJ XJk преобразуются в восстановленные ряды F (k), что приводит к разложению r F (k).

F= k= В теории метода АСС основным является вопрос о нахождении условий разде лимости компонент в исходной сумме F = F (1) +... + F (r), т.е. возможности с помощью АСС найти восстановленные ряды F (k), хорошо аппроксимиру ющие F (k), или базисы {Uj }jJk подпространств, аппроксимирующих траек торные пространства L(L) (F (k) ). Кроме того, важна идентифицируемость компонент, т.е. возможность различить соответствующие собственные трой ки после шага разложения в методе АСС, для чего, в частности, количество собственных троек, соответствующих компоненте, должно быть небольшим и одинаковым для различных размеров окна. Идеальной моделью таких рядов являются ряды, траекторные матрицы которых имеют малый, не зависящий от размеров окна ранг, так называемые ряды конечного ранга.

Во введении обосновывается актуальность диссертации, формулируют ся цели и задачи работы, кратко описывается структура диссертации.

Глава 1 содержит обзор теории и основных понятий метода АСС. Вво дятся определения, описываются модели и задачи, рассматриваемые в рамках данной диссертации.

Первый раздел посвящен описанию базового метода АСС в комплексном варианте и обсуждению основных шагов алгоритма.

Второй раздел посвящен краткому обзору модели рядов конечного ранга.

Ряд FN CN называется рядом конечного ранга d, если ранг X(L) равен некоторому числу d N/2 для любых L, d L N d + 1. Определяется класс рядов, удовлетворяющих линейным рекуррентным формулам (ЛРФ), т.е. рядов, для которых существуют a0,..., a1 C, такие что (3) fn+ = ak fn+k k= для 0 n N 1. В разделе также приводятся известные в теории АСС результаты о соотношениях между рядами, удовлетворяющими ЛРФ, и рядами конечного ранга [1, 6].

Третий раздел посвящен понятию разделимости рядов в методе АСС. Два ряда F (1) и F (2) называются слабо L-полуразделимыми, если пространства столбцов их траекторных матриц ортогональны L(L) (F (1) ) L(L) (F (2) ). Если к тому же L(K) (F (1) ) L(K) (F (2) ), то ряды называются слабо L-разделимыми.

Ряды слабо L-разделимы тогда и только тогда, когда сумма сингулярных раз ложений траекторных матриц отдельных рядов d1 d (1) (1) (2) (2) j Uj (Vj ) j Uj (Vj ) X = X1 + X2 = + j=1 j= является сингулярным разложением матрицы X. В разделе также приводят ся основные сведения о точной и приближенной разделимости [6].

В четвертом разделе содержится обзор теории бесконечных рядов, удовле творяющих ЛРФ. Ряд F = (f0,..., fn,...), fn K, где K поле, удовле творяет ЛРФ (3), если равенство (3), при a0,..., a1 K, выполняется для def всех n N0 = N {0}. Каждой ЛРФ (3) сопоставляется характеристиче ak z k. Существует минимальный многочлен ский многочлен A(z) = z k= d P (z) = pd z +... + p1 z + p0, такой что характеристический многочлен любой ЛРФ делится на P (z). Известно, что в случае комплексного поля, K = C, такие ряды имеют единственное представление 0 m Qk (n)n (4) fn = + cj j (n), k j= k= где Qk ненулевые многочлены степени k 1, cj комплексные константы, символ Кронекера, т.е. j (n) = 1 если n = j и j (n) = c0 1 = 0, j (n) иначе. При этом k являются корнями P (z) с кратностями k, 0 кратность корня 0, и 0 +...+m = d. Для вещественнозначных рядов представление (4) соответствует сумме произведений полиномов, экспонент и косинусов. Если a0 = 0 или, что то же самое, 0 = 0, ряд F называется реверсивным рядом размерности d. Конечный отрезок FN такого ряда F называется реверсив ным рядом размерности d, если N 2d.

В пятом разделе рассматриваются методы прогнозирования компонент (1) (2) (1) разложения в методе АСС. Пусть FN = FN + FN, компонента FN явля ется реверсивным рядом размерности d и имеет представление (4), а также d L N d + 1. Тогда по подпространству = span{Uj1,..., Ujd } CL, со def (1) ответствующему компоненте FN в разложении, если eL = (0,..., 0, 1)T, / коэффициенты a0,..., aL2 ЛРФ прогноза определяются с помощью проек ции eL на сопряжение ортогонального дополнения R = подпространства:

(b0,..., bL1 )T = R eL, (a0,..., aL2 )T = (b0,..., bL2 )T /(bL1 ).

(1) В случае точной разделимости, когда L(FN ) =, корнями характери стического многочлена A(z) ЛРФ прогноза являются d корней минимально го многочлена P (z) и L d 1 побочных корней. В случае приближенной разделимости корни A(z) являются приближениями корней минимального многочлена и побочных корней, что позволяет использовать ЛРФ прогноза (1) для оценки параметров ряда FN.

В шестом разделе описываются модификации метода АСС. Рассматрива ются некоторые методы оценки параметров сигналов. Подробно обсуждается модификация метода АСС над конечным полем для анализа категориальных данных. В рамках этой модификации ставится задача о нахождении вероят ности случайной классификации с точностью до инверсии. Пусть на некото ром вероятностном пространстве (, F, P) заданы случайные вектор V F и случайная ганкелева L K матрица c элементами из F2, независимые и имеющие равномерное распределение. Требуется найти вероятность def F1 (0) = P(V span(X) или V + 1L span(X)), def где 1L = (1,..., 1)T. Эту вероятность можно выразить как F1 (0) = 2P(V span(X)) P(1L span(X) и V span(X)), и для нахождения каждого из слагаемых достаточно найти величины LK = #{X HLK : rank X = r}, r LK,1 = #{X HLK : rank X = r, 1L span(X)}, r где HLK множество ганкелевых матриц размера L K.

В седьмом разделе описывается двумерный вариант метода АСС [2]. Для Nx 1,N двумерного массива данных (матрицы) F = (fn,m )n,m=0 y (Lx, Ly )-траектор ная матрица W = W(Lx,Ly ) формируется по двумерному скользящему окну размера Lx Ly. Столбцы W (векторы вложения) являются векторизациями def def Lx 1,L подматриц Fk,l = (fn+k,m+l )n,m=0 y, где 1 k + 1 Kx = Nx Lx + 1, def 1 l + 1 Ky = Ny Ly + 1, при этом (W)n+Lx m+1,k+Kx l+1 = fn+k,m+l.

Матрица W является блочно-ганкелевой с ганкелевыми блоками [8].

В разделе также описывается класс методов анализа текстурных изоб ражений, основанных на этапе разложения метода АСС. Кроме того, как частный случай двумерного АСС, рассматривается вариант метода АСС для одновременного анализа нескольких временных рядов.

Во второй главе излагается необходимая алгебраическая теория.

В первом разделе излагаются необходимые факты из алгебраической тео рии ганкелевых матриц [7]. Для фиксированного ряда FN KN изучается зависимость от L структуры ганкелевой матрицы X(L), т.е. ранга матрицы и структуры ее левого ядра def R(L) = R(L) (FN ) = {X KL : X T X(L) = (0,..., 0)}.

Показано, что либо ряд имеет конечный ранг, либо матрица X(L) имеет пол ный ранг для любого L. Пусть ранг ряда равен d. Тогда dim R(L) = 0 для L d, а для d L N d + 1 базисом R(L) являются столбцы матрицы T p0... pd 0 P(L) = 0...... 0 KL(Ld), def (5) 0 0 p0... pd т.е. сдвиги характеристического вектора P = (p0,..., pd )T, определенного однозначно с точностью до умножения на константу. Для L N d+1 базис левого ядра образован сдвигами двух характеристических векторов. Также приводятся результаты о поведении ранга и структуры ряда при расширении def ряда: FN +1 () = (f0,..., fN 1, ).

Во втором разделе содержится обзор теории k-последовательностей [4] для случая k = 2 (называемых в диссертации двумерными массивами), свя занных линейными рекуррентными соотношениями. Бесконечная матрица F = (fn,m )+ называется двумерным бесконечным массивом. Линейные n,m= рекуррентные соотношения между элементами F + a(, ) fn+,m+ = 0 для любых n, m N0, (6), = где множество {(, ) : a(, ) = 0} конечно, ассоциируются с многочленами + a(, ) x y. Множество многочленов I(F), для которых выпол p(x, y) =, = няется (6), называется аннулятором F и является идеалом [3] в кольце мно гочленов C[x, y] от двух переменных.

def Известно, что линейное пространство L(F), образованное сдвигами Fk,l = (fn+k,m+l )+, конечномерно тогда и только тогда, когда идеал I(F) нуль n,m= мерен, т.е. многообразие [3] (множество корней) идеала I(F) конечно:

V (I(F)) = {(1, µ1 ),..., (r, µr )}.

В этом случае массив F имеет единственное биномиальное представление r n m n m (k) (7) fn,m = b, k µk, (,)N k=1 где ( ),( m ) биномиальные коэффициенты и количество ненулевых коэф n (k) фициентов b, конечно.

В теории k-линейных последовательностей [4] ставится вопрос об оценке def линейной сложности массива r(F) = dim L(F) по его биномиальному пред ставлению [4]. Основным способом оценки линейной сложности является сле def дующий способ. Определим носитель массива B как как Supp B = {(, ) N2 : b, = 0}. Множество индексов A N2 называется диаграммой Ферре, 0 если ((1, 0) + A) N2 A и ((0, 1) + A) N2 A, где операция сдвига 0 def множества индексов определяется как (, ) + A = {( + k, + l), (k, l) A}.

Предложение [4, Предл. 23]. Если массив F имеет представление c одним корнем (, µ) n m n m (8) fn,m = b, µ, (,)N B = (b, )+ массив коэффициентов и F наименьшая диаграмма Фер,= ре, содержащая Supp B, то r(F) #F.

В третьей главе излагаются теоретические результаты диссертации для временных рядов, полученные с помощью теории ганкелевых матриц.

В первом разделе на основе алгебраической теории ганкелевых матриц производится систематизация типов рядов с точки зрения АСС: конечного ранга, неполного ранга, реверсивных. Естественным образом определяется класс продолжимых рядов. Устанавливаются точные связи между типами, в том числе уточняются результаты из [1] и [6].

Во втором разделе исследуется слабая разделимость рядов. Для полураз делимости предлагается следующее условие.

(1) (1) (2) базис L(L) (FN ), а FN Теорема 3.2.1. Пусть FN = 0 и {U1,..., Ur } является реверсивным рядом размерности d N/2, и d min(L 1, K).

(1) (2) Ряды FN и FN L-полуразделимы тогда и только тогда, когда минималь (2) ный многочлен P (2) (z) ряда FN является общим делителем производящих def (j) (j) (j) (j) (j) (j) многочленов Uj (z) = u0 +u1 z+...+uL1 z L1, где Uj = (u0, u1,..., uL1 )T.

Данное условие позволяет описать все случаи левой разделимости для достаточно широкого класса рядов.

(1) (2) Теорема 3.2.3. Реверсивные ряды FN и FN размерностей d1, d2 N/ L-полуразделимы тогда и только тогда, когда существуют ak, bl C \ {0}, 0, [0;

1/L) и различные mk, hl N0, 0 mk, hl L, такие что d1 d n n (1) (2) mk hl bl 1 exp 2i fn = ak exp 2i +, fn = +.

L L k=1 l= Осуществляется полная классификация случаев полуразделимости при L K. Представлен критерий и все случаи двусторонней разделимости.

В третьем разделе изучается поведение побочных корней ЛРФ прогноза.

Пусть A(z) = P (z)Hn (z) характеристический многочлен ЛРФ прогноза для длины окна L. Тогда вектор Hn, соответствующий n = Ld1 побочным корням ЛРФ, является решением уравнения (P(L) ) P(L) Hn = en+1, и многочлены Hn (z) образуют систему ортогональных многочленов на еди ничной комплексной окружности с весом |P (z)|2. На языке ортогональных многочленов систематизируются известные результаты для побочных кор ней ЛРФ прогноза. Для описания асимптотического распределения корней используются современные результаты теории ортогональных многочленов.

Четвертый раздел посвящен подсчету количества ганкелевых матриц над LK известны [5]. Для нахождения LK, конечным полем. Формулы для r r используется алгебраическая теория ганкелевых матриц.

Теорема 3.4.1.

LK r /3, r min(L, K), L(K+1) LK,1 = r /3, r = K L, r LK r min(L, K) или r = L K.

r, В четвертой главе содержатся теоретические результаты для двумер ного расширения метода АСС.

В первом разделе приводятся базовые свойства ранга (Lx, Ly )-траекторной матрицы W(Lx,Ly ) массива F. В дальнейшем в качестве массивов рассматрива ются Nx Ny подмассивы бесконечных массивов. Для бесконечного массива вводится понятие (Lx, Ly )-траекторного пространства как пространства, по (Lx,L ) рожденного всеми Lx Ly окнами массива F: L(Lx,Ly ) (F) = span{Fm,n y }+. m,n= Показано, что r(F) + тогда и только тогда, когда размерность тра екторного пространства dim L(Lx,Ly ) (F) равномерно ограничена. При этом dim L(Lx,Ly ) (F) = r(F) для достаточно больших размеров окна Lx Lx0, Ly Ly0. Поэтому далее массивы с r(F) + называются массивами ко нечного ранга. Выделяется также класс массивов неполного ранга, для кото рых dim L(Lx,Ly ) (F) Lx Ly. Показано, что этот класс не совпадает с классом массивов конечного ранга, в отличие от случая аналогичных классов времен ных рядов.

Для массивов конечного ранга доказывается новое утверждение об оценке линейной сложности по биномиальному представлению.

Теорема 4.1.2. Пусть массив F имеет представление (8) и m = max{ + :

(, ) Supp B}. Тогда r(F) m + 1 m +, где = 1(2) для четного 2 (нечетного m).

Во втором разделе рассматривается задача о нахождении для массива конечного ранга множества допустимых размеров окна def M(F) = {(Lx, Ly ) N2 : dim L(Lx,Ly ) (F) = r(F)}.

Доказана следующая теорема, которая позволяет оценить M(F) с точностью до конечного числа элементов.

Теорема 3.2.3. Пусть Gx и Gy есть диаграммы Ферре под старшими членами базисов Гребнера для лексикографических упорядочений y x и x y.

Тогда (Bx (Gx ), By (Gx )), (Bx (Gy ), By (Gy )) M(F), и для любого (Lx, Ly ) M выполняются неравенства Ly By (Gx ), Lx Bx (Gy ).

Частным случаем теоремы 4.2.1 является известный результат о нахождении множества допустимых размеров окна для сумм комплексных экспонент [8].

Также показано, что ранг траекторной матрицы W(Lx,Ly ) конечного подмас сива F равен линейной сложности массива r(F) тогда и только тогда, когда (Lx, Ly ) M(F) и (Kx, Ky ) M(F).

В третьем разделе изучается разделимость двумерных массивов. Массивы F и F(2) (Lx, Ly )-полуразделимы, если L(Lx,Ly ) (F(1) ) L(Lx,Ly ) (F(2) ). Если к (1) тому же L(Kx,Ky ) (F(1) ) L(Kx,Ky ) (F(2) ), то массивы (Lx, Ly )-разделимы.

Доказывается следующая теорема, которая позволяет описать все случаи разделимости массивов конечного ранга.

(1) (2) Теорема 4.3.3. Два массива fm,n = P1 (m, n)m µn и fm,n = P2 (m, n)m µn 11 (Lx, Ly )-полуразделимы только в следующих случаях:

1. P1 = P1 (m), P2 = P2 (m), ряды µn и µn Ly -полуразделимы 1 2. P1 = P1 (n), P2 = P2 (n), ряды m и m Lx -полуразделимы.

1 3. P1 = const, P2 = Q21 (n) + Q22 (m), ряды m и m Lx -полуразделимы, 1 n n ряды µ1 и µ2 Ly -полуразделимы.

4. P1 = a1 m+b1 n+c1, P2 = a2 m+b2 n+c2, ряды m и m Lx -полуразделимы, 1 ряды µn и µn Ly -полуразделимы и a1 b2 + b1 a2 = 0.

1 В четвертом разделе рассматривается непрерывная модель двумерного АСС. Доказывается результат о двумерных функциях конечного ранга.

Теорема 4.4.3. Пусть f C(d) ([0;

tx ] [0;

ty ]) (имеет непрерывные частные производные вплоть до порядка d), x (0, tx ), y (0, ty ) и функция g :

D1 D2 R, где D1 = [0;

x ][0;

y ] и D2 = [0;

tx x ][0;

ty y ], определена как g((u, v), (s, t)) = f (u + s, v + t) и имеет конечное разложение Шмидта d f (u + s, v + t) = g((u, v), (s, t)) = k k (u, v) k (s, t).

k= Тогда существуют j, µj C, m d и pj (x, y) C[x, y], такие что m f (x, y) = pj (x, y) exp(j x + µj y).

j= Пятая глава посвящена практическим аспектам двумерного метода АСС.

В первом разделе содержится исследование методами статистического мо делирования качества восстановления зашумленного массива конечного ран га с помощью метода АСС. В качестве модели шума используется аддитив ный гауссовский белый шум. Исследуется зависимость качества восстановле ния от размеров окна, в том числе и для различных областей массива (на пример, центральной части и краев массива).

Второй раздел посвящен применению метода АСС для различных задач обработки двумерных массивов. Предлагается метод фильтрации (сглажива ния) данных с помощью двумерного метода АСС. На примере цифровых мо делей рельефа демонстрируются свойства метода сглаживания. Также пред лагаются новые методы для задачи классификации текстурных изображений с помощью расстояний между подпространствами, используемых в различ ных модификациях метода АСС. Качество работы методов оценивается на тестовых базах данных.

Третий раздел посвящен обсуждению вопросов эффективной реализации алгоритмов для двумерного метода АСС. Предлагаются быстрые методы раз ложения, основанные на вычислении ковариационной матрицы и на быстром преобразовании Фурье. Также описывается устройство реализованного ком плекса программ.

В Заключении приводятся выводы и подводятся итоги диссертационно го исследования.

В приложении приводится часть исходных текстов комплекса программ.

Цитированная литература 1. Бухштабер В. М. Многомерные развертки временных рядов. Теоретиче ские основы и алгоритмы // Обозрение прикл. промышл. матем., сер. Ве роятн. и статист. 1997. Т. 4, № 4. С. 629–645.

2. Главные компоненты временных рядов: метод Гусеница, Под ред.

Д. Л. Данилов, А. А. Жиглявский. СПб.: Пресском, 1997. С. 308.

3. Кокс Д., Литтл Д., О’Ши Д. Идеалы, многообразия и алгоритмы. М.:

Мир, 2000. С. 687.

4. Куракин В. Л. Биномиальная сложность полилинейных последовательно стей // Труды по дискр. матем. М.: ФИЗМАТЛИТ, 2002. Т. 6. С. 82–138.

5. Daykin D. E. Distribution of bordered persymmetric matrices in a nite eld // J. Reine und Angew. Math. (Crelles Journal). 1960. Vol. 203. Pp. 47–45.

6. Golyandina N., Nekrutkin V., Zhigljavsky A. A. Analysis of Time Series Struc ture: SSA and Related Techniques. Chapman and Hall/CRC, 2001. P. 320.

7. Heinig G., Rost K. Algebraic methods for Toeplitz-like matrices and operators.

Akademie Verlag, Berlin, 1984. P. 212.

8. Yang H. H., Hua Y. On Rank of Block Hankel Matrix for 2-D Frequency Detection and Estimation // IEEE Transactions on Signal Processing. 1996.

Vol. 44, no. 4. Pp. 1046–1048.

Список публикаций автора Статьи в журналах, рекомендованных ВАК:

A1. Усевич К. Д. Разложение функций в двумерном варианте метода Гусе ница -SSA и связанные с ним системы уравнений в частных производ ных // Вестник СПбГУ, Серия 10: Прикладная математика, информати ка, процессы управления. 2009. № 3. С. 152–161.

A2. Usevich K. On signal and extraneous roots in Singular Spectrum Analysis // Statistics and Its Interface. 2010. Vol. 3, no. 3. Pp. 281–295.

Остальные публикации:

A3. Golyandina N., Florinsky I., Usevich K. Filtering of Digital Terrain Models by Two Dimensional Singular Spectrum Analysis // International Journal of Ecology & Development. 2007. Vol. 8, no. F07. Pp. 81–94.

A4. Голяндина Н. Э., Усевич К. Д. Метод 2D-SSA для анализа двумерных полей // Труды VII Международной конференции Идентификация си стем и задачи управления SICPRO’08. Москва, 28–31 января 2008. 2008.

С. 1657–1727.

A5. Голяндина Н. Э., Флоринский И. В., Усевич К. Д. Анализ сингулярно го спектра для фильтрации цифровых моделей рельефа // Геодезия и картография. 2008. № 5. С. 21–28.

A6. Golyandina N., Usevich K. An Algebraic View on Finite Rank in 2D-SSA // Proceedings of the 6th St.Petersburg Workshop on Simulation, June-July 2009 / Ed. by S. Ermakov, V. Melas, A. Pepelyshev. 2009. Pp. 308–313.

A7. Alexeyeva N., Alexeyev A., Gracheva P., Podkhalyuzina E., Usevich. K.

Symptom and syndrome analysis of categorial series, logical principles and forms of logic // Proceedings of the 2010 3rd Intern. Conf. on BioMedical En gineering and Informatics. 2010. Vol. 6. Pp. 2603–2606.

A8. Golyandina N. E., Usevich K. D. 2D-extension of Singular Spectrum Analysis:

algorithm and elements of theory // Matrix methods: theory, algorithms and applications / Ed. by V. Olshevsky, E. Tyrtyshnikov. World Scientic, 2010.

Pp. 449–473.