автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Анализ сингулярного спектра в задачах обработки временных и пространственных данных

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

\ I

> 1

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

4ВОО/О!

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

АНАЛИЗ СИНГУЛЯРНОГО СПЕКТРА В ЗАДАЧАХ ОБРАБОТКИ ВРЕМЕННЫХ И ПРОСТРАНСТВЕННЫХ ДАННЫХ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

0 3 013 щ

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

4853787

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

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

доцент Голяндина Нина Эдуардовна

Официальные оппоненты: доктор физико-математических наук,

профессор Егоров Владимир Алексеевич (Санкт-Петербургский государственный электротехнический университет "ЛЭТИ")

кандидат физико-математических наук, старший научный сотрудник Васильев Николай Николаевич (Учреждение Российской академии наук Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН)

Ведущая организация: Учреждение Российской академии наук Санкт-

Петербургский институт информатики и автоматизации РАН

Защита состоится "Л." 2011г. в ^ часов на заседа-

нии диссертационного совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д. 28, математико-механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке имени М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9. Автореферат разослан ",,УУ" 20Иг.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы Основные результаты обсуждались на семинарах кафедры статистического моделирования математико-механического факультета СПбГУ, семинаре кафедры статистики в School of Mathematics, Cardiff University (Великобритания, февраль 2008, 2009) и докладывались на международных конференциях: «2nd International Conference on Matrix Methods

and Operator Equations» (Москва, 23-27 июля 2007 г.), «Идентификация систем и задачи управления» SICPR.0'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 годы, грантами CR.DF №№ R.UB1-1643-ST-06 и RUB1-33015-ST-09 и грантами Правительства Санкт-Петербурга №№ 2.1/30-04/27, 2.1/29-04/021, 2.1/07-06/056.

Публикации. Материалы диссертации опубликованы в работах [Al, А2, A3, А4, А5, А6, А7, А8]. Из них работы [А 1, А2] — в списке журналов, рекомендованных ВАК.

Работы [A3, А4, А5, А6, А7, А8] выполнены в соавторстве. Соискателю в работах [А4, А6, А7, А8] принадлежат доказательства утверждений, в работах [A3, А4, А5, А8] — численные эксперименты и реализация алгоритмов. И.В. Флоринскому в работах [A3, А5] принадлежат постановки задач. В работе [А7] А.О. Алексееву и Н.П. Алексеевой принадлежат постановки задач и способ вычисления вероятности классификации, Е.М. Подхалюзиной и П.В. Грачевой — реализация алгоритмов и обработка данных. Научному руководителю Н.Э. Голяндиной в работах [A3, А4, А5, А6, А8] принадлежат постановки задач, методология применения метода АСС.

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

Содержание работы

Основными объектами исследования являются временные ряды = (Л, • • • , /«-О е С1*" и двумерные массивы Р = (/т,п)т'п=!^"^ 1т,п е С. Рассмотрим базовый метод АСС для временных рядов. Пусть ряд являет-

ся суммой компонент различной структуры = Рд^ + ... + На шаге вложения по ряду ^ и длине окна Ь составляется Ь-траекторная матрица ряда, столбцами которой являются скользящие отрезки ряда длины Ь:

7(г)

Х = X

(fa fi

fx /2 /2 /з

• •• /к-Л ... Iк

(1)

V h-i h Л+1 • • • In- 1 J

Траекторная матрица имеет одинаковые значения на антидиагопалях, т.е. является ганкелевой матрицей. Затем производится сингулярное разложение (SVD) траекторной матрицы

d

X = (2)

j=i

где и\ > ... > ad > 0 — сингулярные числа, a {i/j}j=1 и {Vj}!-=1 — левые и правые сингулярные векторы, называемые также собственными и факторными векторами. Набор (crj,Uj,Vj) называется j-u собственной тройкой. Собственные векторы образуют базис пространства столбцов матрицы X, ¿Я (F*) = span(X), называемого траекторным пространством.

С помощью задания группировки, т.е. разбиения набора собственных троек на г групп {1,..., d} = J\ U ... U Jr, определяется разложение

г

X = £хл>

k=l

где Xj = J2 v/Âj^jV*. Посредством диагонального усреднения матрицы jsJ

X.jk преобразуются в восстановленные ряды F^ , что приводит к разложению

F» = ±F{Nk)-

ь= 1

В теории метода АСС основным является вопрос о нахождении условий разделимости компонент в исходной сумме FV = F$ + .. т.е. возможности с помощью АСС найти восстановленные ряды хорошо аппроксимирующие Fffl, или базисы {Uj}jejk подпространств, аппроксимирующих траек-торные пространства Кроме того, важна идентифицируемость компонент, т.е. возможность различить соответствующие собственные тройки после шага разложения в методе АСС, для чего, в частности, количество собственных троек, соответствующих компоненте, должно быть небольшим и одинаковым для различных размеров окна. Идеальной моделью таких рядов являются ряды, траекторные матрицы которых имеют малый, не зависящий от размеров окна ранг, так называемые ряды конечного ранга.

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

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

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

Второй раздел посвящен краткому обзору модели рядов конечного ранга. Ряд Fjv € С1хДГ называется рядом конечного ранга d, если ранг равен некоторому числу d < Лг/2 для любых L, d<L<N — d-f 1, Определяется класс рядов, удовлетворяющих линейным рекуррентным формулам (ЛРФ), т.е. рядов, для которых существуют во,..., a^i € С, такие что

fn+p

У^ ükfn+k (з)

fc=0

для 0 < п < N — р — 1. В разделе также приводятся известные в теории АСС результаты о соотношениях между рядами, удовлетворяющими ЛРФ, и рядами конечного ранга [1, 6].

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

к тому же C{K\F^) _L ÖK)(F^]), где

К = N-L + 1, то ряды называются слабо L-разделимыми. Ряды слабо L-разделимы тогда и только тогда, когда сумма сингулярных разложений траекторных матриц отдельных рядов

