авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Усевич Константин Дмитриевич

АНАЛИЗ

СИНГУЛЯРНОГО СПЕКТРА В

ЗАДАЧАХ ОБРАБОТКИ ВРЕМЕННЫХ И

ПРОСТРАНСТВЕННЫХ ДАННЫХ

05.13.18 – Математическое моделирование,

численные методы и комплексы программ

ДИССЕРТАЦИЯ

на соискание ученой степени

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

Научный руководитель к. ф.-м. н., доцент Голяндина Нина Эдуардовна Санкт-Петербург – 2011 Содержание Введение................................... 6 Список основных обозначений..................... 14 Основные сведения из теории метода АСС....... Глава 1.

1.1. Операции с матрицами....................... 1.2. Базовый метод АСС......................... 1.2.1. Этап разложения...................... 1.2.2. Этап восстановления.................... 1.2.3. Комментарии к шагу группировки............ 1.3. Ряды конечного ранга и разделимость.............. 1.3.1. Ряды конечного ранга................... 1.3.2. Точная разделимость.................... 1.3.3. Приближенная разделимость и полуразделимость... 1.4. Ряды конечного ранга и линейные рекуррентные формулы.. 1.4.1. Случай конечных рядов.................. 1.4.2. Случай бесконечных рядов................ 1.5. Продолжимые ряды и прогнозирование.............. 1.5.1. ЛРФ прогноза в методе АСС и ее основные свойства.. 1.5.2. Алгоритмы прогноза в методе АСС............ 1.5.3. Побочные корни ЛРФ прогноза и их свойства...... 1.6. Модификации метода АСС..................... 1.6.1. Методы оценки параметров сигналов........... 1.6.2. Метод АСС для рядов над конечным полем....... 1.7. Метод АСС для двумерных массивов............... 1.7.1. Базовый алгоритм метода АСС для двумерных массивов 1.7.2. Частные случаи двумерного метода АСС........ 1.7.3. Метод АСС в анализе текстур: собственные фильтры. Алгебраическая теория................... Глава 2.

2.1. Структура ганкелевых матриц................... 2.1.1. Поведение ранга в зависимости от L........... 2.1.2. Структура левого ядра при d L N d + 1..... 2.1.3. Cтруктура левого ядра, L N d + 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. Полуотделимость от рядов регулярной конечно-разност ной размерности...................... 3.2.3. Перечисление случаев левой отделимости для L K. 3.2.4. Двусторонняя разделимость................ 3.3. ЛРФ прогноза и ее побочные корни................ 3.3.1. Характеристический полином ЛРФ прогноза...... 3.3.2. Основные свойства ортогональных многочленов.... 3.3.3. Асимптотические свойства побочных корней...... 3.3.4. Некоторые приложения и замечания........... 3.4. Подсчет числа матриц данного ранга в конечном поле..... 3.4.1. Сведение задачи подсчета количества ганкелевых мат риц к задаче подсчета рядов................ 3.4.2. Независимость числа рядов данного ранга от длины ряда 3.4.3. Результаты о количестве матриц и рядов........ 3.4.4. Подсчет рангов матриц с ограничениями........ 3.4.5. Нахождение количества рядов данного ранга с ограни чениями........................... Результаты для двумерного случая........... Глава 4.

4.1. Траекторное пространство и ранг массива............ 4.1.1. Траекторное пространство и основные свойства ранга. 4.1.2. Тензорное произведение рядов............... 4.1.3. (Lx, Ly )-траекторное пространство бесконечного массива 4.1.4. Полиномиальное представление массивов и оценка ли нейной сложности...................... 4.1.5. Оценки линейной сложности по диаграмме Ферре бино миального представления................. 4.2. Оценки множества допустимых размеров окна.......... 4.2.1. Оценка множества для бесконечного массива...... 4.2.2. Переход от бесконечного массива к конечному..... 4.3. Двумерная разделимость...................... 4.3.1. Разделимость произведений рядов............ 4.3.2. Разделимость бесконечных массивов конечного ранга. 4.4. Непрерывный вариант и системы в частных производных... 4.4.1. Разложение функций. Ранг функций........... 4.4.2. Линейные системы уравнений в частных производных. 4.4.3. Общий вид функций конечного ранга.......... 4.4.4. Свойства системы высшего порядка........... Численные эксперименты.................. Глава 5.

5.1. Отделимость массивов конечного ранга от шума......... 5.1.1. Описание методов очистки от шума........... 5.1.2. Массивы конечного ранга, сравнение методов...... 5.1.3. Зависимость ошибки восстановления от размеров окна и структура ошибки.................... 5.1.4. Массивы неполного ранга................. 5.2. Задачи анализа изображений.................... 5.2.1. Фильтрация цифровых моделей рельефа......... 5.2.2. Задачи анализа текстур.................. 5.3. Комплекс программ для АСС-разложения и обработки данных 5.3.1. АСС-разложение на основе вычисления ковариационной матрицы........................... 5.3.2. Быстрые вычисления с помощью БПФ.......... 5.3.3. Структура и краткое описание комплекса программ.. Заключение.................................. Литература.................................. Исходные коды комплекса программ...... Приложение А.

А.1. Ядро комплекса программ 2D-SSA................ А.2. Модуль пакета RSSA для двумерного АСС............ Введение Основными объектами исследования в диссертационной работе являются временные ряды и двумерные массивы данных.

Под вещественнозначным (комплекснозначным) одномерным временным рядом длины N 2 понимается упорядоченная последовательность веще ственных (комплексных) чисел F = (f0,..., fN 1 ), fn R (fn C). Чаще всего временной ряд является результатом измерения некоторого показателя в равноотстоящие моменты времени с шагом 0, т.е. fn = f (n), где f (t) некоторая функция, заданная при t 0;

однако, переменная t не обязательно имеет смысл времени и f может быть функцией от другого физического пара метра, например пространственной координаты [3, 7, 13]. Последовательности F = (f0,..., fN 1 ), fn K, где K конечное поле [9], описывающие измене ние категориальных показателей, будем также называть временными рядами (над конечным полем). Мы будем считать временной ряд вектор-строкой, где это необходимо.

Под двумерным массивом (вещественнозначнымиликомплекснозначным) N 1,Ny понимается таблица F = (fm,n )m,n=0 (fm,n R или fm,n C) значений x некоторой функции двух переменных f (x, y), x, y 0 на дискретной прямо угольной сетке с шагом x 0 и y 0, т.е. fm,n = f (x m, y n). Данные могут иметь разную природу: цифровые изображения [37], измерения некото рого показателя в пространстве (например высоты поверхности Земли [20]);

в качестве одной из координат может выступать время, в этом случае массив можно рассматривать как совокупность рядов, или как многомерный времен ной ряд [7]. Двумерный массив везде далее мы считаем Nx Ny матрицей.

Будем говорить, что ряд F (массив F) является суммой аддитивных со ставляющих F (1),..., F (r) (F(1),..., F(r) соответственно) если он является их суммой как векторов (или матриц): F = F (1) +...+F (r) или F = F(1) +...+F(r), т.е. в смысле покомпонентного сложения. Одной из основных задач анализа данных является выделение аддитивных составляющих различной структу ры из наблюдаемого временного ряда или массива, что и является предметом исследования в диссертационной работе.

Актуальность темы. Во многих естественных науках сложилось пред ставление о возможности описания природных процессов в виде суммы f (t) = f (T ) (t) + f (P ) (t) + f () (t) (0.1) где f (T ) (t) медленно меняющаяся составляющая, называемая трендом, ко торую часто описывают некоторой параметрической составляющей, например полиномами невысоких порядков или функциями с ограничениями на их глад кость [3, Гл. 3]1, f (P ) (t) периодическая составляющая, f () (t) шумовая составляющая, которая обычно предполагается реализацией некоторого слу чайного процесса. Наиболее распространенными задачами являются: опреде ление глобального поведения ряда (выделение тренда), обнаружение перио дичностей или удаление их из ряда (seasonal adjustment), сглаживание (выде ление низкочастотной составляющей), выделение детерминистической состав ляющей (отделение сигнала от шума).

Для различных частных случаев представления (0.1) разработаны мощ ные математические теории. Например задача f (t) = f (T ) (t) + f () (t) может решаться методами аппроксимации или регрессии (например, метод наимень ших квадратов [31]);

в случае f (t) = f (P ) (t) + f () (t), где шум предполагает ся стационарным, применимы методы спектрального анализа, основанные на теории стационарных случайных процессов и теории рядов Фурье [32, 117].

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

Анализ Сингулярного Спектра (АСС), как метод решения различных за дач анализа временных рядов, независимо появился в 70х-90х годах в России и других странах [6, 51, 84]. Основой метода АСС является этап разложения, на котором построенная по временному ряду ганкелева матрица расклады существуют и другие подходы к определению тренда [48, 97, 106] вается в сумму матриц с помощью сингулярного разложения (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]. Этап раз ложения двумерного АСС, также известный под названием eigenltering, при меняется в таких задачах анализа текстур как: классификация, сегментация, обнаружение неоднородностей (в том числе и обнаружения дефектов материа лов в промышленности) [39, 99, 105]. Также существуют методы оценки пара метров двумерных комплексных экспоненциальных сигналов, основанные на разложении в двумерном методе АСС [42, 110, 126].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы Основные результаты обсуждались на семинарах кафедры статистического моделирования математико-механического факуль тета СПбГУ, семинаре кафедры статистики в 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.

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

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

