Фреймоподобные системы всплесков

Кривошеин, Александр Владимирович

Фреймоподобные системы всплесков тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Кривошеин, Александр Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Санкт-Петербург МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «Фреймоподобные системы всплесков»

Автореферат диссертации на тему "Фреймоподобные системы всплесков"

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

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

[уЛ

005531450

Кривошеин Александр Владимирович

ФРЕЙМОПОДОБНЫЕ СИСТЕМЫ ВСПЛЕСКОВ

01.01.07 - Вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

11 гт тз

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

2013

005531450

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

Научный руководитель: доктор физико-математических наук, профессор СКОПИНА Мария Александровна

Официальные оппоненты: доктор физико-математических наук, профессор ВИНОГРАДОВ Олег Леонидович (Саикт-Петербургский государственный университет, профессор)

кандидат физико-математических наук, доцент ЛЕБЕДЕВА Елена Александровна (Санкт-Петербургский государственный политехнический университет, доцент)

Ведущая организация: Воронежский государственный университет

Защита состоится 12 сентября 2013 г. в \_3 часов о 0 минут на заседании . диссертационного совета Д 212.232.49 на базе Санкт-Петербургского государственного университета по адресу: 199178, Санкт-Петербург, 14 линия В.О., д. 29, математико-механический факультет, ауд. 22.

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

Автореферат разослан " __2013 г.

Ученый секретарь диссертационного совета

Ю.В.Чурин

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

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

Теория всплесков, наряду с ее огромным значением в цифровой обработке сигналов, также внесла и существенный вклад в развитие ряда разделов математики. Можно отметить построение оптимальных полиномиальных ортогональных базисов в пространствах непрерывных на отрезке и периодических функций, конструктивное описание различных функциональных пространств и построение безусловных базисов в них, в частности безусловных базисов в анизотропных пространствах Соболева, Бесова и Лизоркина-Трибеля. Значение теоретических результатов полученных с развитием теории всплесков общепризнано научным сообществом. За фундаментальные исследования в этой области И. Мейер стал лауреатом премии Гаусса, которая была вручена ему на Международном математическом конгрессе в августе 2010 г.

В последние годы активно изучаются фреймы всплесков, особенно в США и Канаде. Понятие фрейма было введено в 1952 году Р. Даффином и А. Шеф-фером. Однако оно было практически забыто до появления теории всплесков. В настоящее время публикуется значительное число работ, связанных с фреймами всплесков. Этой темой занимались такие выдающиеся математики, как И. Добеши, А. Рон, Б. Хан, Ч. Чуй. Также существенный вклад внесли М. Бо-уник, 3. Шен, А. Петухов, Д. Стоклер, В. Лоутон, М-Дж. Лай, С. Гох, 3. Лим, Ж. Джанг, М. Скопина и др. Фреймы являются системами представления, но в отличие от базисов, разложение по ним не единственное. За счет избыточности в ряде приложений фреймы всплесков позволяют добиться лучших результатов по сравнению с базисами всплесков. Например, при обработке

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

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

М.А. Скопиной была поставлена задача по изучению систем всплесков, полученных по унитарному принципу расширения, но не являющихся фреймами, а также исследованию их обобщений в различных функциональных пространствах, в том числе и в пространстве обобщенных функций медленного роста. Такие системы были названы фреймоподобными системами всплесков. Эти исследования тесно перекликаются с работами Б. Хана в которых он вводит понятие частотных однородных/неоднородных двойственных систем всплесков в пространстве обобщенных функций (pair of frequency-based homogeneous/nonhomogeneous dual wavelet systems).

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

Вопросы, связанные с обеспечением специальных свойств для систем всплесков, исследовались И. Добеши, Ч. Чуй, Б. Ханом, 3. Шеном и др.

Ключевой сложностью при построении систем всплесков по унитарному принципу расширения или его модификациям является проблема расширения заданной строки из тригонометрических полиномов до унитарной матрицы из тригонометрических полиномов, или двух строк до двух матриц, так чтобы столбцы были попрано биортогональны. В одномерном случае такой способ матричного расширения предложен В. Лоутоном, С. Ли и 3. Шеном. Более того, для симметричной строчки тригонометрических полиномов задача симметричного матричного расширения, то есть такого, чтобы все тригонометрические полиномы также обладали свойством симметрии, решена в работах А. Петухова для вещественнозначных функций и Б. Хана для комплексно-значных. Это позволило для случая одной переменной получить алгоритмы вычисления коэффициентов всплеск-масок для построения одномерных симметричных систем всплесков с произвольных коэффициентом растяжения, обладающих различными полезными для приложений свойствами.

Возможность биортогонального матричного расширения в многомерном случае имеет отношение к известной проблеме Сэрра, которую независимо решили Д. Квиллсн и А. Суслин для алгебраических полиномов. Далее, А. Сус-лин распространил этот результат на более широкий класс колец, в частности кольцо лорановских полиномов. Отсюда следует возможность биортогонального расширения. Алгоритм для расширения матриц предложили X. Парк и С. Вудбурн. Однако из-за высокой сложности этот алгоритм фактически непригоден для практического использования. Задача симметричного матричного растяжения в многомерном случае осложняется еще и тем, что в этом случае существуют различные виды симметрии. Не говоря уж о том, что требуется дополнительно обеспечить иные полезные свойства. В настоящее время общих подходов к решению этой задачи нет, однако для конкретных частных случаев матричное продолжение может быть построено. Вопрос о возможности унитарного матричного расширения по любой заданной строчке в многомерном случае до сих пор остается открытой проблемой.

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

Работа выполнена при финансовой поддержке грантов РФФИ № 09-0100162, № 12-01-00216 и СПбГУ № 9.38.62.2012.

Цели работы:

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

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

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

Результаты, выносимые на защиту.

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

- Указан способ построения фреймоподобных систем всплесков, обеспечивающий произвольный порядок аппроксимации, при этом число порождающих всплеск-функций на единицу больше минимально возможного;

- Дано описание всех масштабирующих масок, обладающих центральной симметрией, для которых выполняется правило сумм произвольного порядка;

- Получены конструктивные алгоритмы вычисления коэффициентов симметричных в различных смыслах всплеск-масок, обеспечивающие для соответствующей фреймоподобной системы всплесков любой наперед заданный порядок аппроксимации;

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

- На основе системы компьютерной алгебры МаЛета^са 8.0 написан пакет, реализующий вычислительный алгоритм построения центрально-симметричных фреймоподобных систем с произвольным порядком аппроксима-

ции. С помощью пакета посчитаны примеры таких систем.

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

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

Аппробация работы. Результаты данной работы докладывались

- на конференциях: «Applied Harmonic Analysis and Multiscale Computing», Эдмонтон, Канада (2011), Саратовская зимняя математическая школа «Современные проблемы теории функций и их приложения», Саратов, Россия (2012), «Ряды Фурье и их приложения», Абрау-Дюрсо, Россия (2012), Международная конференция «Wavelets and applications», Санкт-Петербург, Россия (2012), Воронежская зимняя математическая школа «Современные проблемы теории функций и их приложения», Воронеж, Россия (2013),

- на семинаре «Конструктивная теория функций» в СПбГУ (2010-2013).

Публикации. Основные результаты опубликованы в работах [1-8]. Работа [1] соответствует списку ВАК РФ. Работа [2] опубликована в сборнике трудов института математики НАН Украины. Работа [7] опубликована в высокорейтинговом журнале, входящем в базы данных Web of Science и Scopus. Работа [8] принята к печати в том же журнале. Работы [3-6] опубликованы в материалах конференций.

В совместной с научным руководителем М.А. Скопиной работе [2] соавтору принадлежит постановка задачи и общая идея метода се решения. В совместной с М.А. Скопиной работе [7] соавтору принадлежат постановка задачи, разработка общей схемы исследования, формулировки и доказательства некоторых утверждений, именно, лемма 1, формулировка и идея доказательства теоремы 2, пункт (Ь) теоремы 10, теорема 16. Доказательства основных положений, включенных в диссертацию, проведены автором диссертации самостоятельно.

Структура и объем. Диссертация объемом 139 страницы состоит из введения, трех глав, разделенных на параграфы, списка литературы, содержащего 62 источника, и приложения с примерами. Окончания доказательств отмечены знаком О-

Основное содержание работы

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

Системой всплесков будем называть множество функций следующего вида {ф^} := {тп?12фМ{М> ■ +к), з 6 Ъ, к £ Ъ6-, и = 1,..., г, г > тп - 1}, где М - матрица растяжения размера с! х й, т = | det М| > 1. Б(М) обозначает множество цифр матрицы М. Не умаляя общности, полагаем, что 0 6 £>(М).

Функция <р называется масштабирующей, если ее преобразование Фурье удовлетворяет масштабирующему уравнению

где то тригонометрический полином, называемый маской, то(0) = 1. Известно, что для любой маски то функция := то(М*~:1£) дает единственное (с точностью до множителя) решение масштабирующего уравнения и является преобразованием Фурье некоторой функции ¡р € Б' с компактным носителем, где 5" - множество обобщенных функций медленного роста.

Будем говорить, что маска т обладает обнуляющимися моментами до порядка п е М, если

= 0, У/)6Д„

