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

Краткое описание

Усевич, Константин Дмитриевич. Анализ сингулярного спектра в задачах обработки временных и пространственных данных : диссертация ... кандидата физико-математических наук : 05.13.18 / Усевич Константин Дмитриевич; [Место защиты: С.-Петерб. гос. ун-т].- Санкт-Петербург, 2011.- 226 с.: ил. РГБ ОД, 61 11-1/467

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
На правах рукописи
Уссвич Константин Дмитриевич
АНАЛИЗ СИНГУЛЯРНОГО СПЕКТРА В ЗАДАЧАХ ОБРАБОТКИ ВРЕМЕННЫХ И ПРОСТРАНСТВЕННЫХ ДАННЫХ
05.13.18 - Математическое моделирование, численные методы и комплексы программ
ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук
Научный руководитель к. ф.-м. н., доцент Голяндина Нина Эдуардовна
Санкт-Петербург - 2011
Содержание
Введение 6
Список основных обозначений 14
Глава 1. Основные сведения из теории метода АСС 18
1.1. Операции с матрицами 18
1.2. Базовый метод АСС 20
1.2.1. Этап разложения 21
1.2.2. Этап восстановления 22
1.2.3. Комментарии к шагу группировки 23
1.3. Ряды конечного ранга и разделимость 25
1.3.1. Ряды конечного ранга 25
1.3.2. Точная разделимость 27
1.3.3. Приближенная разделимость и полу разделимость ... 28
1.4. Ряды конечного ранга и линейные рекуррентные формулы . . 29
1.4.1. Случай конечных рядов 29
1.4.2. Случай бесконечных рядов 31
1.5. Продолжимые ряды и прогнозирование 34
1.5.1. ЛРФ прогноза в методе АСС и ее основные свойства . . 35
1.5.2. Алгоритмы прогноза в методе АСС 37
1.5.3. Побочные корни ЛРФ прогноза и их свойства 37
1.6. Модификации метода АСС 38
1.6.1. Методы оценки параметров сигналов .... 38
1.6.2. Метод АСС для рядов над конечным полем 41
1.7. Метод АСС для двумерных массивов 43
1.7.1. Базовый алгоритм метода АСС для двумерных массивов 43
1.7.2.. Частные случаи двумерного метода АСС 48
1.7.3. Метод АСС в анализе текстур: собственные фильтры . 49 
53
Глава 2. Алгебраическая теория
2.1. Структура ганкелевых матриц 53