Во второй главе содержится алгебраическая теория, необходимая для решения поставленных задач. Приводится обзор алгебраической теории ган келевых матриц. Описывается теория бесконечных массивов, связанных ли нейными соотношениями. Приводятся результаты о структуре бесконечных рекуррентных массивов и об оценке их линейной сложности.

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

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

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

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

Приложение A содержит исходные коды разработанного комплекса про грамм.

Общий объем диссертации составляет 226 страниц, список литературы состоит из 128 наименований на 14 страницах.

Список основных обозначений множество (поле) вещественных чисел R множество (поле) комплексных чисел C мнимая единица i комплексное сопряжение числа x x конечное поле порядка q Fq произвольное поле K Kn n-мерное векторное пространство над K векторное пространство (над K) матриц с элементами MM,N (V) из векторного пространства V над K def пространство комплексных M N матриц MM,N = MM,N (C) A, B,... Kn векторы (векторы-столбцы) матрицы A, B, X, Y двумерные массивы A, B, F, G бесконечные двумерные массивы A, B, F, G множества индексов (подмножества N2, N2 или Z2 ) A, B, C,... j ej K L единичный вектор (0,..., 1,..., 0)T вектор из единиц (1,..., 1)T 1L K L вектор из нулей (0,..., 0)T 0L K L матрица из нулей 0LK ML,K (V) линейная оболочка векторов Aj span{A1,..., Ad } линейная оболочка столбцов матрицы A span A ранг матрицы rank A (n) биномиальный коэффициент k наибольший общий делитель чисел, многочленов gcd(L, K), gcd(P (z), Q(z)) A = (a0,..., an1 )T поэлементное комплексное сопряжение вектора A = (a0,..., an1 )T Cn A = (an,..., a0 )T перевернутый вектор A = (a0,..., an1 )T n aj z j производящий многочлен вектора A Kn A(z) = j= A(z) (A(z)) производящий многочлен комплексно сопряженного (перевернутого) вектора поэлементное комплексное сопряжение матрицы A def A = (A)T эрмитово сопряжение матрицы комплексное сопряжение подпространства Cn ортогональное дополнение подпространства Cn N одномерный временной ряд (вектор-строка) длины N FN = (fn )n= длина окна L X = X(L) (FN ) ганкелева (траекторная) матрица, построенная по вре менному ряду FN сингулярные числа j собственные (левые сингулярные) векторы Uj факторные (правые сингулярные) векторы Vj восстановленный по множеству индексов I ряд FI L(L) (FN ) L-траекторное пространство L-ранг ряда rankL FN RL (FN ) левое ядро матрицы X(L) (FN ) Ir P сдвиг вектора P Ks на r элементов с вложением в ns Kn P = (p0,..., pd )T первый характеристический вектор ранг ряда rank FN рекуррентный ранг ряда rrank FN конечно-разностная размерность ряда fdim FN () расширение ряда FN + F = (fn )+ бесконечный ряд n= минимальный многочлен ряда P (z) корни минимального многочлена k def n n ( )n = элементарный бесконечный ряд k символ Кронекера j (n) LK число ганкелевых LK матриц в конечном поле ранга r r LK,1 число ганкелевых L K матриц X конечном поле ран r га r, таких что 1L span(X) векторизация матрицы, массива vec A, vec A (M, N )-матрицирование вектора matrM,N A кронекеровское произведение матриц, массивов A B, A B покомпонентное умножение матриц, кронекеровское A B, A B произведение матриц, векторов перевернутый массив F F свертка массива F с массивом A FA (M,N ) M N -подматрица массива F Fk,l размеры массива Nx, Ny размеры окна (Lx, Ly ) W = W(Lx,Ly ) (F) (Lx, Ly )-траекторная матрица массива F собственные массивы j факторные массивы j восстановленный по множеству индексов I массив FI L(Lx,Ly ) (F) (Lx, Ly )-траекторное пространство массива F (Lx, Ly )-ранг массива F rank(Lx,Ly ) (F) (Lx, Ly )-ранг бесконечного массива F rank(Lx,Ly ) (F) L(Lx,Ly ) (F) (Lx, Ly )-траекторное пространство массива F (k, l)-сдвиг бесконечного массива Fk,l пространство сдвигов массива L(F) идеал массива I(F) ранг массива r(F) (,) элементарный бесконечный массив (,µ) биномиальный сдвиг массива конечного ранга F DF,(k,l) B (1),..., B (r) массивы коэффициентов биномиального представле ния носитель массива Supp(B) скалярное произведение Фробениуса X, Y M матричная норма Фробениуса X M расстояние, порожденное матричной нормой Фробени distM (X, Y) уса множество допустимых размеров окна M(F), M(F) мощность множества #A сумма подмножеств Z2 по Минковскому A+B граница множества индексов (A) минимальная диаграмма Ферре, содержащая A F(A) f f (,) частная производная x y Cm (D) множество функций из D R2 в R, имеющих непре рывные производные f (,) для всех + m L2 (D) множество квадратично суммируемых функций из D R2 в R F,F преобразование Фурье ряда (массива) Глава Основные сведения из теории метода АСС В отечественной литературе метод АСС традиционно более известен под названием “Гусеница” [13]. В данной диссертации используется название Ана лиз Сингулярного Спектра, как более соответствующее общепринятому в на учной литературе названию Singular Spectrum Analysis (SSA) [61, 66] 1.

К первым упоминаниям о методе АСС в России можно отнести работы 70-х гг. О.М. Калинина, М.Д. Белонина [6], М.М. Кислицина [25]. В других странах к первым работам обычно относят [46, 51, 84]. Метод АСС активно развивался в Санкт-Петербургском государственном университете, в особен ности коллективом сотрудников кафедры статистического моделирования под руководством С.М. Ермакова.

В 1997 г. сотрудниками кафедры был выпущен сборник работ, посвящен ный методу АСС (“Гусеница”) [13]. В 2001 г. вышла монография N. Golyandina, V. Nekrutkin, A. Zhigljavsky “Analysis of Time Series Structure: SSA and Related Techniques” [66], которая на текущий момент является основным трудом по ме тоду АСС. Эти работы лежат в основе данной главы. Мы будем, в основном, придерживаться обозначений из [66].

1.1. Операции с матрицами Для векторного пространства V над полем K обозначим MM,N (V) про странство M N матриц над полем K, изоморфное пространству V M N. Будем сокращать MM,N (C) до MM,N.

Пусть X = (xkl )M,N и Y = (ykl )M,N матрицы из MM,N. Тогда k,l=1 k,l= M N def (1.1.1) = xkl ykl X, Y M k=1 l= Также в некоторых работах встречается название “сингулярный спектральный анализ” [24].

задает скалярное произведение матриц из MM,N и и M N def ||X||2 = |xkl |2 (1.1.2) = X, X M M k=1 l= задает квадрат матричной нормы (Фробениуса) и def (1.1.3) distM (X, Y) = ||X Y||M.

задает расстояние.

Введем изоморфизм между пространствами MM,N и CM N с помощью следующих двух операторов.

Определение 1.1.1. Векторизацией (см. например [91]) m n матрицы A = {amn }M,N будем называть вектор, составленный из столбцов A:

m,n= def vec A = (a11,..., aM 1 ;

a12,..., aM 2 ;

... ;

a1N,..., aM N )T CM N. (1.1.4) Например, vec 2 5 = (1, 2, 3, 4, 5, 6)T.

Определение 1.1.2. (M, N )-Матрицированием вектора X CM N будем на def зывать матрицу размера M N A = matrM,N (X), такую что vec A = X.

Замечание 1.1.1. Заметим, что vec является изометрией из MM,N в CM N :

= vec X, vec Y 2, X, Y M ||X||2 = || vec(X)||2, M = X Y стандартное скалярное произведение в CM N.

где X, Y Определим также операцию кронекеровского произведения [91].

Определение 1.1.3. Пусть A = {akl }M,N MM,N и B = {bkl }T,S MT,S k,l=1 k,l= две матрицы размера M N и T S соответственно. Кронекеровским произведением A B называется матрица размера M T N S:

a11 B... a1N B.. M def AB =.. (1.1.5) M,N (MT,S ) = MM T,N S,..

aM 1 B... aM N B т.е. блочная M N матрица с T S блоками.

Отметим некоторые свойства кронекеровского произведения.

Предложение 1.1.1 ([87, Th. 13.3]) Для любых A Mm,n, B Mr,s, C Mn,p, D Ms,t выполняется (A B)(C D) = AC BD.

Предложение 1.1.2 ([87, Th. 13.4]) Для любых матриц A и B (A B)T = AT BT.

Предложение 1.1.3 ([87, Th. 13.26]) Для любых матриц A, B и C, для ко торых определено произведение ABC имеет место равенство vec(ABC) = (CT A) vec B.

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