X = X, + Х2 = <)* + i>^2)(vf Г

j=i j=i

является сингулярным разложением матрицы X. В разделе также приводятся основные сведения о точной и приближенной разделимости [6].

В четвертом разделе содержится обзор теории бесконечных рядов, удовлетворяющих ЛРФ. Ряд F(X= (/о, ...,/„,...), /„ е К., где К. — поле, удовлетворяет ЛРФ (3), если равенство (3), при ао,..., ap_i £ 1С, выполняется для всех n е Ко = N U {0}. Каждой ЛРФ (3) сопоставляется характеристиче-

Р-1

ский многочлен A{z) = zp — akz ■ Существует минимальный многочлен

к=о

P(z) — PdZd + ... +P1Z + P0, такой что характеристический многочлен любой ЛРФ, которой удовлетворяет F,делится на P(z). Известно, что в случае комплексного поля, К, — С, такие ряды имеют единственное представление

ГП Со-1

= + . (4)

fc=l j=О

где Qk — ненулевые многочлены степени Vk — 1, cj — комплексные константы, си„-\ ф 0, <5j(n) — символ Кронекера, т.е. Sj(n) = 1 если п = j и öj(n) = 0

иначе. При этом Л^ являются корнями Р{г) с кратностями 14, щ — кратность корня 0и1/о + ... + сга = <1. Для вещественнозначпыхрядов представление (4) соответствует сумме произведений полиномов, экспонент и косинусов. Если ао ф 0 или, что то же самое, ио = 0, ряд ^ называется реверсивным рядом размерности ¿. Конечный отрезок ^ такого ряда ^ называется реверсивным рядом размерности если N > 2й.

В пятом разделе рассматриваются методы прогнозирования компонент разложения в методе АСС. Пусть ^ = + компонента Fдr1) является реверсивным рядом размерности (1 и имеет представление (4), а также <1 < Ь < N — ¿+1. Тогда по подпространству Л = 8рап{£/)п ..., С С1, соответствующему компоненте ^' в разложении, если еь == (0,..., 0,1)т ^ Л, коэффициенты ао, ■ • • ,аь-2 ЛРФ прогноза определяются с помощью проекции еь на сопряжение ортогонального дополнения И = Ах подпространства:

(60,...А-1)Т = Пце£, (ао, • •., а£_2)т = (60, • • •, Ьь-2)Т/{-ЬЬ-1).

В случае точной разделимости, когда = А, корнями характери-

стического многочлена А(г) ЛРФ прогноза являются с1 корней минимального многочлена Р{г) и Ь — <1 — 1 побочных корней. В случае приближенной разделимости корни А(г) являются приближениями корней минимального многочлена и побочных корней, что позволяет использовать ЛРФ прогноза для оценки параметров ряда .

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

^(0) = Р(У е эрап(Х) или V + и е зрап(Х)), где 11 ={ (1,..., 1)т. Эту вероятность можно выразить как

^п(0) = 2Р(К е Брап(Х)) - Р(1ь е эрап(Х) и V е зрап(Х)), и для нахождения каждого из слагаемых достаточно найти величины

= #{Х б Я1хК : ганкХ = г}, Г^*'1 = #{Х £ ЪЬхК : ганкХ = г,1ь € зрап(Х)},

где — множество ганкелевых матриц размера Ь х К.

В седьмом разделе описывается двумерный вариант метода АСС [2]. Для двумерного массива данных (матрицы) Г = (/п,т)п*т1о'У~1 Ьу)-траектор-ная матрица W = формируется по двумерному скользящему окну

размера Ьх х Ьу. Столбцы W (векторы вложения) являются векторизациями

подматриц '= (¡п+к,т+1)^т=о'"""1! где 1 < к + 1 < Кх = Мх — Ьх + 1,

1 <1+1 < Ку = Ыу - Ьу + 1, при этом (У^)п+ьхт+1,к+Кх1+1 = 1п+к,т+1-Матрица ЛУ является блочно-ганкелевой с ганкелевыми блоками [8].

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

Во второй главе излагается необходимая алгебраическая теория. В первом разделе излагаются необходимые факты из алгебраической теории ганкелевых матриц [7]. Для фиксированного ряда ^ € К.** изучается зависимость от Ь структуры ганкелевой матрицы т.е. ранга матрицы и структуры ее левого ядра

иЮ = ¡Н^(Г^) = {ХеК.1-. ХтХ(х) = (0,..., 0)}.

Показано, что либо ряд имеет конечный ранг, либо матрица имеет полный ранг для любого Ь. Пусть ранг ряда равен <1. Тогда сИтЭТ^ = 0 для Ь < с?, а для (1<Ь<Ы — й-1-1 базисом являются столбцы матрицы

/ро ... Р<1 0 О \ Т

0 ••• О е/С^Л (5)

\0 0 ро ... Р4/

т.е. сдвиги характеристического вектора Р = (ро,... ,Р(/.)Т, определенного однозначно с точностью до умножения на константу. Для Ь> базис

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

ряда: Р^+1(а) = (/о,..., /лг-ь а).

Во втором разделе содержится обзор теории /с-последовательностей [4] для случая к = 2 (называемых в диссертации двумерными массивами), связанных линейными рекуррентными соотношениями. Бесконечная матрица Р = (/п,т)пт=о называется двумерным бесконечным массивом. Линейные рекуррентные соотношения между элементами Р

+О0

а(р,т)1п+р,т+т - О для любых 71, ГП & М0) (6)

р,т=О

где множество {(/5, г) : а(р,т) Ф 0} конечно, ассоциируются с многочленами

+00

р(х<у) — X! а(р,т)хРУт- Множество многочленов Х(^), для которых выпол-

р, т=0

няется (6), называется аннулятором Т и является идеалом [3] в кольце многочленов С[х, у] от двух переменных.

Известно, что линейное пространство £(/"), образованное сдвигами = (/п+А,т+/)п,т=0' конечномерно тогда и только тогда, когда идеал Х^Т) нульмерен, т.е. многообразие [3] (множество корней) идеала Х(конечно:

- {(Аь /л).....(Аг>^)}.

В этом случае массив X2 имеет единственное биномиальное представление

= Е £ («) (я) (7)

гДе (аМ™) — биномиальные коэффициенты и количество ненулевых коэффициентов б^д конечно.

В теории ¿-линейных последовательностей [4] ставится вопрос об оценке линейной сложности массива

по его биномиальному представлению [4]. Основным способом оценки линейной сложности является следующий способ. Определим носитель массива В как как Эиррб = ;{(а,/3) 6 : Ъа$ Ф 0}. Множество индексов 21 С называется диаграммой Ферре, если ((—1,0) + 21) П N¡3 С 21 и ((0, -1) + 21) П N¡1 С 21, где операция сдвига множества индексов определяется как (а, 0) +21 == {(а + к,/3 + 1), (к, I) е 21}.

Предложение [4, Предл. 23]. Если массив Т имеет представление с одним корнем (А,//)

= Е Ь(а) (Ц) (8)

В = (¿а,/г)а^= о — массив коэффициентов и 3 — наименьшая диаграмма Ферре, содержащая Яирр В, то г(^) <

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

В первом разделе на основе алгебраической теории ганкелевых матриц производится систематизация типов рядов с точки зрения АСС: конечного ранга, неполного ранга, реверсивных. Естественным образом определяется

класс продолжимых рядов. Устанавливаются точные связи между типами, в том числе уточняются результаты из [1] и [6].

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

Теорема 3.2.1. Пусть ^ ф 0 и {ии..., иг} - базис /Я^4), а является реверсивным рядом размерности в, < N/2, и с1 < тт(£ — 1, К).

Ряды Р^ и РрР ¿-полуразделимы тогда и только тогда, когда минимальный многочлен Р№(г) ряда является общим делителем производящих многочленов Щг) = . где II 1 = и<?\ ..., и£1,)т.

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

Теорема 3.2.3. Реверсивные ряды и Р^1 размерностей с1\, с/г < N/2 ¿-полуразделимы тогда и только тогда, когда существуют € С \ {0}, р > 0, ш 6 [0; 1 /Ь) и различные тпь Ы е Мо, 0 < т,к, Ы < Ь, такие что

1п] = Е ак (р ехр (2тгг + ш)) )", = £ Ь, (р"1 ехр (2ттг + ш)) )".

Осуществляется полная классификация случаев полуразделимости при Ь < К. Представлен критерий и все случаи двусторонней разделимости.

В третьем разделе изучается поведение побочных корней ЛРФ прогноза. Пусть А(г) = Р(г)Нп(г) — характеристический многочлен ЛРФ прогноза для длины окна Ь. Тогда вектор Нп, соответствующий п = Ь—<1— 1 побочным корням ЛРФ, является решением уравнения

(Р(£))*Р(«ЯП = е„+1,

и многочлены Нп{г) образуют систему ортогональных многочленов на единичной комплексной окружности с весом |Р(г)|2. На языке ортогональных многочленов систематизируются известные результаты для побочных корней ЛРФ прогноза. Для описания асимптотического распределения корней используются современные результаты теории ортогональных многочленов.

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

гь*к, 1

используется алгебраическая теория ганкелевых матриц. Теорема 3.4.1.

г < тт(Ь, К),

г1хК, 1 = г1х(К+1)д

Г^хК, г > тт{I, К) или г = Ь < К.

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

В первом разделе приводятся базовые свойства ранга (Lx, ¿,;)-траекторпой матрицы W^1'^ массива F. В дальнейшем в качестве массивов рассматриваются Nx х Ny лодмассивы бесконечных массивов. Для бесконечного массива вводится понятие (Lx, ¿,,)-траекторного пространства как пространства, порожденного всеми ЬхкЬу окнами массиваF\ (F) = span{Fm,n'i'^}m~=n-Показано, что r(.F) < +00 тогда и только тогда, когда размерность тра-екторного пространства равномерно ограничена. При этом dim C^'^iF) = r(7") для достаточно больших размеров окна Lx > Lxо, Ly > Lvq. Поэтому далее массивы с r(.F) < +00 называются массивами конечного ранга. Выделяется также класс массивов неполного ранга, для которых dim£'il,il''(Jr) < LxLy. Показано, что этот класс не совпадает с классом массивов конечного ранга, в отличие от случая аналогичных классов временных рядов.

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

Теорема 4.1.2. Пусть массив F имеет представление (8) и т = max {а + ¡3 : (ct,j3) е SuppB}. Тогда r(F) < (|_f J + l) (|_f J + S), где <5 = 1(2) для четного (нечетного т).

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

ЩГ) = {(Lx, Ly) е N2: dim = x{F)}.

Доказана теорема, позволяющая найти почти все элементы 9Ji(.F). Обозначим Вх(21) = гаах{а + 1 : (а, /3) € 21} и Ву{21) = max{/? + 1 : (а, /3) G 21}.

Теорема 3.2.3. Пусть <5Х и <5У есть диаграммы Ферре под старшими членами базисов Гребиера для лексикографических упорядочений у > х и х > у. Тогда

(В*(<5Х), В„(0г)), (Вя(0„), В„(0„)) е Щ?),

и для любого (Lx, Ly) € ffl выполняются неравенства

Ly > В„(0Я), Lx > Ba(0ff).

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

Также показано, что ранг траекторной матрицы конечного подмас-

сива F равен линейной сложности массива r(Jr) тогда и только тогда, когда (Lx, Ly) е m{F) и (Кх, Ку) е ОЯ(^).

В третьем разделе изучается разделимость двумерных массивов. Массивы FÍ1) и F® (Lx,Ly) -полуразделимы, если ¿^'^(F^) _L Если к

тому же ^^'^(F'1)) ± то массивы (Lx, ¿^-разделимы.

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

Теорема 4.3.3. Для (Lx,Ly) е ЗЯ(7'(1))ПЯЯ(Я2)) массивы ftth = Pi(m, n)\f $ и /m,n = Píim, п)X'z/jíq (Lx,Ly)-полуразделимы только в следующих случаях:

1. Р\ = Р\(т) , Р2 = Р2(т), ряды ¡J," и ц2 /^-полуразделимы;

2. Р\ = Р\(п), Р2 = Piin), ряды А"1 и А™ Ьх-полуразделимы;

3. Pi = const, Р2 = Q2\{n) + Q22{m), ряды А"1 и Ai," ¿х-полуразделимы, ряды fi'l и ¡л2 ¿¡,-полуразделимы;

4. Рх = (цт+bin+ci, Р2 = а2т+Ь2п+С2, ряды А"1 и Х2 L^-полуразделимы, ряды /4' и (¿2 Ь^-полуразделимы и ai&2 + b{a2 = 0.

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

Теорема 4.4.3. Пусть / 6 tx] х [0; £у]) (имеет непрерывные частные

производные вплоть до порядка d), тх G (0, tx), ту е {0,ty) и функция д : T>i хТ>2 н-> R, где Vi = [0;тж] х [0; ту\ иТ>2= [0;^-^] х p,ty-Ty], определена как д((и, V), (s, í)) = f(u + s,v + t) и имеет конечное разложение Шмидта

d

f(u + s,v + t) = g{(u,v),(s,t)) = akVk{u,v)4>k(s,t).

k=i

Тогда существуют Aj, ¡ij е С, m < d и Pj(x,у) e С [ж, у], такие что

m

f(x,y) = Pj(x, y) exp(AjX + njy). i

Пятая глава посвящена практическим аспектам двумерного метода АСС. В первом разделе содержится исследование методами статистического моделирования качества восстановления зашумленного массива конечного ранга с иомощыо метода АСС. В качестве модели шума используется аддитив-

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

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

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

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

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

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

2. Главные компоненты временных рядов: метод «Гусеница», Под ред. Д. Л. Данилов, А. А. Жиглявский. СПб.: Пресском, 1997. С. 308.

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

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

5. Daykin D. Е. Distribution of bordered persymmetric matrices in a finite field // J. Reine und Angew. Math. (Crelles Journal). 1960. Vol. 203. Pp. 47-45.

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

7. Heinig G., Rost К. Algebraic methods for Toeplitz-like matrices and operators. Akademie Verlag, Berlin, 1984. P. 212.

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

Список публикаций автора

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

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

А2. Usevich К. On signal and extraneous roots in Singular Spectrum Analysis // Statistics and Its Interface. 2010. Vol. 3, no. 3. Pp. 281-295.

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

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

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

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

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

A7. Alexeyeva N., Alexeyev A., Gracheva P., Podkhalyuzina E., Usevich. K. Symptom and syndrome analysis of categorial series, logical principles and forms of logic // Proceedings of the 2010 3rd Intern. Conf. on BioMedical Engineering and Informatics. 2010. Vol. 6. Pp. 2603-2606.

A8. Golyandina N. E., Usevich K. D. 2D-extension of Singular Spectrum Analysis: algorithm and elements of theory // Matrix methods: theory, algorithms and applications / Ed. by V. Olshevsky, E. Tyrtyshnikov. World Scientific, 2010. Pp. 449-473.

Подписано в печать 27.12.2010 г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № ¡862.

Отпечатано в ООО «Издательство "JIEMA"» 199004, Россия, Санкт-Петербург, В.О., Средний пр., д. 24 тел.: 323-30-50, тел./факс: 323-67-74 e-mail: izd_lema@mail.ru http://www.lemaprint.ru

Введение

Список основных обозначений

Глава 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. Поведение ранга в зависимости от Ь.

2.1.2. Структура левого ядра при <1 < Ь < N — <¿+

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. Полуотделимость от рядов регулярной конечно-разностной размерности

3.2.3. Перечисление случаев левой отделимости для Ь < А

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, £у)-траекторное пространство бесконечного массива

4.1.4. Полиномиальное представление массивов и оценка линейной сложности.

4.1.5. Оценки линейной сложности по диаграмме Ферре биномиального представления

4.2. Оценки множества допустимых размеров окна.

4.2.1. Оценка множества для бесконечного массива.

4.2.2. Переход от бесконечного массива к конечному.

4.3. Двумерная разделимость.

4.3.1. Разделимость произведений р51дов.

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. Быстрые вычисления с помощью БПФ.180'

5.3.3. Структура и краткое описание комплекса программ

Основными объектами исследования в диссертационной работе являются временные ряды и двумерные массивы данных.

Под вещественнозначным (комплекснозначным) одномерным временным рядом длины 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(p\t)+f^(t) (0.1-) где f(T\t) — медленно меняющаяся составляющая, называемая трендом, которую часто описывают некоторой параметрической составляющей, например полиномами невысоких порядков или функциями с ограничениями на их гладкость [3, Гл. З]1, f(p\t) — периодическая составляющая, f^(t) — шумовая составляющая, которая обычно предполагается реализацией некоторого случайного процесса. Наиболее распространенными задачами являются: определение глобального поведения ряда (выделение тренда), обнаружение перио-дичностей или удаление их из ряда (seasonal adjustment), сглаживание (выделение низкочастотной составляющей), выделение детерминистической составляющей (отделение сигнала от шума).

Для различных частных случаев представления (0.1) разработаны мощные математические теории. Например задача f(t) — t) + f^(t) может решаться методами аппроксимации или регрессии (например, метод наименьших квадратов [31]); в случае f(t) = f^p\t) + /^(t), где шум предполагается стационарным, применимы методы спектрального анализа, основанные на теории стационарных случайных процессов и теории рядов Фурье [32, 117]. В общей постановке задачи, которая характерна для анализа реальных данных, при отсутствии априорной информации, применение параметрических методов наталкивается на ряд трудностей.

Анализ Сингулярного Спектра (.АСС'), как метод решения различных задач анализа временных рядов, независимо появился в 70х-90х годах в России и других странах [6, 51, 84]. Основой метода АСС является этап разложения, на котором построенная по временному ряду ганкелева матрица раеклады

1 существуют и другие подходы к определению тренда [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]. Этап разложения двумерного АСС, также известный под названием 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.

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

Заключение

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

• Было установлено, что в рамках алгебраической теории ганкелевых матриц становится возможным систематизировать и установить точные связи между типами рядов: конечного ранга, реверсивными, продолжимы-ми, и т.д. (предложения 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). Данный критерий может быть полезен для дальнейшего исследования разделимости в АСС, например, более сложного, практически и теоретически значимого случая асимптотической разделимости.

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

Было показано, что бесконечные массивы конечного ранга соответствуют массивам с конечной линейной сложностью (линейным рекуррентным массивам, см. предложение 4.1.1); был найден общий вид непрерывных функций, имеющих конечное АСС разложение в непрерывном варианте метода АСС (теорема 4.4.2).

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

Был исследован вопрос о нахождении области допустимых размеров окна для массивов конечного ранга. На общий случай массивов конечного ранга расширены оценки множества допустимых размеров окна с помощью методов базисов Грёбнера (теорема 4.2.1). Знание минимально допустимых размеров окна необходимо для выбора достаточных размеров окна в практических задачах.

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

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

• Были разработаны и реализованы в виде комплекса программ алгоритмы для двумерного разложения в методе АСС и для решения различных задач обработки данных (см. раздел 5.3).

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

1. Александров Ф. И. Выделение аддитивных компонент временного ряда при пакетной обработке методом "Гусеница"-88А // Вестник СПбГУ, Сер. 1. Математика. Механика. Астрономия. 2006. № 2. С. 71-74.

2. Алексеева Н. Комбинаторный анализ двух форм скрытой периодичности категориальных последовательностей // Вестник Санкт-Петербургского университета. Серия 1: Математика, механика, астрономия. 2007. № 3. С. 55-64.

3. Андерсон Т. Статистический анализ временных рядов. М.: Мир, 1976. С. 757.

4. Бардин М. Изменчивость температуры воздуха над западными территориями России и сопредельными странами в XX веке // Метеорология и гидрология. 2002. № 8. С. 5-23.

5. Белонин М. Д., Татаринов И. В., Калинин О. М. и др. Факторный анализ в нефтяной геологии. М.: ВИЭМС, 1971. С. 56.

6. Бриллинджер Д. Временные ряды. Обработка данных и теория. М.: Мир, 1980. С. 536.

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

8. Ван дер Варден Б. Л. Алгебра. М.: Наука, 1976. С. 623.

9. Владимиров В. С. Уравнения математической физики. М.: Наука, 1981. С. 512.

10. И. Воеводин В., Кузнецов Ю. Матрицы и вычисления. М.:Наука, 1984. С. 320.

11. Гантмахер Ф. Р. Теория матриц, 5-е изд. ФИЗМАТЛИТ, 2004. С. 576.

12. Главные компоненты временных рядов: метод «Гусеница», Под ред. Д. Л. Данилов, А. А. Жиглявский. СПб.: Пресском, 1997. С. 308.

13. Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра, Учебник. В 2-х т. Т. II. М.: Гелиос АРВ, 2003.

14. Голуб Д., Лоан Ч. В. Матричные вычисления. М.: Мир, 1999. С. 548.

15. Голяндина Н. Э. Метод «Гусеница»-88А: анализ временных рядов: Учеб. > пособие. СПб.: ВВМ, 2003. С. 85.

16. Голяндина Н. Э. Метод «Гусеница»-83А: прогноз временных рядов: Учеб. пособие. СПб.: ВВМ, 2004. С. 53.

17. Голяндина Н. Э., Осипов Е. В. Метод Тусеница'-ЭбА для анализа временных рядов с пропусками // Мат. модели. Теория и приложения. 2005. 6. С. 50-61.

18. Голяндина Н. Э., Усевич К. Д. Метод 20-38А для анализа двумерных полей // Труды VII Межд. конф «Идентификация систем и задачи управления» !31СР.Ю'08. Москва, 28-31 января 2008. 2008. С. 1657-1727.

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

20. Дюк В. Поиск сложных непериодических шаблонов в последовательностях числе и символов методами локальной геометрии // Тр. СПИИ РАН. 2002. Т. 2, № 1. С. 263-268.

21. Ефимов В. М., Галактионов Ю. К. О возможности прогнозирования циклических изменений численности млекопитающих // Журн. общ. биологии. 1983. Т. 44, № 3. С. 343-352.

22. Иохвидов И. С. Ганкелевы и теплицевы матрицы и формы. Наука, М., 1974. С. 263.

23. Кислицин М. М. Многомерная статистика временных рядов наблюдений в авиационной эргономике // Вопросы кибернетики.Биотехнические системы в авиационной эргономике. 1978. № 51. С. 117-126.

24. Кокс Д., Литтл Д., О'Ши Д. Идеалы, многообразия и алгоритмы. М.: Мир, 2000. С. 687.

25. Кузьмин А. С., Куракин В. Л., Нечаев А. А. Псевдослучайные и полилинейные последовательности // Труды по дискретной математике / Под ред. П. ред. В.Н. Сачкова и др. М.: ТВП, 1997. Т. 1. С. 139-202.

26. Куракин В. Л. Линейная сложность полилинейных последовательностей // Дискретная математика. 2001. Т. 13. С. 4-55.

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

28. Лидл Р., Нидеррайтер Г. Конечные поля: в 2-х т. Государственное издание физико-математической литературы, 1988. С. 820.

29. Линник Ю. Метод наименьших квадратов и основы теории обработки наблюдений. М.: Физматлит, 1958. С. 336.

30. Марпл-мл. С. Л. Цифровой спектральный анализ и его приложения. М.: МИР, 1990. С. 584.

31. Муттер В. М. Основы помехюустойчивой телепередачи информации. Л.: Энергоатомиздат, 1990. С. 288.

32. Некрутк'ин В. Аппроксимирующие пространства и продолжения временных рядов // Статистическ^исе модели с приложениями в эконометрике и смежных областях / Под род. П. ред. С.М.Ермакова и Ю.Н.Каштанова. СПб.: изд-во НИИХ СПбГУ, 1999. С. 2-32.

33. Некруткин В. В. Разложения временных рядов // Главные компоненты временных рядов: метод «Гусеница» / Под ред. А. А. Ж. Под ред. Д. Л. Данилова. СПб: Пресском, 1997. С. 194-227.

34. Прасолов В. В. Многочлены. М.: МЦНМО, 2001. С. 336.

35. Прэтт У. Цифровая обработка изображений, Под ред. пер. с англ. под ред. Д. С. Лебедева. MI. : Мир, 1982. С. 310.

36. Усевич К. Д. Разложение ф>;у~шкций в двумерном варианте метода «Гусени-4a»-SSA и связанные с ним: системы уравнений в частных производных // Вестник СПбГУ, Серия 10г Прикладная математика, информатика, процессы управления. 2009. К5а 3. С. 152-161.

37. Ade F. Characterization of Textures by 'Eigenfilters' // Signal Processing. 1983. Vol. 5. Pp. 451-457.

38. Alexeyeva N., Alexeyev A., Gracheva P. et al. Symptom and syndrome analysis of categorial series, logical principles and forms of logic // Proc. of the 2010 3rd Int. Conf. on BioMed. Engineering and Informatics . Vol. 6. 2010. Pp. 2603-2606.

39. Althaler J., Dur. A. Finite linear recurring sequences and homogeneous ideals // Applicable Algebra in Engineering, Communication and Computing. 1996. Vol. 7. Pp. 377-390.

40. Axmon J., Hansson M., Sornmo L. Partial forward-backward averaging for enhanced frequency estimation of real X-texture modes // IEEE Transactions on Signal Processing. 2005. Vol. 53, no. 7. Pp. 2550-2562.

41. Badeau R., David B., Richard G. High-Resolution Spectral Analysis of Mixtures of Complex Exponentials Modulated by Polynomials // IEEE Transactions on Signal Processing. 2006. Vol. 54, no. 4. Pp. 1341-1350.

42. Bezerra L. H., Bazan F. S. V. Eigenvalue Locations of Generalized Companion Predictor Matrices // SI AM Journal on Matrix Analysis and Applications. 1998. Vol. 19, no. 4. Pp. 886-897.

43. Biondi F., Isaacs C., Hughes M. et al. The Near-1600 Dry/wet Knock-out: Linking Terrestrial and Near-shore Ecosystems // Proc. 24th Annual Climate Diagnostics and Prediction Workshop, / US department of Commerce, Springfield, VA. 76-79.

44. Broomhead D. S., King G. P. Extracting qualitative dynamics from experimental data // Physica. 1986. Vol. 20. Pp. 217-236.

45. Buchstaber V. M. Time Series Analysis and Grassmanians // Applied problems of Radon transform / Ed. by S. Gindikin. 1994. Vol. 162 of American Mathematical Society Translations. Pp. 1-18.

46. Chatfield C. The Analysis of Time Series: An Introduction. 2nd edition. Chapman&Hall, London, 1980. P. 268.

47. Cheveigne A. D., Simon J. Z. Denoising based on time-shift PCA // Journal of Neuroscience Methods. 2007. Vol. 165. Pp. 297-305.

48. Chi-Jie L., Du-Ming T. Automatic defect inspection for LCDs usiizx^^ singular value decomposition // The International Journal of Advanced IVX^^nufactur-ing Technology. 2005. Vol. 25. Pp. 53-61.

49. Colebrook J. M. Continuous plankton records — zooplankton arxcfL environment, northeast Atlantic and North Sea // Oceanol. Acta, 1978. Vol. 1. Pp. 9-23.

50. Columbia-Utrecht Reflectance and Texture Database (CUReTT1^) 1999. URL: http: //wwwl. cs . Columbia. edu/CAVE/software/curet/ (^^гц^ата обращения: 08.09.2010).

51. Dalgaard P. Introductory Statistics with R. 2nd edition. Sprin.^er, 2008. P. 380.

52. Dana K. J., van Ginneken В., Nayar S. K., Koenderink J. J. Reflecttance and. Texture of Real World Surfaces // ACM Transactions on GraptiJL<3s. 1999. Vol. 18, no. 1. Pp. 1-34.

53. Daykin D. E. Distribution of bordered persymmetric matrices i^rx a finite field // J. Reine und Angew. Math. (Crelles Journal). 1960. "Vol. 203. Pp. 47-45.

54. Elkies N. D. On finite sequences satisfying linear recursions // INTew York Journal of Mathematics. 2002. Vol. 8. P. 85-97.

55. Feldmann S., Heinig G. Parametrization of minimal rank block Ы-eLiikel matrix extensions and minimal partial realizations // Integral Equations and Operator Theory. 1999. Vol. 33. Pp. 151-171.

56. Findley D. F. On the Early History of the Singular Value Decorrr£> <z>sition // SIAM Review. 1993. Vol. 35, no. 4. Pp. 551-566.

57. Florinsky I. Derivation of topographic variables from a digital elevation modelgiven by a spheroidal trapezoidal grid // International Journal of Geographical Information Science. 1998. Vol. 12. Pp. 829-852.

58. Florinsky I. Errors of signal processing in digital terrain modelling // International Journal of Geographical Information Science. 2002. Vol. 16, no. 5. Pp. 475-501.

59. Ghil M., Allen R., Dettinger M. et al. Advanced spectral methods for climatic time series // Rev. Geophys. 2002. Vol. 40, no. 1. Pp. 1-41.

60. Ghil M., Vautard R. Interdecadal oscillations and the warming trend in global temperature time series // Nature. 1991. Vol. 350. Pp. 324-327.

61. Golub G., Reinsch C. Singular value decomposition and least squares solutions // Numerical Mathematics. 1970. Vol. 14. Pp. 403-420.

62. Golyandina1 N. On the choice of parameters in Singular Spectrum Analysis and related subspace-based methods // Statistics and Its Interface. 2010. Vol. 3, no. 3. Pp. 259-279.

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

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

65. Golyandina N., Osipov E. The "Caterpillar'-SSA method for anatysis of time series with missing values // J. Stat. Plan. Infer. 2007. Vol. 137, no. 8. Pp. 2642-2653.

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

67. Golyandina N., Vlassieva E. First-order SSA-errors for long time series: model examples of simple noisy signals // Proceedings of the 6th St.Petersburg Workshop on Simulation Vol.1, June 28-July 4, 2009, St. Petersburg. 2009. Pp. 314-319.

68. Golyandina N. E., Usevich K. D. 2D-extension of Singular Spectrum Analysis: algorithm and elements of theory // Matrix methods: theory, algorithms and applications / Ed. by V. Olshevsky, E. Tyrtyshnikov. World Scientific, 2010. Pp. 449-473.

69. Govil N. K., Rahman Q. I. On the Enestrom-Kakeya theorem. // Tohoku Mathematical Journal. 1968. Vol. 20, no. 2. Pp. 126-136.

70. Hakopian H., Tonoyan M. Partial differential analogs of ordinary differential equations and systems // New York Journal of Mathematics. 2004. Vol. 10. Pp. 89-116.

71. Handbook of texture analysis, Ed. by M. Mirmehdi, X. Xie, J. Suri. Imperial College Press, 2008. P. 423.

72. Heinig G., Rost K. Algebraic methods for Toeplitz-like matrices and operators. Akademie Verlag, Berlin, 1984. P. 212.

73. Holloway D. M., Harrison L. G., Kosman D. et al. Analysis of Pattern Precision Shows That Drosophila Segmentation Develops Substantial Independence From Gradients of Maternal Gene Products // Development Dynamics. 2006. Vol. 235. Pp. 2949-2960.

74. Hsieh W. W., Hamilton K. Nonlinear singular spectrum analysis of the tropical stratospheric wind // Quarterly Journal of the Royal Meteorological Society. 2003. Vol. 129. Pp. 2367-2382.

75. Jevrejeva S., Moore J. C. Singular Spectrum Analysis of Baltic Sea ice conditions and large-scale atmospheric patterns since 1708 // Geophy. Res. Lett. 2001. Vol. 28, no. 23. Pp. 4503-4506.

76. Johnson S. G., Frigo M. A modified split-radix FFT with fewer arithmetic operations // IEEE Trans. Signal Processing. 2007. Vol. 55, no. 1. Pp. 111-119.

77. Kehrein A., Kreuzer M. Computing Border Bases // Journal of Pure and Applied Algebra. 2006.-May. Vol. 205, no. 2. Pp. 279-295.

78. Konstantinides K., Natarajan B., Yovanof G. S. Noise estimation and filtering using block-based singular value decomposition // IEEE Transactions on Image Processing. 1997. Vol. 6. Pp. 479-483.

79. Korobeynikov A. Computation- and space-efficient implementation of SSA // Statistics and Its Interface. 2010. Vol. 3, no. 3. Pp. 357-368.

80. Krim H., Forster P., Proakis J. G. Operator approach to performance analysis of root-MUSIC and root-min-norm // IEEE Transactions on Signal Processing. 1992. Vol. 40, no. 7. Pp. 1687-1696.

81. Kumaresan R. On the Zeros of the Linear Prediction-Error Filter for Deterministic Signals // IEEE Transactions on Acoustics, Speech, and Signal Processing. 1983. Vol. 31, no. 1. Pp. 217-220.

82. Kumaresan R., Tufts D. W. Data-adaptive principal component signal processing // Proc. of IEEE Conference On Decision and Control. Albuquerque, 1980. Pp. 949-954.

83. Kumaresan R., Tufts D. W. Estimating the Parameters of Exponentially Damped Sinusoids and Pole-Zero Modelling in Noise // IEEE Transactions on Acoustics, Speech, and Signal Processing. 1982. Vol. 30, no. 6. Pp. 833-840.

84. Kumaresan R., Tufts D. VV. Estimating the Angles of Arrival of Multiple Plane Waves // IEEE Transactions on Aerospace and Electronic Systems. 1983. Vol. AES-19, no. 1. Pp. 134-139.

85. Laub A. J. Matrix Analysis for Scientists and Engineers. SIAM, 2004.

86. Laws K. I. Textured image segmentation: Report 940 / Image Processing Institute, University of southern California. 1980. P. 190.

87. Li F., Liu H., Vaccaro R. J. Performance analysis for DOA estimation algorithms: unification, simplification, and observations // IEEE Transactions on Aerospace and Electronic Systems. 1993. Vol. 29, no. 4. Pp. 1170-1184.

88. Loan C. F. V., Pitsianis N. P. Approximation with Kronecker products // Linear Algebra for Large Scale and Real Time Applications / Ed. by M. S. Moo-nen, e. G. H. Golub. Kluwer Publications, 1993. Pp. 293-314.

89. Magnus J. R., Neudecker H. Matrix Differential Calculus with Applications to Statistics and Econometrics. John Wiley & Sons, 2004. P. 450.

90. Mahecha M., Reichstein M., Lange H. et al. Characterizing ecosystem-atmosphere interactions from short to interannual timescales // Biogeosciences Discuss. "2007. Vol. 4. Pp. 1405-1435.

91. Mamou J., Feleppa E. J. Singular spectrum analysis applied to ultrasonic detectionand imaging of brachytherapy seeds // J. Acoust. Soc. Am. 2007. Vol. 121, no. 3. Pp. 1790-1801.

92. Markovic D., Koch M. Characteristic scales, temporal variability modes and simulation of monthly Elbe River flow time series at ungauged locations // Physics and Chemistry of the Earth. 2006. Vol. 31. Pp. 1262-1273.

93. Martinez-Finkelshtein A., McLaughlin K. T.-R., Saff E. B. Szego Orthogonal Polynomials with Respect to an Analytic Weight: Canonical Representation and Strong Asymptotics // Constr. Approx. 2006. Vol. 24, no. 3. Pp. 319-363.

94. McElroy T., Sutcliffe A. An iterated parametric approach to nonstationary signal extraction // Computational Statistics & Data Analysis. 2006. Vol. 50. Pp. 2206-2231.

95. Monadjemi A. Towards Efficient Texture Classification and Abnormality Detection: Ph. D. thesis / Department of Computer Science, University of Bristol. 2004. P. 177.

96. Monadjemi A., Mirmehdi M., Thomas B. Restructured eigenfilter matching for novelty detection in random texture // In Proceedings of the 15th British Machine Vision Conference. 2004. Pp. 637-646.

97. Mourrain B. A New Criterion for Normal Form Algorithms // Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC-13. 1999. Pp. 430-443.

98. Nekrutkin V. Perturbation expansions of signal subspaces for long signals / / Statistics and Its Interface. 2010. Vol. 3, no. 3. Pp. 297-319.

99. Paegle J. N., Byerle L., Mo K. Intraseasonal Modulation of South American Summer // Monthly Weather Review. 2000. March. Vol. 128. Pp. 837-850.

100. Pakula L. Asymptotic Zero Distribution of Orthogonal Polynomials in Sinusoidal Frequency Estimation // IEEE Transactions on Information Theory. 1987. Vol. 33, no. 4. Pp. 569-576.

101. Pan V. Structured matrices and polynomials: unified superfast algorithms. Birkhauser Boston, 2001. P. 278.

102. Patel D., Davies E., Hannah I. The use of convolution-operators for detecting contaminants in food images // Pattern Recognition. 1996. Vol. 29, no. 6. Pp. 1019-1029.

103. Planas C. The Analysis of Seasonality in Economic Statistics: A Survey of Recent Developments: Tech. rep.: EUROSTAT working group document, 1997.198

104. Randen Т., Husoy J. H. Filtering for Texture Classification: A Comparative Study // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1999. Vol. 21, no. 4. Pp. 291-310.

105. Rezek I., Roberts S. Stochastic Complexity Measures for Physiological Signal Analysis // IEEE Transactions on BME. 1998. —Sept. Vol. 25, no. 9. Pp. 1186-1191.

106. Rodriguez-Aragon L. J., Zhigljavsky A. Singular spectrum analysis for image processing // Statistics and Its Interface. 2010. Vol. 3, no. 3. Pp. 419-426.

107. Rouquette S., Najim M. Estimation of frequencies and damping factors by two-dimensional ESPRIT type methods // IEEE Transactions on Signal Processing. 2001. Vol. 49, no. 1. Pp. 237-245.

108. Roy R., Kailath T. ESPRIT: estimation of signal parameters via rotational invariance techniques // IEEE Tians. Acoust. 1989. Vol. 37. Pp. 984-995.

109. Serita A., Hattori K., Yoshino С., M. Hayakawa N. I. Principal component analysis and singular spectrum analysis of ULF geomagnetic data associated with earthquakes // Natural Hazards and Earth System Sciences. 2005. Vol. 5. Pp. 685-689.

110. Simon B. Orthogonal Polynomials on the Unit Circle, Part 1: Classical Theory. AMS Colloquium Series, AMS, Providence, RI, 2005. P. 466.

111. SRTM3 (Shuttle Radar Topographic Mission) Version 2. 2003. URL: http://dds.cr.usgs.gov/srtm/version2l/SRTM3/ (дата обращения: 08.10.2011).

112. Stepanov D., Golyandina N. SSA-based approaches to analysis and forecast of multidimensional time series // Proceedings of the 5th St.Petersburg Workshop on Simulation, St. Petersburg State University, St. Petersburg. 2005. Pp. 293-298.

113. Stetter H. J. Numerical polynomial algebra. SIAM, Philadelphia, 2004. P. 472.

114. Stoica P., Moses R. L. Introduction to spectral analysis. Prentice Hall, 1997. P. 319.

115. Strang G. Introduction to Linear Algebra. 2003. P. 568.

116. Szabados J. On some problems connected with orthogonal polynomials // Acta Mathernatica Academiae Scientarium Hungaricae. 1979. Vol. 33, no. 1-2. Pp. 197-210.

117. Thomakos D., Wanga Т., Wille L. Modeling daily realized futures volatility with singular spectrum analysis // Physica A: Statistical Mechanics and its Applications. 2002. Vol. 312, no. 3-4. Pp. 505-519.

118. Unser M., Ade F. Feature extraction and decision procedure for automated inspection of textured materials // Pattern Recognition Letters. 1984.— March. Vol. 2. Pp. 181-195.

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

120. Varma M., Zisserman A. Texture Classification: Are Filter Banks Necessary? // IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 18-20 June 2003. Proceedings. Vol. 2. 2003. Pp. 691-698.

121. Varma M., Zisserman A. A Statistical Approach to Texture Classification from Single Images // Int. J. Comput. Vision. 2005. Vol. 62, no. 1-2. Pp. 61-81.

122. Vassiliev N., Pavlov D. Strong non-Noetherity of polynomial reduction // Записки научных семинаров ПОМИ. 2009. Т. 373. С. 73-76.

123. Wang F., Wang S., Dou H. Estimating two-dimensional frequency pairs by extended Esprit-type method // Proceedings, ICCT 2003. International Conference on Communication Technology. Vol. 2. 2003. Pp. 1464-1467.

124. Yang H. H., Hua Y. On Rank of Block Hankel Matrix for 2-D Frequency Detection and Estimation // IEEE Transactions on Signal Processing. 1996. Vol. 44, no. 4. Pp. 1046-1048.

125. Yu X.-L., Buckley K. M. Bias and variance of direction-of-arrival estimates from MUSIC, MIN-NORM, and FINE // IEEE Transactions on Signal Processing. 1994. Vol. 42, no. 7. Pp. 1812-1816.