2.1.1. Поведение ранга в зависимости от Ь
2.1.2. Структура левого ядра при <1 < Ь < N — <¿+1 ...
2.1.3. Структура левого ядра, Ь> N — <¿-1-1
2.1.4. Поведение ранга при расширении ряда
2.1.5. Библиографические ссылки
2.2. Бесконечные массивы
2.2.1. Бесконечные массивы и линейная сложность ....
2.2.2. Биномиальное представление и базисы пространства сдви¬гов
2.2.3. Биномиальное представление с одним корнем
2.2.4. Определяющие множества и оценки сверху линейной сложности по биномиальному представлению
2.2.5. Нижняя оценка линейной сложности
2.2.6. Оценки линейной сложности по биномиальному пред¬ставлению общего вида
2.2.7. Граничные базисы и базисы Грсбнера
Глава 3. Результаты для одномерного случая
3.1. Систематизация типов рядов конечного ранга
3.1.1. Продолжимые ряды и бесконечные ряды
3.1.2. Продолжимость и линейные рекуррентные формулы
3.1.3. Реверсивные ряды. Характеризация
3.1.4. Теорема Бухштабера. Базис траекторного пространства
3.2. Разделимость
3.2.1. Критерий односторонней разделимости
3.2.2. Полуотделимость от рядов регулярной конечно-разност¬ной размерности
53 55 57 60
63
64 64
67
68
70
72
73
74
79 79 79 82 84 86 88 88
91 96
3.2.3. Перечисление случаев левой отделимости для Ь < А 
3.2.4. Двусторонняя разделимость 97
3.3. ЛРФ прогноза и ее побочные корни 99
3.3.1. Характеристический полином ЛРФ прогноза . . . ... 99
3.3.2. Основные свойства ортогональных многочленов .... 101
3.3.3. Асимптотические свойства побочных корней 104
3.3.4. Некоторые приложения и замечания 109
3.4. Подсчет числа матриц данного ранга в конечном поле НО
3.4.1. Сведение задачи подсчета количества ганкелевых мат¬риц к задаче подсчета рядов 110
3.4.2. Независимость числа рядов данного ранга от длины ряда111
3.4.3. Результаты о количестве матриц и рядов 113
3.4.4. Подсчет рангов матриц с ограничениями . . 114
3.4.5. Нахождение количества рядов данного ранга с ограни¬чениями 116
Глава 4. Результаты для двумерного случая 120
4.1. Траекторное пространство и ранг массива 120
4.1.1. Траекторное пространство и основные свойства ранга . 120
4.1.2. Тензорное произведение рядов 121
4.1.3. (Lx, £у)-траекторное пространство бесконечного массива 122
4.1.4. Полиномиальное представление массивов и оценка ли¬нейной сложности 124
4.1.5. Оценки линейной сложности по диаграмме Ферре бино-миального представления 126
4.2. Оценки множества допустимых размеров окна 128
4.2.1. Оценка множества для бесконечного массива 128
4.2.2. Переход от бесконечного массива к конечному 132
4.3. Двумерная разделимость 134
4.3.1. Разделимость произведений р51дов 134
4.3.2. Разделимость бесконечных массивов конечного ранга . 136
4.4. Непрерывный вариант и системы в частных производных . . . 144
4.4.1. Разложение функций. Ранг функций 145
4.4.2. Линейные системы уравнений в частных производных . 147
4.4.3. Общий вид функций конечного ранга 149
4.4.4. Свойства системы высшего порядка 153
Глава 5. Численные эксперименты 156
5.1. Отделимость массивов конечного ранга от шума 156
5.1.1. Описание методов очистки от шума 156
5.1.2. Массивы конечного ранга, сравнение методов 157
5.1.3. Зависимость ошибки восстановления от размеров окна
и структура ошибки 161
5.1.4. Массивы неполного ранга 164
5.2. Задачи анализа изображений 165
5.2.1. Фильтрация цифровых моделей рельефа 165
5.2.2. Задачи анализа текстур 170
5.3. Комплекс программ для АСС-разложения и обработки данных 176
5.3.1. АСС-разложение на основе вычисления ковариационной матрицы 177
5.3.2. Быстрые вычисления с помощью БПФ 180'
5.3.3. Структура и краткое описание комплекса программ . . 183
Заключение 185
Литература 188
Приложение А. Исходные коды комплекса программ 202
А.1. Ядро комплекса программ 2D-SSA 202
А.2. Модуль пакета RSSA для двумерного АСС 211
Введение
Основными объектами исследования в диссертационной работе являются временные ряды и двумерные массивы данных.
Под вещественнозначным (комплекснозначным) одномерным временным рядом длины N > 2 понимается упорядоченная последовательность веще¬ственных (комплексных) чисел ^ = (/0,..., /лг-1), /п 6 1 (/п £ С). Чаще всего временной ряд является результатом измерения некоторого показателя в равноотстоящие моменты времени с шагом Д > 0, т.е. /„ = /(Дп), где /(£) — некоторая функция, заданная при ¿ > 0; однако, переменная I не обязательно имеет смысл времени и / может быть функцией от другого физического пара¬метра, например пространственной координаты [3, 7, 13]. Последовательности I7 = (/о,.... /дг-1), 1п £ /С, где /С — конечное поле [9], описывающие измене¬ние категориальных показателей, будем также называть временными рядами (над конечным полем). Мы будем считать временной ряд вектор-строкой, где это необходимо.
Под двумерным массивом (вещественнозначным или комплекснозначным) понимается таблица Р = (/т,п)т*п=о^"1 (/т,д е К или /т.:П е С) значений некоторой функции двух переменных /(ж,у), х,у > 0 на дискретной прямо¬угольной сетке с шагом Ах > 0 и Ау > 0, т.е. /т>п = /(Ахт,Ауп). Данные могут иметь разную природу: цифровые изображения [37], измерения некото¬рого показателя в пространстве (например высоты поверхности Земли [20]); в качестве одной из координат может выступать время, в этом случае массив можно рассматривать как совокупность рядов, или как многомерный времен¬ной ряд [7]. Двумерный массив везде далее мы считаем х А^ матрицей.
Будем говорить, что ряд ^ (массив Р) является суммой аддитивных со-ставляющих ..., (Р^...., р(г) соответственно) если он является их суммой как векторов (или матриц): Р = .Р^-К . .^-Р^ или Р = Р^-К . т.е. в смысле покомпонентного сложения. Одной из основных задач анализа данных является выделение аддитивных составляющих различной структу¬ры из наблюдаемого временного ряда или массива, что и является предметом исследования в диссертационной работе.
Актуальность темы. Во многих естественных науках сложилось пред-ставление о возможности описания природных процессов в виде суммы
m = fiT)(t)+f(pt)+f^(t) (0.1-)
где f(Tt) — медленно меняющаяся составляющая, называемая трендом, ко¬торую часто описывают некоторой параметрической составляющей, например полиномами невысоких порядков или функциями с ограничениями на их глад-кость [3, Гл. З] , f(pt) — периодическая составляющая, f^(t) — шумовая составляющая, которая обычно предполагается реализацией некоторого слу-чайного процесса. Наиболее распространенными задачами являются: опреде-ление глобального поведения ряда (выделение тренда), обнаружение перио- дичностей или удаление их из ряда (seasonal adjustment), сглаживание (выде¬ление низкочастотной составляющей), выделение детерминистической состав¬ляющей (отделение сигнала от шума).
Для различных частных случаев представления (0.1) разработаны мощ¬ные математические теории. Например задача f(t) — t) + f^(t) может решаться методами аппроксимации или регрессии (например, метод наимень¬ших квадратов [31]); в случае f(t) = f^pt) + /^(t), где шум предполагает¬ся стационарным, применимы методы спектрального анализа, основанные на теории стационарных случайных процессов и теории рядов Фурье [32, 117]. В общей постановке задачи, которая характерна для анализа реальных дан¬ных, при отсутствии априорной информации, применение параметрических методов наталкивается на ряд трудностей.
Анализ Сингулярного Спектра (.АСС'), как метод решения различных за¬дач анализа временных рядов, независимо появился в 70х-90х годах в России
и других странах [6, 51, 84]. Основой метода АСС является этап разложения,

на котором построенная по временному ряду ганкелева матрица раеклады- вается в сумму матриц с помощью сингулярного разложения (singular value decomposition, SVD) [58]. Группам слагаемых сингулярного разложения сопо-ставляются восстановленные ряды и результатом метода является разложение исходного ряда на аддитивные компоненты. Метод АСС позволяет решать за¬дачи выделения компонент временного ряда различной структуры и, кроме того, решать для выделенных компонент задачи описания их структуры, про-гнозирования, оценки параметров, обнаружения разладки в структуре [66].
Существует большое количество прикладных научных исследований, ис-пользующих метод АСС, в таких областях, как экология [4, 92], геология [6, 45], метеорология и гидрология [5, 77, 94], климатология [62, 76,102], сейсмо¬логия [112], экономика [120], биология [22, 51], медицина [49, 93, 108], генетика [75] и т. д. Также существует множество методов оценки параметров комплекс¬ных экспоненциальных сигналов с высоким разрешением [43, 82, 85, 111, 117] основанных на этапе разложения метода АСС, а также близких по структуре методов пеленгации с помощью антенных решеток [86, 89, 128].
Метод АСС для двумерных массивов, основанный на сингулярном разло-жении двухуровневой ганкелевой матрицы, был предложен в [13]. Этап раз-ложения двумерного АСС, также известный под названием eigenfiltering, при-меняется в таких задачах анализа текстур как: классификация, сегментация, обнаружение неоднородностей (в том числе и обнаружения дефектов материа¬лов в промышленности) [39, 99, 105]. Также существуют методы оценки пара¬метров двумерных комплексных экспоненциальных сигналов, основанные на разложении в двумерном методе АСС [42, 110, 126].
В теории методов типа АСС основными являются вопросы о нахождении условий, при которых исходные компоненты разделилш с помощью метода АСС, и об описании структуры, которой обладают разделимые компоненты [66], в частности, компоненты имеющие малый ранг разложения в АСС (так называемые ряды/массивы конечного ранга). Несмотря на большое количе¬ство приложений, данные вопросы практически не исследованы для двумер¬ного варианта метода АСС.
К недостаткам методов, основанных на двумерном варианте АСС, тради-ционно относят их вычислительную сложность. В связи с отсутствием эффек-тивных вычислительных алгоритмов для разложения в методе АСС, обычно используются лишь небольшие размеры окна. В частности поэтому практи¬чески не исследован вопрос выбора параметров метода (размеров окна) для лучшей разделимости массивов в практических задачах.
Основными целями работы являются комплексное исследование про-блемы разделимости временных и пространственных данных в методе АСС, исследование свойств моделей данных конечного ранга и развитие методов обработки данных на основе метода АСС. Для достижения целей были по-ставлены и решены следующие задачи:
1. Систематизация и уточнение известных (для рядов) и получение новых (для массивов) результатов о структуре данных конечного ранга, опре¬деляемой линейными рекуррентными соотношениями.
2. Нахождение условий точной разделимости рядов и массивов в методе АСС.
3. Определение влияния параметров двумерного метода АСС на раздели¬мость детерминистической и шумовой составляющих с помощью мате¬матического моделирования; разработка рекомендаций по выбору пара¬метров метода.
4. Разработка и эффективная реализация методов обработки двумерных массивов, основанных на методе АСС, исследование свойств методов с помощью численных экспериментов.
Методы исследования. В работе используются методы алгебраической теории ганкелевых матриц; теории ортогональных многочленов; теории к-ли-нейных рекуррентных последовательностей; теории идеалов в кольцах много-членов и их базисов Гребнера; методы теории обыкновенных дифференциаль¬ных уравнений и уравнений в частных производных. Для численного иссле¬дования свойств алгоритмов обработки данных, основанных на методе АСС, применяются методы статистического моделирования. Для реализации алго¬ритмов используются среды программирования Visual С++, R.
Основные результаты, выносимые па защиту:
1. Для временных рядов систематизированы и уточнены соотношения меж¬ду рангом рядов и свойствами линейных рекуррентных формул (ЛРФ), которым они удовлетворяют; на основе теории ортогональных многочле-нов систематизированы свойства побочных корней ЛРФ. [122].
2. Разработан критерий слабой полу разделимости рядов, позволяющий пе-речислить все возможные случаи полуразделимости для L < К и все случаи разделимости рядов [122]. Получено необходимое и достаточное условие полуразделимости массивов конечного ранга.
3. Получено распределение ранга в подмножестве множества ганкелевых матриц над конечным полем, необходимое для нахождения вероятности случайной классификации с инверсией в модификации метода АСС над конечным полем [40].
4. Описаны классы бесконечных массивов с точки зрения ранга их разло-жения в методе АСС [19, 68]. Описан класс функций, имеющих конечный ранг в непрерывном варианте разложения метода АСС [38].
5. Получена новая оценка ранга (линейной сложности) полиномиального массива по набору коэффициентов его биномиального представления [19, 70]. Расширена оценка множества допустимых размеров окна со слу¬чая сумм комплексных экспонент на общий случай массивов конечного ранга.
6. С помощью статистического моделирования для задачи восстановления заптумленного сигнала произведено сравнение двумерного метода АСС
с другими методами обработки двумерных массивов, основанными на сингулярном разложении [19]. На основе экспериментов выработаны ре-комендации по выбору параметров в задаче восстановления, в том числе и для восстановления различных областей массива.
7. Разработаны и реализованы эффективные методы вычисления разложе¬ния в методе АСС. Разработаны и реализованы алгоритмы для решения задач фильтрации цифровых моделей рельефа [20, 65] и анализа тек¬стурных изображений.
Научная новизна Все результаты, выносимые на защиту, являются но¬выми.
Теоретическая и практическая значимость В диссертационной рабо¬те был предложен алгебраический подход для решения широкого класса тео¬ретических задач в методе АСС; была продемонстрирована эффективность предложенного подхода. Также в рамках данной работы были разработаны и эффективно реализованы алгоритмы решения различных задач обработки двумерных данных на основе метода АСС. На основе численных эксперимен¬тов было показано, что разработанные алгоритмы могут быть успешно исполь¬зованы для решения данных задач.
Апробация работы Основные результаты обсуждались на семинарах кафедры статистического моделирования математико-механического факуль¬тета СПбГУ, семинаре кафедры статистики в School of Mathematics, Cardiff University (Великобритания, февраль 2008, 2009) и докладывались на меж¬дународных конференциях: «2nd International Conference on Matrix Methods and Operator Equations» (Москва, 23-27 июля 2007 г.), «Идентификация си¬стем и задачи управления» SICPRO'OS (Москва, 28-31 января 2008 г.), «6th St.Petersburg Workshop on Simulation» (Санкт-Петербург, 28 июня - 4 июля, 2009 г.), «UK-China Workshop on singular spectrum anafysis and its applications» (Кардифф, Великобритания, 16-18 сентября 2010 г.).
Работа над диссертацией была частично поддержана стипендией Прави-тельства Российской Федерации для аспирантов за 2009-10 годы, грантами СКОТ №№ ШШ-ШЗ-ЭТ-Об и ГШВ1-33015-8Т-09 и грантами Правительства Санкт-Петербурга №№ 2.1/30-04/27, 2.1/29-04/021, 2.1/07-06/056.
Диссертационная работа состоит из введения, списка основных обозначе¬ний, пяти глав, заключения, библиографии и приложения.
В первой главе содержится основная информация о методе АСС. При-водится обзор результатов о разделимости рядов и модели рядов конечного ранга. Вводится понятие продолжимости рядов, прогноза в АСС и линейной рекуррентной формулы прогноза. Рассматриваются различные модификации метода АСС. Отдельно описывается алгоритм двумерного метода АСС, его базовые свойства и существующие приложения.
Во второй главе содержится алгебраическая теория, необходимая для решения поставленных задач. Приводится обзор алгебраической теории ган- келевых матриц. Описывается теория бесконечных массивов, связанных ли-нейными соотношениями. Приводятся результаты о структуре бесконечных рекуррентных массивов и об оценке их линейной сложности.
В третьей главе содержатся результаты диссертации для случая времен¬ных рядов. Систематизируются и уточняются известные результаты о соотно¬шениях между рядами конечного ранга и Л РФ. Предлагается новый критерий полуразделимости и производится классификация всех случаев полураздели-мости и разделимости. Систематизируются результаты о распределении по-бочных корней ЛРФ. Приводятся результаты о способе подсчета количества матриц данного ранга в конечном поле.
В четвертой главе содержатся теоретические результаты для двумер¬ного метода АСС. Показывается связь между линейной сложностью беско¬нечных массивов и рангом разложения в методе АСС. Выделяются классы массивов конечного и неполного ранга. Доказывается новая оценка линейной сложности. Расширяется на общий случай оценка множества допустимых раз¬меров окна. Исследуются условия разделимости двумерных массивов. Дока¬зывается результат об общем виде функций конечного ранга в непрерывном варианте двумерного АСС.
В пятой главе содержатся практические результаты для двумерных мас-сивов. Изучается зависимость ошибки восстановления зашумленного сигнала от размеров окна и области изображения. Формулируются рекомендации по выбору размеров окна. Рассматриваются методы, основанные на АСС, для задач фильтрации изображений и обработки текстурных изображений. Разра-батываются методы для эффективного вычисления АСС-разложения и опи-сывается реализация этих методов в виде комплекса программ.
В заключении приводятся выводы и подводятся итоги диссертационного исследования.
Приложение А содержит исходные коды разработанного комплекса про-грамм.
Общий объем диссертации составляет 226 страниц, список литературы состоит из 128 наименований на 14 страницах.

Список литературы

Заключение
В диссертационной работе исследовались проблемы разделимости времен¬ных и пространственных данных в методе АСС и описания структуры моделей рядов и массивов конечного ранга, порождаемых разложением в методе АСС. Были предложены новые математические методы решения данных проблем. Были построены алгоритмы для решения задач обработки двумерных данных, свойства моделей и алгоритмов были исследованы методами статистического моделирования. Алгоритмы были эффективно реализованы в виде комплекса программ. Рассмотрим подробнее основные выводы работы.
• Было установлено, что в рамках алгебраической теории ганкелевых мат¬риц становится возможным систематизировать и установить точные свя¬зи между типами рядов: конечного ранга, реверсивными, продолжимы- ми, и т.д. (предложения 3.1.3, 3.1.4, 3.1.6 и 3.1.7; теорема 3.1.1), а также систематизировать важные для практики свойства, такие как свойства побочных корней ЛРФ прогноза (см. теорему 3.3.1, предложение 3.3.3 и раздел 3.3.3).
• Был предложен новый критерий полуразделимости (теорема 3.2.1), кото¬рый позволил найти все случаи полуразделимости и разделимости» про¬извольных рядов (теоремы 3.2.3 и 3.2.4) и разделимости массивов конеч¬ного ранга (теорема 4.3.3). Данный критерий может быть полезен для дальнейшего исследования разделимости в АСС, например, более слож¬ного, практически и теоретически значимого случая асимптотической разделимости.
использованы для нахождения границ доверительных областей в соот¬ветствующих статистических тестах.
Было показано, что бесконечные массивы конечного ранга соответству¬ют массивам с конечной линейной сложностью (линейным рекуррент¬ным массивам, см. предложение 4.1.1); был найден общий вид непре¬рывных функций, имеющих конечное АСС разложение в непрерывном варианте метода АСС (теорема 4.4.2).
В рамках исследования была получена новая оценка линейной слож¬ности (ранга) полиномиального массива по его коэффициентам (теоре¬ма 4.1.2), которая в некоторых случаях лучше известной оценки (предло¬жение 2.2.6). Однако и полученную оценку, возможно, можно улучшить. Оценка ранга массива важна для предварительного этапа математиче¬ского моделирования в рамках метода АСС.
Был исследован вопрос о нахождении области допустимых размеров ок¬на для массивов конечного ранга. На общий случай массивов конечного ранга расширены оценки множества допустимых размеров окна с помо¬щью методов базисов Грёбнера (теорема 4.2.1). Знание минимально до¬пустимых размеров окна необходимо для выбора достаточных размеров окна в практических задачах.
Была исследована зависимость разделимости сигнала и шума от разме¬ров окна для различных массивов конечного ранга . Было продемонстри¬ровано, что многие эффекты, известные и доказанные для одномерного случая, имеют место и для двумерного АСС, и в некоторых случаях усиливаются. Было показано, что двумерный АСС в задачах восстанов¬ления зашумленного сигнала во многих случаях предпочтительнее обыч¬ного сингулярного разложения, которое используется во многих методах обработки данных (см. раздел 5.1).
Метод АСС был применен к задаче фильтрации цифровых моделей ре-
льефа. Были разработаны методы обработки текстурных изображений на основе введения расстояния, что упрощает процедуру классификации по сравнению с известными методами, основанными на АСС (см. раз¬дел 5.2.2). На тестовых изображениях и базах данных изображений были продемонстрированы эффективность разработанных методов и преиму¬щества использования больших размеров окна.
• Были разработаны и реализованы в виде комплекса программ алгорит-мы для двумерного разложения в методе АСС и для решения различных задач обработки данных (см. раздел 5.3).
Таким образом, в диссертации были отражены теоретические и методологиче¬ские вопросы математического моделирования и разработки устойчивых алго¬ритмов, реализованных в виде комплекса программ, пригодных для решения научных и практических задач.