1.2.1. Этап разложения Пусть F = FN = (f0,..., fN 1 ) CN комплекснозначный временной ряд длины N 2, и L некоторое фиксированное натуральное число, назы ваемое длиной окна, 1 L N.

Вложение Шаг вложения образует K = N L + 1 векторов вложения Xn = Xn = (fn1,..., fn+L2 )T CL, (L) (1.2.1) 1 n K.

L-Траекторная матрица (или просто траекторная матрица) ряда F (1.2.2) X = [X1 :... : XK ] состоит из векторов вложения как столбцов. Другими словами, траекторная матрица имеет вид f0 f1 f2... fK f1 f2 f3... fK =, (xmn )L,K X = X(L) = (1.2.3) f2 f3 f4... fK+ m,n=....

...

....

....

fL1 fL fL+1... fN где xmn = fm+n2, т.е. матрица X ML,K (C) имеет одинаковые элементы на антидиагоналях n + m = const. Матрицы такой структуры называются ганкелевыми. Существует очевидное взаимно-однозначное соответствие меж ду ганкелевыми матрицами размерности LK и рядами длины N = L+K 1.

Сингулярное разложение С траекторной матрицей производится сингулярное разложение (singular value decomposition, SVD) [11, 58, 118] d j Uj Vj, (1.2.4) X= j= сингулярные числа, {Uj }d, {Vj }d где 1... d 0 ортонормиро j=1 j= ванные системы левых и правых сингулярных векторов.

Пусть S = XX. Тогда 1,..., d являются всеми ненулевыми собствен 2 ные числа матрицы S, взятыми в невозрастающем порядке, а U1,..., Ud система собственных векторов матрицы S, соответствующих собственным числам. Правые сингулярные векторы можно получить как Vj = X Uj /j, j = 1,..., d.

В соответствии с [16, 66] будем называть векторы Uj собственными век факторными векторами, а набор (j, Uj, Vj ) мы будем называть торами, Vj j-й собственной тройкой сингулярного разложения (1.2.4).

1.2.2. Этап восстановления Группировка На основе разложения (1.2.4) процедура группировки делит все множе ство индексов {1,..., d} на r непересекающихся подмножеств J1,..., Jr. Тогда разложение (1.2.4) может быть записано в сгруппированном виде r (1.2.5) X= XJk, k= где XJ сгруппированная по множеству индексов J {1,..., d} компонента:

j Uj Vj.

XJ = jJ Процедура выбора множеств J1,..., Jr называется группировкой собственных троек.

Ортогональное проецирование (диагональное усреднение) На последнем шаге базового алгоритма каждая матрица сгруппированно го разложения (1.2.5) преобразуется в ряд длины N. Сначала матрицам XJk сопоставляются ганкелевы матрицы XJk вида (1.2.3) с помощью линейного оператора ганкелизации.

Определение 1.2.1. Пусть V некоторое евклидово пространство. Дей ствие оператора ганкелизации H V : ML,K (V) MH (V) для матрицы L,K L,K ML,K (V) определяется как A = am,n m,n= aa... aK 1 2 a a... aK+ 2, ak = am,n #Dk, H VA =......

...... (m,n)Dk aL aL+1... aL+K где Dk = {(m, n) N : 1 m L, 1 n K, m + n = k + 1}, а #A обозначает мощность множества A.

Тогда, если обозначить XJk = H C XJk, разложение (1.2.5) превращается в разложение r X= XJk.

k= Затем каждой ганкелевой матрице XJk однозначно ставится в соответствие ряд F (k) длины N, который называется восстановленным по набору индексов Jk рядом. Таким образом, разложение ряда в сумму восстановленных рядов принимает вид r F (k). (1.2.6) F= k= Это разложение является результатом работы базового метода АСС.

1.2.3. Комментарии к шагу группировки Наиболее сложным шагом метода является шаг группировки. Группиров ка зависит от конкретной задачи решаемой в рамках метода АСС, например в задаче выделения параметрического сигнала из шума группировкой может быть J1 = {1,..., m}, J2 = {m + 1,..., d}, где первые m компонент соответ ствуют сигналу. В базовом методе АСС [13, 66] группировка выбирается иссле дователем, и этап разложения предоставляет дополнительную информацию, по которой можно судить о принадлежности собственных троек интересую щим составляющим.

Пусть наблюдается сумму составляющих F = F (1) +... + F (m), например тренда, периодических составляющих, шума. На шаге группировки необходи мо сгруппировать собственные тройки (элементарные слагаемые разложения (1.2.4)). В этой связи возникают следующие вопросы:

• Существует ли группировка, результатом которой является разложение F в сумму исходных компонент F (k) ?

• Как идентифицировать собственные тройки, соответствующие F (k) ?

Для ответа на первый вопрос в теории метода АСС вводится понятие точной разделимости рядов F (1),..., F (m) с помощью АСС-разложения как возможность точно выделить их из суммы;

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

Если компоненты разделимы, то возникает вопрос: как идентифициро вать соответствующие компоненты? Основной идеей группировки в базовом алгоритме метода АСС является следующая: собственные и факторные век торы в особенности повторяют поведение соответствующих компонент, так как они являются базисами пространств строк и столбцов сгруппированных матриц (1.2.5). Векторы, соответствующие периодическим компонентам тоже являются периодическими (если их также рассматривать как ряды);

векто ра, соответствующие тренду медленно меняющимися. Существуют методы автоматической идентификации составляющих [1]. Собственные числа дают информацию о вкладе компонент. Есть дополнительные средства для иденти фикации, например, взвешенные корреляции [16, 66].

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

1.3. Ряды конечного ранга и разделимость В этом разделе вводятся основные понятия теории метода АСС: разде лимость, как способность АСС-разложения разделять ряд на составляющие ряды, и класс рядов конечного ранга, описывающих структуру компонент в рамках метода АСС. Ряды конечного ранга в рамках АСС разложения впер вые исследованы в [47], а понятие разделимости было введено в [35].

1.3.1. Ряды конечного ранга Определение 1.3.1. Определим L-траекторное пространство как def (L) (L) L(L) = L(L) (FN ) = span X1,..., XN L+1 = span(X(L) ) KL, (1.3.1) (L) где Xn из (1.2.1) столбцы траекторной матрицы.

Будем называть L-рангом временного ряда FN def rankL (FN ) = dim L(L) (FN ) = rank X. (1.3.2) Замечание 1.3.1. L-Ранг ряда равен d тогда и только тогда, когда суще ствуют линейно независимые наборы функций j : {0,..., L 1} C и j : {0,..., K 1} C, 1 j d, такие что d (1.3.3) fn+l = j (n)j (l) j= для 0 n L, 0 l K.

Интерес представляют ряды, ранг которых, в основном, не зависит от длины окна, так называемые ряды конечного ранга [66].

Определение 1.3.2. Если rankL (FN ) = d для любых d min(L, K), то бу def дем говорить, что ряд FN имеет ранг d (rank(FN ) = d). Будем говорить, что ряд имеет конечный ранг (d), если d N/2.

Вид ранга для ряда конечного ранга изображен на рис. 1.1. Известно [74], что Рис. 1.1. Поведение ранга для ряда конечного ранга ранг определен для любого ряда, при этом почти все ряды имеют конечный ранг кроме случая, когда L-траекторная матрица имеет полный ранг для лю бого L. Это будет показано в разделе 2.1, и обосновано условие d N/22, что означает, например, что все ряды четной длины имеют конечный ранг.

Пример 1.3.1. Примерами рядов конечного ранга, по замечанию 1.3.1, явля ются:

комплексная экспонента;

• fn = c exp(n), C ряд ранга 1: fn+l = c exp(n) exp(l).

• fn = cos(2n + ), (0, 0.5), R;

ряд ранга 2: fn+l = cos(2n + ) cos(2l) cos(2n + ) cos(2l).

• fn = Pm (n), где Pm (n) комплексный полином степени m.

m dj Pm lj ряд ранга m + 1: fn+l = dnj (n) j!

j= В общем случае верно следующее утверждение.

Заметии, что в [17] это условие имеет вид d N/2, а в [16, 66] оно вообще опущено Предложение 1.3.1. Ряды, являющиеся суммой произведений полиномов и комплексных экспонент являются рядами конечного ранга для достаточно больших N.

В разделе 1.4 будет подробнее охарактеризован класс рядов из предложе ния 1.3.1.

1.3.2. Точная разделимость Пусть имеются два ряда F (1) and F (2) и зафиксирована длина окна. Рас смотрим SVD-разложение L-траекторной матрицы суммы рядов F = F (1) + F (2) :

d i Ui Vi T. (1.3.4) X= i= Если мы обозначим X1 и X2 L-траекторные матрицы рядов F (1) и F (2), то вопрос о разделимости рядов можно сформулировать следующим образом:

cуществует ли группировка {J1, J2 }, такая что j Uj Vj и X(2) = j Uj V j ?

X(1) = jJ1 jJ Заметим, что в случае кратных собственных чисел разложение SVD (1.3.4) не единственно. Поэтому вводятся понятия сильной и слабой разделимости.