С=о

где Дп = {/3 £ Ъй+, Ц/ЗЦ1 = п}. Будем говорить, что для маски т выполняется правило сумм до порядка п £ М, если

=0, Уз £ £>(ЛГ) \ {0}, V/? € Д„.

Унитарный принцип расширения для построения систем всплесков заключается в следующем. Рассмотрим <р,(р - две масштабирующие функции с масками т0,т0 соответственно. Предположим, что существуют тригонометрические полиномы т„, и = I,... ,г, г > т — 1 (всплеск-маски), такие

что матрицы

С := {т„(£ + М-Ч)}Й!;Г\ С ■= + М'-'д^оГ1 >

где {д0, • • •, Ят-1} = 0{М*), удовлетворяют следующему равенству

С С — З-т-

Определим всплеск-функции фи =1,...,г, задав их преобразование Фурье по формулам

Если всплеск-функции и = 1,...,г построены вышеизложенным

способом-, тогда систему функций {ф{Ф^} будем называть двойственной системой всплесков, порожденной масштабирующими функциями (р, (или масками то,то).

Пусть А - класс функций для которых функционалы {/,фок), имеют смысл (например, если (/? € £", то / € где 5 - класс Шварца). Будем говорить, что система {ф^} почти фреймоподобпа, если V/ € Л

оо г

/ = £ а, + £ £ £ </'

ке!.'' 1=0 к^Ъ*

Систему {ф^} будем называть фреймоподобпой, если V/ € Л

00 г

/= Е ££</.®>^-

j~-oo ке Ъ*1

Ряды сходятся в некотором естественном смысле.

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

В §2.1 исследуется оператор масштабирования, который определен как

Qj(<p>&f) '•= Y,keZd(f''Pjk)iPjk, где функции ip,ip принадлежат различным функциональным пространствам. Прежде всего, рассмотрен наиболее общий случай.

Теорема 1 Пусть ip,<p € S' имеют компактный носитель, / € S. Тогда

(i) для любого j € Z ряд J2kezd(f''Pjk)(Pjk сходится безусловно в S', в частности, Qj{ip,ip, /) G S'.

(ii) Qj{<p, ip, f) стремится к ^(0)^(0)/ в S' при j —> +оо.

Далее, пара аналогичных теорем доказана для пространств Lp и одного особого случая. Под понимаем подмножество пространства Loo(Rd),

такое что для / е ¿^(R^): Пт^^^ /(х) = 0.

Теорема 2 Пусть при 1 < р < оо, 1 + ^ = 1, функции ip € L9(Rd) и tp € Lp(Rd) имеют компактный носитель, f € Lp(M.d); при р = оо функции ip е Li(Rd) и ip € //^(Ш^) имеют компактный носитель, / £ //^(R^). Тогда

(i) для всех j € Ъ, ряд ^2kezd(f>Vjk)tPjk сходится безусловно в Lp(Rd), при этом Qj(ip,<p,f) е Lp(Rd);

(ii) справедливо неравенство \\Qj(tp, ip, f)\\p < Cp^\\f\\p;

(iii) если p > 1, тогда lim \\Qj(<p, ip, /)|| =0.

j—>—00 p

Теорема 3 Пусть ip € L2(M.d), ip s S' имеют компактный носитель, f G S. Тогда

(i) для всех j € Ъ, ряд ^2keZd(f, ipjk)<pjk сходится безусловно в пРи

этом Qj(tp, ip, f) е L2{Rd);

(ii) если <p(0) = <^(0) = 1, то условия Стрэнга-Фикса до порядка 1 для функции ip являются необходимыми и достаточными для сходимости Qj(<p, ip, /) к функции / по норме Ь2 при j -э- +оо.

Результаты §2.2-2.3 относятся уже непосредственно к системам всплесков. Прежде всего, приведен метод, позволяющий строить системы всплесков, обладающие произвольным числом обнуляющихся моментов. Это свойство, как далее будет ясно, напрямую связано с порядком аппроксимации построенной системы.

Система всплесков {ф^}, V = I,... ,г, с компактным носителем обладает

обнуляющимися моментами до порядка п, п € N (имеет УМп свойство), если 0) = О, V = 1,..., г, для всех /3 € Д„. Условия на исходные маски

то, "1о и явные формулы для получения всплеск-функций с УМп свойством указаны в §2.2.

Лемма 4 Пусть масштабирующие функции € 5' имеют компактный носитель, т0,то - их маски, п £ N. Если для маски то выполняется правило сумм до порядка п, а маска т0 удовлетворяет условию

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

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

Теорема 5 Пусть / € 5, масштабирующие функции (р, <р € 5" имеют компактный носитель. Двойственная система всплесков {ф^}, {Ф^}> V = 1,. , г, порооюдена функциями <р,ф. Тогда {ф^} является почти фреймоподобной.

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

тогда существует двойственная система всплесков {ф^}, {Ф$} пороэ/с денная <р,(р такая, что система {ф^} обладает VМп свойством.

Теорема 6 Пусть масштабирующие функции & 5' имеют компактный носитель, / € 5. Двойственная система всплесков {'Ф^}}, {Ф^}, V = 1,... ,г, порождена функциями <р, <р. Тогда {ф^)} является почти фрей-моподобпой, где ряды сходятся в £". Если система {Фр?} обладает УМп свойством, то Уд € 51

ке:

¿-1

г=0 1/=1 ке 2

/ - £ </, еьо- £ £ £ </, <?) <

гс?е Л наименьшее по модулю собственное число матрицы М, е > 0, |А|— е > 1, С не зависит от

Теорема 7 Пусть масштабирующие функции £ ), <Р € 5" име-

ют компактный носитель, / £ 5". Двойственная система всплесков {Ф^)}, {Ф^к}, V = 1,..., г, пороэюдена функциями <р,<р. Тогда {Ф^} является почти фреймоподобной, где ряды сходятся по норме вЬ2(К'1). Если система {Ф$} обладает УМп свойством, то

/-£(/. ёок)ч>ак -£££</. ФШ.

кехЛ «=о и=1 кегЛ

С\\

где А наименьшее по модулю собственное число матрицы М, е > 0, |А|— е > 1, го* > те, Сип* ие зависят от / и

Теорема 8 Пусть 1 < р < оо, ^ + ^ = 1> масштабирующие функции

V е Ь,

и (р £ Ь^

имеют компактный носитель, f £ Ьр{Шг). Двойственная система всплесков {фр)}, {Ф^}, и — порооюдеиа функциями (р, <р. Тогда {фр)} является фреймоподобной, где ряды сходятся по норме в Ьр(Ш ). Если система {ф^} обладает УМп свойством, то для / £ имеет место

з-1 >=-оо ке

см

где А наименьшее по модулю собственное число матрицыМ, е > 0, |А|— е > 1, С не зависит от / и ].

Теорема 9 Пусть масштабирующие функции ¡р ё Ь^Ш1),^ £ Ь00(К<') имеют компактный носитель, / € ^(М^). Двойственная система всплесков {Цк}> ^ = 1) • • • >Л порождена функциями у, 1р. Тогда {ф^} является почти фреймоподобной, где ряды сходятся по норме е./^Е''). Если система обладает, УМп свойством, то для / € И^Е^),

/-£</, - Ё Е Е </.

< сНЛк-

- (|А|-е)*'

где Л наименьшее по модулю собственное число матрицы М, £ > 0, |А| — е > 1, С и п* не зависят от / и 3.

Глава 3 посвящена обеспечению свойства симметрии (в различных смысла) для систем всплесков в многомерном случае. Понятие симметрии определим с помощью группы симметрии. Будем называть множество унимодуляр-ных матриц Я группой симметрий на если Я является группой относительно матричного умножения. Маска ш является Я-симметричной относительно центра с € К"4, если

т(£) = е2п^с~Ес'®т{Е*£), УЕ е Я е М1*

и с — Ее & Ъй, УЕ € Я. Центр симметрии назовем подходящим для группы Я, если с — Ее € УЕ € Я. Будем рассматривать следующие виды симметрии: центральная с группой Я = {1а, —1^} и произвольными матрицами растяжения М, осевая с группой

Нах{з := {<Иа 8(«ь ...,иа)-.щ = ±\,з = \,..., ¿}

и матрицами растяжения вида М = ... ,та)Р, где Р перестановоч-

ная матрица, иные группы симметрий с особыми условиями, а также центральную симметрию другого вида: т(£) = е2,г,(2с'^т(£). Отметим, что для центральной и осевой групп симметрии с е Тогда для этих групп выполняется с — Ее е ЧЕ е Я. Для иных рассматриваемых групп симметрии полагаем с €

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

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

Теорема 10 Пусть с - подходящий центр симметрии, п € N. Тогда существует маска то, которая симметрична (в любом из указанных выше смыслов) относительно центра с и для которой выполняется правило сумм до порядка п. Для центрально-симметрич?шх относительно центра с в обоих смыслах масок то приводится общий вид всех таких масок.

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

Теорема 11 Пусть с - подходящий центр симметрии, и е М, маска то является симметричной (в любом из указанных выше смыслов) относительно центра с и для нее выполняется правило сумм до порядка п. Тогда существует симметричная (в любом из указанных выше смыслов) маска то, удовлетворяющая условию

& (1 - гоо(£)йЩ) | = О УР е Д„,

причем центр симметрии может быть равным только с.

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

Теорема 12 Пусть с - подходящий центр симметрии п € N. Маски то и т,о симметричны (в любом из указанных выше смыслов) относительно центра с, для маски то выполняется правило сумм до порядка п, маска то подходящая. Тогда существуют маски т„ и т„, V = 1,... ,т, которые являются симметричными/антисимметричными (в любом из указанных выше смыслов) относительно некоторых центров и всплеск-маскит„, и = 1,..., т, имеют обнуляющиеся моменты до порядка п.

Следующий результат дополняет результаты работы С. Караказьян, М. Скопиной и М. Чобану [2009]. Маска то называется интерполяционной, если имеет место следующее тождество о(м-) та(€ + М*~1в) = 1. В указанной

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

Теорема 13 Пусть п € N. Интерполяционная маска то симметрична (в любом из указанных выше смыслов) относительно нуля и для нее выполняется правило сумм до порядка п. Тогда существует подходящая маска т0 и всплеск-маски т„ и ти, и = 1, ...,т — 1, которые являются сим-метричпыми/антисимметричными (в любом из указанных выше смыслов) относительно некоторых центров и все всплеск-маски т„ и т„ имеют обнуляющиеся моменты до порядка п.

Также, для интерполяционных и М-ортогональных масок установлен схожий результат. Маска т0 называется М-ортогональной, если

|шо(£ + М*_1а)|2 = 1.

яб

Теорема 14 Пусть п е N. М-ортогональная интерполяционная маска т0 симметрична (в любом из указанных выше смыслов) относительно нуля и для нее выполняется правило сумм до порядкап. Тогда существуют маски га,,, и = 1,... ,тп — 1, которые являются симметричными/антисимметричными (в любом из указанных выше смыслов) относительно некоторых центров и все всплеск-маски т„ имеют обнуляющиеся моменты до порядка п.

Системы всплесков, построенные по последней теореме, в силу М-ортого-налыюсти маски и модификации известной теореме Малла, принадлежат пространству ¿гО^) и образуют симметричный (в любом из указанных выше смыслов) жесткий фрейм всплесков. А если система {<рак}ке1* является ортогональной, то и симметричный (в любом из указанных выше смыслов) ортогональный базис всплесков.

Публикации автора по теме диссертации.

1. Кривошеин А. В. О порядке аппроксимации многомерных систем всплесков // Вестник С.-Петерб. ун-та. 2010. Сер. 10, вып. 3. С. 44-58.

2. Кривошеин А. В., Скопина М. А. Фреймоподобные системы всплесков // 36. праць 1н-ту математики НАН Укра'ши. 2009. Т. 6. С. 96-114.

3. Кривошеин А. В. О построении симметричных фреймоподобных систем / Материалы 16-й Саратовской зимней школы (Саратов, Россия).

2012. С. 100.

4. Кривошеин А. В. О построении симметричных систем всплесков / Материалы Воронежской зимней математической школы (Воронеж, Россия).

2013. С. 126.

5. Krivoshein А. V. On construction of symmetric MRA-based framelike wavelet systems / Тезисы докладов международной конференции «Applied Harmonic Analysis and Multiscale Computing» (Эдмонтон, Канада) 2011. С. 15.

6. Krivoshein A. V., Skopina M. A. Approximation by frame-like wavelet systems / Тезисы докладов международной конференции «Теория приближений» (Санкт-Петербург, Россия). 2010. С. 125-127.

7. Krivoshein A., Skopina М. Approximation by frame-like wavelet systems // Appl. Comput. Harmon. Anal. 2011. Vol. 31. P. 410428.

8. Krivoshein A. On construction of multivariate symmetric MRA-based wavelets // Appl. Comput. Harmon. Anal. 2013. Available online: http://dx.doi.Org/10.1016/j.acha.2013.04.001.

Подписано к печати 27.05.13. Формат 60 х 84 Vie . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. _Тираж 100 экз. Заказ 5809._

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Кривошеин, Александр Владимирович, Санкт-Петербург

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

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

0420136,324

Кривошеин Александр Владимирович ФРЕЙМОПОДОБНЫЕ СИСТЕМЫ ВСПЛЕСКОВ

01.01.07 - Вычислительная математика

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

Научный руководитель доктор физико-математических наук профессор М. А. Скопина

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

2013

Посвящаю родителям и моей дорогой Жене.

Оглавление

Введение 4

1 Обозначения и вспомогательные результаты 18

1.1 Обозначения .............................18

1.2 Предварительные сведения.....................23

1.3 Вспомогательные результаты....................29

2 Фреймоподобные системы всплесков 36

2.1 Оператор масштабирования и его свойства............37

2.2 Реализация принципа расширения.................50

2.3 Разложения по системе всплесков.................54

2.4 Выводы................................69

3 Построение симметричных систем всплесков 71

3.1 Группы симметрий..........................72

3.2 Результаты..............................76

3.3 Симметричные фреймоподобные системы.............78

3.3.1 Центрально-симметричные фреймоподобные системы . . 81

3.3.2 Фреймоподобные системы с осевой симметрией......99

3.3.3 Фреймоподобные системы с различной симметрией . . .117

3.4 Симметричные фреймы всплесков.................120

3.4.1 Предварительные сведения.................121

3.4.2 Построение симметричных фреймов всплесков......124

Литература 127

Приложение 134

Введение

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

уник, 3. Шен, А. Петухов, Д. Стоклер, В. Лоутон, М-Дж. Лай, С. Гох, 3. Лим, Ж. Джанг, М. Скопина и др. Фреймы являются системами представления, но в отличие от базисов, разложение по ним не единственное. За счет избыточности в ряде приложений фреймы всплесков позволяют добиться лучших результатов по сравнению с базисами всплесков. Например, при обработке сигнала с помощью фреймов всплесков, потеря или искажение части коэффициентов разложения сигнала не обязательно влияет на возможность его полного восстановления (что принципиально невозможно для разложений по базисам всплесков).

свойством линейной фазы, что влечет за собой отсутствие фазовых искажений при обработке. Кроме того, симметрия позволяет избежать проблем, связанных с разрывностью сигнала на границах, а также уменьшить вычислительную сложность обработки данных. Высокое число обнуляющихся моментов у системы всплесков связано с высоким порядком аппроксимации. Вопросы, связанные с обеспечением специальных свойств для систем всплесков, исследовались И. Добеши, Ч. Чуй, Б. Ханом, 3. Шеном и др.

Возможность биортогонального матричного расширения в многомерном случае имеет отношение к известной проблеме Сэрра, которую независимо решили Д. Квиллен и А. Суслин для алгебраических полиномов. Далее, А. Сус-лин распространил этот результат на более широкий класс колец, в частности кольцо лорановских полиномов. Отсюда следует возможность биортогонального расширения. Алгоритм для расширения матриц предложили X. Парк и С. Вудбурн. Однако из-за высокой сложности этот алгоритм фактически непригоден для практического использования. Задача симметричного матричного растяжения в многомерном случае осложняется еще и тем, что в этом случае существуют различные виды симметрии. Не говоря уж о том, что требуется дополнительно обеспечить иные полезные свойства. В настоящее время общих подходов к решению этой задачи нет, однако для конкретных частных случаев матричное продолжение может быть построено. Вопрос

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

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

Работа выполнена при финансовой поддержке грантов РФФИ № 09-0100162, № 12-01-00216 и СПбГУ № 9.38.62.2012.

Цели работы:

Результаты, выносимые на защиту.

- На основе системы компьютерной алгебры Mathematica 8.0 написан пакет, реализующий вычислительный алгоритм построения центрально-симметричных фреймоподобных систем с произвольным порядком аппроксимации. С помощью пакета посчитаны примеры таких систем.

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

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

Аппробация работы. Результаты данной работы доклады вались

- на семинаре «Конструктивная теория функций» в СПбГУ (2010-2013).

Публикации. Основные результаты опубликованы в работах [3], [4], [5],

[б], [7], [47], [48], [49] и [50], а также в препринте [46]. Работа [4] опубликована в сборнике трудов института математики HAH Украины. Работа [3] соответствует списку ВАК РФ. Работа [50] опубликована в высоко-рейтинговом журнале, входящем в базы данных Web of Science и Scopus. Работы [5], [б], [7], [47], [48], [49] опубликованы в материалах конференций.

В совместной с научным руководителем М.А. Скопиной работе [4] соавтору принадлежит постановка задачи и общая идея метода ее решения. В совместной с М.А. Скопиной работе [50]соавтору принадлежат постановка задачи, разработка общей схемы исследования, формулировки и доказательства некоторых утверждений, именно, лемма 1, формулировка и идея доказатель-

ства теоремы 2, пункт (Ь) теоремы 10, теорема 16. Доказательства основных положений, включенных в диссертацию, проведены автором диссертации самостоятельно.

Структура и объем. Диссертация объемом 139 страницы состоит из введения, трех глав, разделенных на параграфы, списка литературы, содержащего 62 источников. Окончания доказательств отмечены знаком О-

Основное содержание работы.

Системой всплесков будем называть множество функций следующего вида {ф^} := {т?/2фМ(АР - +*), з <Е г, к € V = 1,... ,г, г > т - 1}, где М - матрица растяжения размера в, х т — | det М\ > 1. О(М) обозначает множество цифр матрицы М. Не умаляя общности, полагаем, что О € О(М).

Функция (р называется масштабирующей, если ее преобразование Фурье удовлетворяет масштабирующему уравнению

Ф(0 = тоШ'-^ЖМ^а

где Шо тригонометрический полином, называемый маской, то (О) = 1. Известно (см., например, [8, § 2.4]), что для любой маски т0 функция <£>(£) := дает единственное (с точностью до множителя) решение масштабирующего уравнения и является преобразованием Фурье некоторой функции ср € Б' с компактным носителем, где 5' - множество обобщенных функций медленного роста.

Будем говорить, что маска тп обладает обнуляющимися моментами до порядка п 6 М, если

=01 € Ап,

£=о

где Д„ = {¡5 е ||/3||х = д}. Будем говорить, что для маски т выполняется правило сумм до порядка п € М, если

£^т(ЛГ=0, УЙ € Я(АГ) \ {0}5 € Д„.

Унитарный принцип расширения для построения систем всплесков заключается в следующем. Рассмотрим <р, <р - две масштабирующие функции с масками то, то соответственно. Предположим, что существуют тригонометрические полиномы ту, т», V — 1,...,г, г > т — 1 (всплеск-маски), такие что матрицы

£ +£ -■= +лг-^ЙЗГ1.

где {<7о,..., г/т1} — В{М*), удовлетворяют следующему равенству

СТ1= /т.

Определим всплеск-функции и 1,..., г, задав их преобразование

Фурье по формулам

Если всплеск-функции и — 1,..., г построены вышеизложенным

способом, тогда систему функций {ф^}-, Ы^к } будем называть двойственной системой всплесков, порожденной масштабирующими функциями <р, кр (или масками то, то).

Пусть А - класс функций для которых функционалы {/, <рок), (/, Ф^) имеют смысл (например, если (р 6 5", то / 6 Я, где 5 - класс Шварца). Будем говорить, что система {ф^} почти фреймоподобна, если У/6-4

ос г

/=£</, йж*+Е Е Е </.

Систему {ф^}} будем называть фреймоподобной, если V/ е Л

оо г

/= EEEtf-^VS?-

Ряды сходятся в некотором естественном смысле.

В §2.1 исследуется оператор масштабирования, который определен как Qj(<p,ip,f) := 52keZd(f,Pjk)tfjk, где функции (р,<р принадлежат различным функциональным пространствам. Прежде всего, рассмотрен наиболее общий случай.

Теорема 1 Пусть (p,ip Е S' имеют компактный носитель, f € S. Тогда

(i) для любого j € Z ряд Ylkezd(f->^jk)^Pjk сходится безусловно в S', в частности, Qj{(p,<p, /) € S'.

(ii) Qj((p, <р, /) стремится к у?(0)£>(0)/ в S' при j —» +оо.

Далее, пара аналогичных теорем доказана для пространств Lp и одного особого случая. Под Rd) понимаем подмножество пространства L^ (Rd), такое что для / 6 ¿4(Rd): fix) =

Теорема 2 Пусть при I < р < ос, ^ -f 1 = функции у? € Z/q(Rd) и (р 6 Lp(Rd) имеют компактный носитель, / G Lp(Md); при р = оо функции ip € Li(Rd) и (р £ Loo(Rd) имеют компактный носитель, / € L^W1). Тогда

(г) для всех j € Ъ, ряд YlkeZdif-> <Р]к)<Рзк сходится безусловно в Lp(M.d), при этом Qj(<p, (р, /) € Lp(Rd):

(И) справедливо неравенство \\Qj{<p,<p,f)\\p < CPAPg\\f\\p,

(iii) если р > 1, тогда lim \\Qj{(p, ip, /)|| = 0.

j—эо ^

Теорема 3 Пусть <р € Z,2(Rd)> (р € S' имеют компактный носитель, / € Тогда

(г) для всех э £ Ъ, ряд ^кегЛ/^ сходится безусловно в при

этом (р,./) € Ь2{Шё);

(И) если <р(0) = ср(0) = 1; то условия Стрэпга-Фикса до порядка 1 для функции (р являются необходимыми и достаточными для сходимости /) к функции / по норме Ь2 при ] —> +оо.

Система всплесков {ф^}}, ^ = 1,..., г, с компактным носителем обладает обнуляющимися моментами до порядка ?г, п € N (имеет VМп свойство), если В^ф^Цо) = О, V = 1,..., г, для всех ¡3 € Лп. Условия на исходные маски то, то и явные формулы для получения всплеск-функций с УЛ/П свойством указаны в §2.2.

Лемма 4 Пусть масштабирующие функции ср,(р �