Определение 1.3.3. Два ряда F (1) и F (2) называются слабо L-разделимыми, если пространства столбцов и строк их траекторных матриц ортогональны:

L(L) (F (1) ) L(L) (F (2) ) и L(K) (F (1) ) L(K) (F (2) ).

Определение 1.3.4. Два ряда F (1) и F (2) сильно L-разделимы, если они сла бо L-разделимы и наборы сингулярных чисел матриц X1 и X2 не пересекают ся.

Замечание 1.3.2. Сильная разделимость двух рядов означает, что любое сингулярное разложение матрицы X допускает нужную группировку. Слабая же разделимость означает существование такого сингулярного разложения.

Чаще всего объектом исследования является слабая разделимость. Приведем примеры слабой разделимости для вещественнозначных рядов.

Пример 1.3.2. Ряд F = (f0,..., fN 1 ) с fn = cos (2n + ) L-отделим сле ва от ненулевого константного ряда (c,..., c)T, если L и K являются целы ми числами.

Пример 1.3.3. Два ряда (1) (2) and fn = cos (22 n + 2 ) fn = cos (21 n + 1 ) L-разделимы тогда и только тогда, когда 1 = 2, 0 1, 2 1/2 и L1, L2, K1, K2 являются целыми числами.

Эти примеры можно найти в [66]. В разделе 3.2 будет показано, как можно най ти все случаи точной разделимости с помощью разработанного в разделе 3. алгебраического критерия.

1.3.3. Приближенная разделимость и полуразделимость При анализе реальных данных трудно ожидать точной разделимости, по этому имеет смысл определить понятие приближенной разделимости. Наибо лее важным свойством метода АСС является способность выделить траектор (1) (1) (2) ное пространство L(1) (FN ) из суммы FN = FN + FN, поэтому приближен ную разделимость можно определить в терминах возмущения траекторного пространства [101].

d (1) (1) (1) Uj (Uj ) Пусть FN имеет L-ранг d1 и 1 = ортогональный про j= (1) (1) и {Uj }d (L) ектор на траекторное пространство L собственные век (FN ), j= (1) тора. Допустим, что в сингулярном разложении FN компоненте FN будут (12) d соответствовать первые d1 собственных векторов {Uj }j=1 (все собственные (1) (2) числа, соответствующие FN больше таковых для FN ). Тогда в качестве меры разделимости можно предложить спектральную норму разности проекторов d (1) (2) (12) (12) = 12 1 2, где 12 = проектор на возмущен (FN, FN ) Uj (Uj ) j= ное пространство. В [101] методами теории возмущений линейных операторов исследуется зависимость от размеров рядов, длины окна и величины второго ряда.

Рассмотрим также понятие односторонней разделимости (или полуразде лимости), при котором лишь одно из условий в определении 1.3.3 выполняется.

Определение 1.3.5. Два ряда F (1) и F (2) называются слабо L-полуразде лимыми, если пространства столбцов их траекторных матриц ортогональны L(L) (F (1) ) L(L) (F (2) ).

Замечание 1.3.3. Таким образом, два ряда слабо слабо L-разделимы, если они слабо L- и K-полуразделимы.

Полуразделимость (точная и приближенная, т.е. асимптотическая ортого нальность) влияет на порядок сходимости [101], поэтому она также является важным понятием.

1.4. Ряды конечного ранга и линейные рекуррентные формулы В этом разделе рассматриваются известные в рамках теории метода АСС [8, 13, 66] связи между рядами конечного ранга и рядами, удовлетворяющими линейным рекуррентным формулам. Последний класс рядов также важен для описания структуры ряда в АСС и для АСС-прогноза.

1.4.1. Случай конечных рядов Среди рядов конечного ранга выделяется следующий подкласс рядов.

Определение 1.4.1. Ряд FN удовлетворяет линейной рекуррентной фор муле (ЛРФ) порядка, если существуют коэффициенты a1,..., a C, такие что для любого n {0,..., N 1 } выполняется (1.4.1) fn+ = ak fn+k.

k= Будем называть ЛРФ реверсивной, если a0 = 0. Определение 1.4.2. Рекуррентным рангом ряда FN, rrank FN, (конечно-раз ностной размерностью ряда FN, fdim FN ) называется минимальная размер ность ЛРФ (минимальная размерность реверсивной ЛРФ), которой он удовле творяет. Если F 0 мы полагаем fdim FN = rrank FN = 0.

Будем называть ряд рядом конечного рекуррентного ранга, если рекур рентный ранг для нее определен, и реверсивным рядом 4, если определена конечно-разностная размерность.

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

Если ряд удовлетворяет ЛРФ (1.4.1), то все столбцы траекторной матри цы можно выразить через первых ее столбцов, и верно следующее соотно шение между рекуррентным рангом и рангом ряда.

Предложение 1.4.1 ([66, Prop 5.4]) Пусть FN удовлетворяет ЛРФ (1.4.1) порядка, min(L, K) (т.е. rrank FN и fdim FN если ЛРФ ревер сивна). Тогда rank FN. Если к тому же первые столбцы траекторной (L) (L) матрицы X1,..., X линейно независимы, то rank FN = = rrank FN.

Если при этом ЛРФ реверсивна, то fdim FN =.

Таким образом, ранг любого ряда не превосходит (и в большом количестве слу чаев равен) рекуррентному рангу и конечно-разностной размерности ряда. В В [66] принято другое опеределение: если a0 = 0, то ряд управляется ЛРФ. В данной работе используется другое обозначение, согласованное с [14], т.к. это свойство ЛРФ, а не ряда.

В [14] реверсивная последовательность.

разделе 3.1 мы установим точные соотношения между рангом, рекуррентным рангом и конечно-разностной размерностью для конечных рядов.

Также известен результат о том, что любой ряд конечного ранга удовле творяет реверсивной ЛРФ, за исключением конечного числа элементов в на чале и в конце ряда.

Теорема 1.4.1 ([66, Th. 5.1]) Пусть 1 rankL (FN ) = d L. Тогда суще ствуют целые числа d0 и M, такие что 0 d0 d, 0 M d d0 и fdim (fM,..., fM +K+d0 1 ) = d0.

Таким образом, из любого ряда можно получить ряд, обладающий конечно разностной размерностью, “отрезать” небольшое количество элементов из на чала и из конца ряда. К недостаткам утверждения можно отнести его зави симость от L. В разделе 3.1 мы покажем, как найти минимальное количество элементов, которые необходимо отрезать, чтобы получить реверсивный ряд.

1.4.2. Случай бесконечных рядов Рассмотрим бесконечный ряд (над произвольным полем K) (1.4.2) fn K.

F = (f0, f1,...), Определение 1.4.3. Будем говорить, что бесконечный ряд F удовлетворя ет линейной рекуррентной формуле порядка если равенство (1.4.1) выполня ется для всех n N0. Если a0 = 0 то ЛРФ называется реверсивной. Порядока ЛРФ fn = 0 полагается равным 0. Такая ЛРФ считается реверсивной.

Рекуррентным рангом rrank F ряда (конечно-разностной размерностью, fdim F ) будем называть минимальную размерность ЛРФ (минимальную раз мерность реверсивной ЛРФ), которой он удовлетворяет.

Каждой ЛРФ (1.4.1) будем ставить в соответствие ее характеристиче ский многочлен A(z) = z a1 z 1... a1 z a0. (1.4.3) Характеристический многочлен ЛРФ fn = 0 полагается равным 1.

Теорема 1.4.2 ([14, Гл.XXV, § 5, Т.8]) Пусть бесконечный ряд F удовлетво ряет ЛРФ (1.4.1). Тогда он может быть представлен в виде 0 m Pk (n)n (1.4.4) fn = + cj j (n), k j= k= ненулевые многочлены степени k 1, k 0, cj где Pk комплексные константы, причем c0 1 = 0, 0 0, а j (n) символ Кронекера 1, n = j j (n) = 0, иначе.

В выражении (1.4.4) полагается m = 0 или 0 = 0, если левая или правая сумма отсутствует соответственно. При этом k C\{0} корни харак теристического многочлена A(z) с кратностями не менее k, k = 1,..., m, а 0 не превосходит кратность корня 0 многочлена A(z).

При этом число m, корни k, коэффициенты Pk и cj определяются пер выми значениями временного ряда.

Замечание 1.4.1. Если ряд обладает представлением (1.4.4), то это представ ление единственно. Это следует из линейной независимости последовательно стей вида gn = nk n и j (n) для различных C \ {0} и k, j N0.

По замечанию 1.4.1 для временного ряда вида (1.4.4) однозначно опреде лен многочлен def P (z) = (z 1 )1 ·... · (z m )m = (1.4.5) = pd z d +... + p1 z + p0, где pd = 1 и (1.4.6) d = 1 +... + m.

Таким образом, теорему 1.4.2 можно переформулировать следующим об разом.

Следствие 1.4.1. Пусть задан многочлен B(z) = br z r +... b1 z + b0. (1.4.7) Если временной ряд вида (1.4.4) удовлетворяет ЛРФ r bk (1.4.8) n N0, fn+r = fn+k, br k= то многочлен B(z) делится на многочлен (1.4.5), т.е. B(z) = P (z)Q(z).

Верно и обратное утверждение.

Теорема 1.4.3 ([14, Гл. XXV, Утв. 6–8]) Если многочлен (1.4.7) делится на многочлен (1.4.5), то ряд вида (1.4.4) удовлетворяет ЛРФ (1.4.8).

Следствие 1.4.2. Если ряд имеет вид (1.4.4), то rrank F = d, где d опре делено в (1.4.6), и ЛРФ d (1.4.9) fd+n = pk fk+n, k= соответствующая многочлену (1.4.5), является единственной ЛРФ порядка d, которой удовлетворяет ряд.

Многочлен (1.4.5) называется минимальным (порождающим) многочле ном ряда F.

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

Замечание 1.4.2. По следствию 1.4.1 ряд F является реверсивным тогда и только только тогда, когда свободный член p0 минимального многочлена не равен 0. При этом fdim F = rrank F.

Нам будут также важны представления реверсивных рядов, описанные след ствиями теоремы 1.4.2.

Следствие 1.4.3. Ряд имеет конечно-разностную размерность d и мини мальный многочлен (1.4.5) тогда и только тогда, когда ряд F имеет пред ставление m Pk (n)n, (1.4.10) fn = k k= где степени Pk равны k 1.

Следствие 1.4.4. Вещественнозначный ряд удовлетворяет конечно-разност ному уравнению тогда и только тогда, когда он имеет вид d d Pmk (n) n cos(2k n (k) Pmk (n) n.

(k) (1.4.11) fn = + k ) + k k k=1 k=d + При этом корнями минимального многочлена P (z) являются 1 e2i1, 1 e2i1,..., d e2id, d e2id, d +1,..., d, где 1,..., d R и 0 k, k 0. 1.5. Продолжимые ряды и прогнозирование Прогноз в методе АСС основан на понятии продолжимости и связи между конечными продолжимыми рядами и бесконечными рядами.

Определение 1.5.1. Ряд FN называется L-продолжимым, или допускающим L-продолжение, если существует единственное, такое что для расширенного ряда () (1.5.1) FN +1 = (f0,..., fN 1, ) () ранг сохраняется, т.е. rankL (FN +1 ) = rankL (FN ).

Известно следующее свойство:

Теорема 1.5.1 ([66, Th. 5.4]) Если ряд FN удовлетворяет ЛРФ (1.4.1), по рядка min(K, L 1), то ряд L-продолжим и продолжение может быть получено с помощью той же ЛРФ, т.е. = a1 fN 1 +... + a0 fN.

Следствие 1.5.1. Если ряд FN удовлетворяет ЛРФ (1.4.1), то он един ственным образом может быть L-продолжен до бесконечного ряда F, удо влетворяющего той же ЛРФ.

Есть также следующее характеризующее свойство продолжимости.

Предложение 1.5.1. Ряд FN L-продолжим тогда и только тогда, когда eL L(L) (FN ).

/ Введем некоторые обозначения. Для подпространства KL в случае K = R, C будем обозначать def = {X KL : X, Y = 0 для любого Y } K его ортогональное дополнение.

Для вектора V = (v0,..., vL1 )T CL будем обозначать V = (v0,..., vL1 )T его комплексное сопряжение. Для случая подпространства CL определим сопряженное подпространство как def = {X CL : X }.


1.5.1. ЛРФ прогноза в методе АСС и ее основные свойства некоторое подпространство CL, обладающее свойством eL, Пусть и выбран его ортонормированный базис {U1,..., Ud } CL. Обозначим Uk =, где Uk CL1 и k C. Определим вектор R = (a0,..., aL1 )T CL Uk k как d (1.5.2) R= k Uk, 1 k= d где 2 = |1 |2 +... + |d |2 = | Ui, eL |2 1. Последнее неравенство выпол i= няется, так как eL. Следующее предложение является вариантом теоремы [66, Ch. 5, Th. 5.2] для комплекснозначного случая.

Предложение 1.5.2. Пусть FN временной ряд рекуррентного ранга d, 1 d L и = L(L) (FN ). Тогда FN удовлетворяет ЛРФ L (1.5.3) 0 n N L 1, fn+L = ak fn+k, k= коэффициенты ak которой определяются (1.5.2).

ЛРФ (1.5.3) для краткости будем называть ЛРФ прогноза, так как она лежит в основе алгоритмов прогноза в методе АСС, см. [66, Ch. 2].

Рассмотрим сопряжение ортогонального дополнения R = подпростран ства. Следующее предложение является модификацией [66, Ch. 5, Prop. 5.5] для комплекснозначного случая.

Предложение 1.5.3. Вектор A = (RT, 1)T = (a0,..., aL1, 1)T, (1.5.4) R определен в (1.5.2), может быть выражен как (1.5.5) A = c R eL, ортогональный проектор на пространство R и c = (1 2 )1 = где R.

R eL, eL По предложению 1.5.3, вектор коэффициентов ЛРФ прогноза (1.5.4) совпадает с Min-Norm вектором [82, 83] оценки параметров сигнала (метод оценки будет описан в разделе 1.6.1). Название этому вектору дано в связи с его следующим экстремальным свойством, доказательство которого можно найти, например, в [85].

Предложение 1.5.4. Вектор (1.5.4) имеет минимальную сумму квадратов |a0 |2 + |a1 |2 +... + |aL1 |2 (1.5.6) среди векторов из R с последней координатой равной 1.

1.5.2. Алгоритмы прогноза в методе АСС Основным алгоритмом прогноза является рекуррентный прогноз [17, 66].

Пусть F = F (1) + F (2), и с помощью АСС-разложения окном L мы приближен но выделили компоненту F (1) и 1 приближение её траекторного простран ства L(L) (F (1) ). Тогда ЛРФ прогноза (1.5.3) R, полученная по R, является приближением [64, 101] ЛРФ прогноза R, полученной из невозмущенного про странства L(L) (F (1) ).

Таким образом, одношаговый алгоритм прогноза выглядит следующим образом.

Алгоритм 1.5.1.

(1) (1) 1. Найти F (1) = (f0,..., fN 1 ) и 1.

2. Оценить коэффициенты приближенной ЛРФ R = (a0,..., aL2 ) по ра венству (1.5.3).

L (1) 3. Построить одношаговый прогноз как al fN L+1+l.

fN = l= Применяя последовательно шаг 3 алгоритма 1.5.1, можно найти m-шаговый прогноз.

Существуют также и другие алгоритмы прогноза на основе АСС метода, например, векторный прогноз [17, 66]. Анализ точности аппроксимации и ка чества прогноза можно найти в [64, 101]. Похожим образом может решаться и задача заполнения пропусков в данных [18, 67].

1.5.3. Побочные корни ЛРФ прогноза и их свойства Зафиксируем ряд FN конечно-разностной размерности d с характеристи ческим полиномом P (z). Пусть также длина окна L удовлетворяет d L N d+1 и = L(L) (FN ). Если A(z) производящий многочлен вектора (1.5.4), то по следствию 1.4.1 A(z) = P (z)H(z). Таким образом, среди корней A(z) есть d главных корней (соответствующих P (z)) и L d 1 побочных корня.

С точки зрения устойчивости прогноза [17], а также в методах оценки пара метров [82, 83] интерес представляет поведение побочных корней, в частности асимптотика при L.

Известны следующие результаты:

• Все побочные корни лежат внутри единичного круга [83];

• Побочные корни ЛРФ прогноза сопряжены побочным корням ЛРФ про гноза для перевернутого ряда FN [44] (ЛРФ прогноза назад );

• Побочные корни ЛРФ прогноза слабо сходятся к распределению на окруж ности некоторого радиуса [103].

Все эти результаты доказываются разными методами: теории линейного пред сказания стационарных процессов [83], матричными методами [44], теории ор тогональных многочленов на единичном круге [103]. В диссертации показано, что все эти результаты единообразно и просто можно доказать на языке орто гональных многочленов, где используются современные результаты о сильной асимптотике корней ортогональных многочленов [95, 96].

1.6. Модификации метода АСС В данном разделе рассматриваются рассматриваются методы решения различных задач анализа данных в рамках метода АСС.

1.6.1. Методы оценки параметров сигналов Пусть FN реверсивный ряд конечного ранга d с минимальным много членом P (z), т.е. FN имеет вид (1.4.10), и наблюдается зашумленный сигнал GN = FN +, где шум (например, белый гауссовский). Задача состоит в нахождении параметров в представлении (1.4.10) для незашумленного сиг нала. Для простоты будем предполагать, что ранг d известен. Общая схема методов такова.

1. По ряду GN с окном L производятся шаги вложения и разложения базо вого метода АСС.

2. Выбираются первые d собственных векторов {U1,..., Ud } и по ним оце ниваются корни P (z).

3. Затем, обычно методом наименьших квадратов [31] находятся коэффи циенты в представлении (1.4.10).

Чаще всего рассматривается случай простых корней, т.е.

m ck n.

fn = k k= Оценки с помощью Min-norm вектора Пусть A(z) производящий многочлен вектора (1.5.4). Тогда для нахож дения корней P (z) достаточно отбросить побочные корни A(z), что можно сде лать используя свойства побочных корней. Тот факт, что все корни находятся внутри единичного круга, лежит в основе метода root-Min-Norm [82, 85, 117] для оценки параметров в сумме комплексных экспонент. В предположении, что все корни истинного ряда имеют модуль не менее 1, в этом методе в ка честве оцененных корней ряда выбираются d наибольших по модулю корней из приближенной ЛРФ (1.5.2). Если все корни ряда имеют модули более 1, из асимптотического распределения корней следует, что метод root-Min-Norm применим в данном случае. При наличии умеренного шума, главные и побоч ные корни оцененной ЛРФ находятся близко к корням оцененной ЛРФ (см., например, [85]). На рис. 1.2 изображен зашумленный ряд с корнями оцененной ЛРФ прогноза. Если какие-то корни лежат на единичном круге, то этот метод работает хуже: эти корни при больших L оцениваются хуже, так как вместо корней ряда могут быть выбраны побочные корни.

Если все корни ряда имеют модули менее 1, этот метод не работает. Да же если все корни ряда лежат на критической окружности, побочные корни L = 50, N = 1. 0. X 0. f_n X 0. X 1. 1.0 0.5 0.0 0.5 1. 0 20 40 60 80 n Рис. 1.2. Слева: временной ряд, Справа: корни ряда (x) и побочные корни ЛРФ прогноза cos(0.5n) + n, n are i.i.d. N (0, 502 ), (o), fn = 1.05n + 1.1n могут иметь больший модуль, как показано на рис. 1.3. Однако в этом случае можно оценивать ЛРФ прогноза назад, у которой главные корни находятся вне единичного круга, см. [85].

L = 32, mult = 3, std = 0 L = 32, mult = 3, std = 0. 1. 1. 0. 0. 0. 0. X X 0. 0. 1. 1. 1.0 0.5 0.0 0.5 1.0 1.0 0.5 0.0 0.5 1. Рис. 1.3. Корни ряда (x) и побочные корни ЛРФ прогноза (o), fn = n2 0.8n + std · n, n i.i.d. N (0, 1), N = 150.

На рис. 1.3 изображены корни ЛРФ прогноза для незашумленного ряда и ряда с добавлением белого шума.

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

Существуют и другие методы оценки параметров, основанные на АСС разложении (например, ESPRIT [111]).

1.6.2. Метод АСС для рядов над конечным полем Для категориальных последовательностей, здесь рассматриваются, в ос новном, дихотомические последовательности над полем F2, актуальной являет ся задача о поиске скрытых периодичностей в данных [2] и шаблонов в данных [21]. Среди приложений можно указать анализ геномных последовательностей и другие приложения в биологии и медицине [21].

Задачу можно решить с помощью метода АСС. По временному ряду FN FN и длине окна строится ганкелева матрица X(L) (FN ), которая затем, по аналогии с SVD, некоторым оптимальным образом приближается матрицей фиксированного ранга r (L) Uj VjT.

X j= В качестве критерия оптимальности может выбираться последовательная мак симизация энтропии [2] или другие критерии [21]. Рассмотрим способ опреде ления близости для последовательностей, основанный на многомерном вложе нии, который сильно связан с разложением по методу максимизации энтропии [2].

Определим расстояние Хэмминга между векторами A, B FL как L |aj bj |, 0 (A, B) = j= т.е. количество замен, которое необходимо для получения одного вектора из другого. В анализе реальных данных имеет смысл также следующее расстоя ние [40]:

1 (A, B) = min{1 (A, B), 1 (A + 1L, B)}, так как если мы ищем зависимость одного признака от других в смысле ли нейных соотношений в F2, то разумно допускать возможность неправильного обозначения значения признака (замена 0 на 1). Определим для k = 0, 1 рас стояние между рядом и вектором следующим образом:

(L) k (FN, A) = min k (A, B).

BL(L) (FN )\{0} Ноль исключается так как для векторов с небольшим количество единиц, но мало связанных с временным рядом расстояние до нуля мало.

(L) При измерении расстояния с помощью k возникает следующий есте ственный вопрос: насколько часто встречается то количество ошибок, которое наблюдалось при конкретном измерении? Этот вопрос можно формализовать следующим образом. Пусть (, F, P) вероятностное пространство, на кото ром задано два независимых равномерно распределенных случайных вектора V FL и F FN, или X = X(L) (F ) является равномерно распределенной мат 2 рицей в пространстве HLK ML,K (F2 ) ганкелевых L K матриц. Требуется (L) найти функцию распределения случайной величины k = k (, ), т.е.

Fk (t) = P(k t).

По функции распределения можно оценить, насколько тот или иной уровень ошибок случаен (проверить гипотезу о случайности классификации).

Базовой задачей является задача нахождения Fk (0), т.е. следующих ве роятностей:

F0 (0) = P(V span(X)), F1 (0) = P(V span(X) или V + 1L span(X)).


Легко видеть, что P(V span(X) или V + 1L span(X)) = = 2F0 (0) P(V span(X), 1L span(X)).

При этом, полагая L K, получаем L r 2r /2L LK r= F0 (0) =, 2N LK где r число ганкелевых L K матриц ранга r над F2, и L LK,1 2r /2L r r= P(V span(X), 1L span(X)) =, 2N где LK,1 число ганкелевых L K матриц ранга r над F2, содержащих r LK в пространстве столбцов вектор 1L. Заметим, что задача нахождения r довольно хорошо известна, см. например [55]. Задача же нахождения LK,1, r насколько известно автору, не ставилась и не решалась.

1.7. Метод АСС для двумерных массивов Алгоритм метода АСС для разложения двумерных случайных полей был предложен в [13], однако частично (без восстановления) метод был, по-видимо му, впервые предложен в работах по текстурному анализу [39]. Кроме этого, есть большое количество работ по оценке параметров двумерных сигналов [42, 110, 126] используют этап разложения алгоритма АСС. Для описания ал горитма нам потребуются некоторые обозначения.

1.7.1. Базовый алгоритм метода АСС для двумерных массивов Пусть имеется двумерный Nx Ny массив F f f0,1... f0,Ny 0,0 f f1,1... f1,Ny 1,0 F=..

..

...

...... fNx 1,0 fNx 1,1... fNx 1,Ny Алгоритм двумерного метода АСС состоит из тех же шагов, что и одномер ный: вложения, разложения, группировки и ортогонального проецирования, объединенных в два этапа: разложения и восстановления.

В двумерном случае траекторная матрица строится по двумерным сколь зящим окнам, поэтому алгоритм имеет пару параметров: размеры окна (Lx, Ly ), удовлетворяющие условиям 1 Lx Nx, 1 Ly Ny.

1 l Ny 1 pp pp k ppppppppp Fk,l 6x L  -?

Ly Nx Рис. 1.4. Скользящее окно Этап разложения Вложение (M,N ) Обозначим Fk,l следующую M N подматрицу:

fk,l... fk,l+N.....

=..

(M,N ). (1.7.1)..

Fk,l fk+M 1,l... fk+M 1,l+N Тогда скользящее окно с размерами (Lx, Ly ) порождает K = Kx Ky def (L,Ly ) таких подматриц Fk,lx 0 k Kx, 0 l Ky, где Kx = Nx Lx + 1 и def Ky = Ny Ly + 1. Будем накладывать также ограничение 1 Lx Ly Nx Ny, def чтобы не рассматривать вырожденные случаи. Будем также обозначать L = def Lx Ly 1, K = Kx Ky 1.

Результатом шага вложения является матрица W W = [W1 :... : WK ], столбцы Wm которой являются векторизациями скользящих (Lx, Ly )-окон, т.е.

(L,Ly ) ) для 0 k Kx, 0 l Ky. (1.7.2) W1+k+lKx = vec(Fk,lx (L,Ly ) Заметим, что столбцы, соответствующие подматрицам Fk,lx располагаются в порядке векторизации. Таким образом, строки матрицы W являются векто ризациями Kx Ky массивов, т.е. если W = [W 1 :... : W Lx Ly ]T, то W 1+u+vLx = vec(Fu,vx,Ky ) ) для 0 u Lx, 0 v Ly.

(K (1.7.3) Матрица W имеет следующую структуру:

H1 H2... HKy H 0 H H 2 H 3... H Ky 1....

H3....

W = W(Lx,Ly ) (F) = H2, (1.7.4).

......

...

...... HLy 1 HLy...... HNy где f0,n f1,n... fKx 1,n f1,n f2,n... fKx,n (1.7.5) Hn =.

...

...

...

...

fLx 1,n fLx,n... fNx 1,n Таким образом, она является блочно-ганкелевой с ганкелевыми блоками размера Lx Kx (двухуровневой ганкелевой матрицей [11]), где каждый блок (N,1) Hn является одномерной траекторной матрицей ряда (F0,nx )T, (N,1) Hn = X(Lx ) (F0,nx )T, полученного из функции fm,n при фиксированном n, где T (N,1) (1.7.6) F0,nx = f0,n, f1,n,..., fNx 1,n, обозначает (n + 1)-й столбец матрицы F. Будем называть матрицу W блочно ганкелевой траекторной матрицей. Очевидно, что существует взаимноодно значное соответствие между матрицами вида (1.7.4) и двумерными массивами Nx Ny.

Сингулярное разложение Далее, как и в одномерном АСС производится сингулярное разложение (SVD) блочно-ганкелевой траекторной матрицы d j Uj V j, где W= j= собственные числа, Uj и Vj собственные и факторные вектора соответ j ственно, а (j, Uj, Vj ) собственные тройки.

Собственные векторы Uj и факторные векторы Vj образуют ортонормиро ванные базисы пространств векторизаций Ws (Lx, Ly )-подматриц и векториза ций W t (Kx, Ky )-подматриц соответственно. Поэтому разумно преобразовать их в массивы j = matrLx,Ly (Uj ) MLx,Ly, j = matrKx,Ky (Vj ) MKx,Ky, Массивы j и j будем называть собственными и факторными массивами соответственно.

Заметим, что сингулярное разложение с помощью перегруппировки ин дексов может быть также переписано в виде биортогонального разложения Kx Ky блочной матрицы с Lx Ly блоками в сумму кронекеровских произ ведений (см. раздел 1.1) F0,0 F0,1... F0,Ky 1 d......

... = j j j,... j= FKx 1,0 FKx 1,1... FKx 1,Ky называемого также KP-SVD (Kronecker-product SVD) [90]), см. подробнее в [70].

Этап восстановления Группировка Шаг группировки в двумерном варианте АСС выглядит ровно так же, как и в одномерном случае. Группировка по m наборам индексов (1.7.7) J1 J2 · · · Jm = {1,..., d}, Jk Jl = для k = l, производится суммированием элементарных компонент SVD:

m j Uj Vj где WJ = (1.7.8) W= WJk, jJ k= Ортогональное проецирование Сгруппированным матрицам WJk сопоставляются Lx Ly Kx Ky двухуров невые ганкелевы матрицы WJk с помощью ортогонального проецирования на пространство двухуровневых ганкелевых матриц. Ортогональная проекция матрицы Z1,1 Z1,2... Z1,Ky Z2,1 Z2,2... Z2,Ky Zk,l MLx,Kx, Z=,...

...

...

...

ZLy,1 ZLy,2... ZLy,Ky на пространство Lx Ly Kx Ky двухуровневых ганкелевых матриц может быть выражена с помощью двухуровневой ганкелизации def Z = H MLx,Kx (1Ly Ky H C )Z = H C Z1,1 H C Z1,2... H C Z1,Ky H C Z2,1 H C Z2,2... H C Z2,Ky def = H MLx,Kx,...

...

...

...

H C ZLy,1 H C ZLy,2... H C ZLy,Ky т.е. ганкелизация сначала применяется к блокам (внутриблочная ганкелиза ция) и затем ко всей матрице целиком, т.е. блоки на одних и тех же антидиа гоналях усредняются между собой (межблочная ганкелизация). Два уровня ганкелизации могут производиться и в обратном порядке. Пусть FJk мас сив, (Lx, Ly )-траекторной матрицей которого является WJk, называемый вос становленным по набору индексов Jk массивом. Элементы восстановленного массива можно найти и следующим образом:

(WJ )jl /#Dmn, где (FJ )mn = (j,l)Dmn Dmn = {(j, l) : m = (j 1) mod Lx + (l 1) mod Kx, n = (j 1)/Lx + (l 1)/Kx }.

Отметим, что (1.7.9) #Dmn = min(m, Nx m + 1, Lx, Kx ) min(n, Ny n + 1, Ly, Ky ).

Результатом алгоритма является разложение m (1.7.10) F= FJ k, k= 1.7.2. Частные случаи двумерного метода АСС Рассмотрим экстремальные размеры окна:

(a) Lx = 1 или Lx = Nx (b) Ly = 1 или Lx = Ny.

1. Если оба условия (a) и (b) выполняются, то так как 1 Lx Ly Nx Ny мы получаем (Lx, Ly ) = (Nx, 1) или (Lx, Ly ) = (1, Ny ). В этом случае блочно ганкелева траекторная матрица W совпадает с двумерным массивом F или его транспонированием. Таким образом, алгоритм АСС совпадает с группировкой компонент SVD исходного двумерного массива F:

L j Uj VjT, (1.7.11) F= j= Такой подход к обработке двумерных массивов [50, 80] используется в некоторых алгоритмах обработки изображений и он хорошо работает для массивов, которые можно приблизить небольшим количеством сумм r (j) (j) одномерных рядов (fm,n = pm qn ).

j= 2. Рассмотрим случай, когда выполняется либо (a), либо (b). Пусть выпол няется (b). Тогда без потери общности мы можем предположить, что Ly = 1 и 1 Lx Nx ;

в этом случае блочно-ганкелева траекторная матрица W, порожденная F, составлена из ганкелевых матриц столбцов (1.7.6) массива:

(1.7.12) W = [H0 : H1 :... : HNy 1 ], где блоки Hn определены в (1.7.5). Таким образом, мы получаем алго ритм многомерного метода АСС (MSSA, см. [13, 115]). В этом случае мы работаем с двумерным массивом как с набором рядов, которые распола (N,1) гаются в столбцах массива (F0,nx ) (см. (1.7.6)), и применяем алгоритм MSSA с параметром Lx к этому набору рядов. Если же еще и Ny = 1, т.е. исходный массив был одномерным рядом, то мы получаем алгоритм одномерного АСС.

Если выполняется (a) и мы рассматриваем массив как многомерный ряд по y, то траекторная матрица строится следующим образом:

(Nx,1) T (Nx,1) T (Nx,1) T (Nx,1) T (F ) (F0,1 ) (F0,2 )... (F0,Ky 1 ) 0,0 (F(Nx,1) )T (F(Nx,1) )T (F(Nx,1) )T... (F(Nx,1) )T 0,1 0,2 0,3 0,Ky (N,1)....

W = (F0,2x )T (F0,3x,1) )T..... (1.7.13) (N.

....

.

..........

(N,1) (N,1) (N,1) (F0,Lxy 1 )T (F0,Lxy )T... (F0,Ny 1 )T x...

Заметим, что матрицу (1.7.13) перегруппировкой столбцов можно пред ставить в виде W = [G0 : G1 :... : GNx 1 ], (1,N ) где Gk Ly -траекторная матрица (m + 1)-й строки массива Fm,0 y.

1.7.3. Метод АСС в анализе текстур: собственные фильтры Объектом исследования текстурного анализа являются текстурные изоб ражения, которые можно определить как однородные изображения составлен ные из большого числа похожих элементов (подробнее см. [73]). Чаще всего под текстурами подразумевают изображения однородных поверхностей природ ных или искусственных материалов. Примеры текстур изображены на рис. 1.5.

Синусоида Периодичная Возмущенная Черепица Ткань Дерево Галька Трава Гранит Мрамор Рис. 1.5. Примеры текстур Основной задачей в текстурном анализе является задача классификации, т.е. определения принадлежности различных текстур F(1),..., F(M ) к неболь шому набору классов. Обычно задача классификации решается с помощью уменьшения размерности, т.е. каждой рассматриваемой текстуре F(j) некото рым образом сопоставляется вектор V (j) в пространстве Rq небольшой размер ности, и задача классификации сводится к задаче кластеризации множества точек в Rq. Вектор V (j) будем называть классифицирующим вектором.

Далее нам потребуется следующая операция.

Определение 1.7.1. Пусть изображение F имеет размеры Nx Ny, и массив H имеет размер Lx Ly. Сверткой Y = F H будем называть Kx Ky массив, Lx 1,Ly определенный как yk,l = fks+(Lx 1),lt+(Ly 1) hs,t s=0,t= Применение АСС-разложения в текстурном анализе относится к методу так называемых собственных фильтров (eigenlters), как одного из методов в рамках фильтрационного подхода в текстурном анализе. Фильтрационный подход, впервые предложенный в работе [88], кратко можно описать следую щим образом:

1. Фиксируется некоторый набор фильтров H1,..., Hr.

2. Каждому изображению F сопоставляется набор откликов Yj = F Hj.

3. Набор откликов представляется в виде многомерной выборки Y = (vec(Y1 )... vec(Yr )), где каждый индивид это точка (позиция) в массиве откликов, а признаками являются значения каждого отклика для данной точки.

4. Классифицирующим вектором является некоторая статистика от выбор ки Y.

В оригинальном методе [88] рассматриваются 9 фильтров 3 3 следующе го вида: всевозможные произведения векторов (1, 2, 1)T, (1, 0, 1)T, (1, 2, 1)T на вектор-строки (1, 2, 1), (1, 0, 1), (1, 2, 1). В работе [107] можно найти сравнение различных наборов фильтров.

В качестве классифицирующего вектора обычно выбирается вектор раз мерности r, составленный из сумм квадратов откликов. Однако в этом случае возникает проблема поиска подходящего метода кластеризации. В более совре менных работах предлагается использовать гистограммы многомерной выбор ки [124], сравнивая их с помощью расстояния хи-квадрат. Так как фильтрация представляет собой некоторую замену базиса в пространстве признаков, то с точки зрения гистограмм это преобразование не имеет значения, что было экспериментально подтверждено [123], и вместо выборки откликов можно рас сматривать выборку скользящих окон. Заметим, что в случае использования гистограммного подхода, несмотря на простой классификатор, для построения гистограмм (необходимо дискретизовать пространство признаков) применяет ся кластеризация, которая является довольно трудоемкой.

Теперь перейдем к рассмотрению собственных фильтров. В работе [39] было предложено в качестве фильтров Hj использовать собственные массивы (k) j базовых изображений, где для массива A = (am,n )M 1,N 1 перевернутый m,n= массив A = (bm,n )M 1,N 1, bm,n = aM m+1,N n+1. Рассмотрим в качестве при m,n= мера пару изображений F(1), F(2), и пусть j собственные массивы F(1).

Тогда отклики разных массивов будут иметь вид (1) • Yj = F(1) j = j j факторный массив, сумма квадратов элементов которого равна квадрату сингулярного числа j.

(2) (2) величины проекций скользящих окон Fk,l на пространство, по • Yj рожденное массивом j.

В первых работах по собственным фильтрам размеры окна Lx Ly выби рались минимальными 3 3, однако в последних работах используются окна больших размеров [98, 99].

Собственные фильтры применяются в различных задачах обнаружения дефектов: обнаружение дефектов в ткани [121], обнаружение дефектов кера мической плитки [99], контроль качества продуктов [105].

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

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

выделяются инва риантные относительно длины окна характеристики ряда, такие как ранг, характеристические векторы, и т.д. Мы будем придерживаемся обозначений, принятых в теории метода АСС [66].

Для ряда FN = (f0,..., fN 1 ) длины N со значениями в поле K будем рассматривать ганкелевы матрицы X(L) (FN ) (определенные в (1.2.3)), порож денные рядом, для различных L, 1 L N.

2.1.1. Поведение ранга в зависимости от L Покажем, как зависит от L ранг ганкелевых матриц X(L), порожденных фиксированным рядом FN. Удобнее работать с дефектом L матрицы X(L), def т.е. L = L (FN ) = dim R(L) (FN ) = L rankL (FN ), где def R(L) = R(L) (FN ) = {X KL : X T X(L) = 01(NL+1) } (2.1.1) обозначает левое ядро матрицы.

Замечание 2.1.1.

(L) L, K = C, R(L) = L(L), K = R, где обозначает комплексное сопряжение подпространства CL, а ортогональное дополнение подпространства. Различия вещественного и ком плексного случая вызваны различными определениями скалярного произведе def def = X T Y и X, Y = (X)T Y соответственно.

ния: X, Y R C В основе алгебраической теории лежит следующее свойство левого ядра.

Лемма 2.1.1. Пусть 1 L N 1. Вектор A = (a0, a1,..., aL1 )T KL принадлежит R(L) тогда и только тогда, когда векторы (a0, a1,..., aL1, 0)T и (0, a0, a1,..., aL1 )T принадлежат R(L+1).

Доказательство.

Легко видеть, что AT X(L) = (a0, a1,..., aL1, 0) X(L+1), (2.1.2) AT X(L) = (0, a0, a1,..., aL1 ) X(L+1), где числа, K можно найти, приравняв правые части в (2.1.2).

Из леммы 2.1.1 можно вывести свойства дефекта L и, следовательно, ранга.

Предложение 2.1.1 ([74, Prop. 5.4, Cor. 5.1]) Существует (единственное) целое число d, 0 d (N + 1)/2, такое что если d = 0, то L = L для любого L ;

если же d 0, то 0, 1 L d, L = L1 + 1, d L N d + 1, L1 + 2, N d + 1 L N.

При этом для любого d ранг матрицы X(L) имеет следующий вид (см. рис. 1.1) L, 1 L d, (2.1.3) rankL (FN ) = d, d L N d + 1, N L + 1, N d + 1 L N.

Определение 2.1.1. Рангом временного ряда F называется def rank(FN ) = d, где d определено в предложении 2.1.1.

Замечание 2.1.2. Заметим, что d = max1LN rankL (FN ). Таким образом, определение 2.1.1 соответствует определению 1.3.2. Действительно, rank X(L) = d для допустимых L, т.е. когда d min(L, K). Для остальных L, т.е. L d или L N d + 1, матрица X(L) имеет полный ранг, меньший d.

Существует четыре типа поведения ранга:

(a) d = 0, (b) d N/2, (c) d = N/2, (d) d = (N + 1)/2.

Случай (a) соответствует нулевому ряду (FN = (0,..., 0)T ). В случае (b) су ществует по крайней мере одно L1 (например, L1 = (N + 1)/2), такое что X(L1 ) неполного ранга, в то время как в случаях (c) и (d) матрица X(L) имеет полный ранг для всех L. Отметим, что случаи (c) и (d) соответствуют четной и нечетной длине ряда соответственно;

также случаи (b) и (c) выглядят различа ющимися, но, как мы покажем далее, структура их одинакова. В дальнейшем будем говорить, что ряд имеет полный ранг, если d = (N + 1)/2 (случай (d)).

2.1.2. Структура левого ядра при d L N d + На основе леммы 2.1.1 базис левого ядра для разных L можно получить итеративно, из одного или нескольких векторов, с помощью сдвигов. Введем оператор сдвига вектора следующим образом: для V = (v0,..., vs1 )T Ks и чисел r Z, n N обозначим def Ir V = (vr,..., vnr1 )T Kn, ns где полагаем vj = 0 для j s и j 0.

Если r 0 и r + s n, то Ir V = (0,..., 0, v1,..., vs, 0,..., 0)T.

ns r n(r+s) Будем также использовать обозначение Ir = Ir, так как размерность вектора n ns обычно известна из контекста. Тогда лемму 2.1.1 можно кратко записать в виде V R(L) I0 V, I1 V R(L+1), L+1 L+ а также обобщить ее по индукции.

временной ряд и выбрано s, 1 s N. Для Лемма 2.1.2. Пусть FN любого L, s L N, вектор V Ks принадлежит R(s) тогда и только Ls тогда, когда I0 V, I1 V,..., IL V R(L).

L L Для вектора V Ks и n s, назовем набор векторов I0 V,..., Ins V Kn n n сдвиговой цепочкой (shift-chain) длины n s + 1. Очевидно, что если V = 0, то любая его сдвиговая цепочка состоит из линейно независимых векторов.

По предложению 2.1.1, dim R(d+1) = 1, откуда можно вывести следующее утверждение.

Предложение 2.1.2 ([74, Th. 5.1, 1.]) Пусть FN временной ряд и 0 rank FN = d N/2, 1. Существует вектор P Kd+1, такой что для любого L, d L min{N d + 1, N }, базисом R(L) является сдвиговая цепочка {I0 P, I1 P,..., IL Ld (2.1.4) P }.

L L 2. Вектор P определен однозначно с точностью до умножения на кон станту. Такой вектор называется (первым) характеристическим век тором ряда FN.

Иногда удобнее работать с матричной формой предложения 2.1.2. Пусть P = (p0,..., pd )T первый характеристический вектор. Для L d + 1 (L может превосходить N ) определим матрицу p0 0..... p0.....

..

.........

.

... p KL(Ld).

.

(L) (2.1.5) P = pd. 0 p.....

.

d........

..

..

0... 0 pd временной ряд, 0 rank FN = d N/2, и Следствие 2.1.1. Пусть FN P Kd+1 его первый характеристический вектор. Тогда для L, d L min{N d + 1, N }, левое ядро совпадает с образом матрицы P(L). Иными словами, V R(L) тогда и только тогда, когда существует вектор H KLd, такой что V = P(L) H. (2.1.6) Замечание 2.1.3. В условиях следствия 2.1.1, если к тому же pd = 0, то вектор V принадлежит пространству R(L) (FN ) тогда и только тогда, когда его производящий многочлен V (z) делится на P (z), так как равенство (2.1.6) равносильно равенству V (z) = P (z)H(z) при pd = 0.

2.1.3. Cтруктура левого ядра, L N d + Предложение 2.1.3 ([74, Th. 5.1, 2.]) Пусть FN временной ряд и 1 rank FN = d (N + 1)/2.

1. Существует пара векторов P Kd+1, Q KN d+2, таких что для любого L, N d + 1 L N, базисом R(L) является объединение сдвиговых цепочек {I0 P..., IL P } {I0 Q, I1 Q,... IL-N +d-2 Q}.

L-d- (2.1.7) L L L L 2. Если d N/2, то P является первым характеристическим вектором (см. предложение 2.1.2), а вектор Q определен единственным образом в следующем смысле: другой вектор Q удовлетворяет пункту 1 данного предложения тогда и только тогда, когда существуют K \ {0} и H KN 2d+2, такие что Q Q = P(N d+2) H.



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.