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

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

8046076^»

Соловьева Наталья Анатольевна (/

ВЕЙВЛЕТЫ И ФРЕЙМЫ В ДИСКРЕТНОМ АНАЛИЗЕ

01.01.07 — вычислительная математика

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

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

- 2 СЕН 2010

004607638

Работа выполнена на кафедре исследования операций

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

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

доктор физико-математических наук, профессор Малозёмов Василий Николаевич

официальные оппоненты:

доктор физико-математических наук, профессор Демьянович Юрий Казимирович, (Санкт-Петербургский государственный университет)

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

Беспалов Михаил Сергеевич (Владимирский государственный университет)

Защита состоится 23 сентября 2010 г. в «/_2_» часов на заседании совета Д 212.232.49 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., д. 28, математико-механический факультет, ауд. 405.

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

Автореферат разослан ШъМ^ 2010 г.

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

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Академический университет РАН (Санкт-Петербург)

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

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

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

Общепринятый базис Фурье хорошо выделяет частоты, но не даёт информации о резких и коротких всплесках и вообще о локальном поведении функции. Желательно, чтобы элементы базиса были лучше локализованы по времени. Вейвлетные базисы удовлетворяют такому требованию. Часто накладываются и дополнительные условия, например, ортогональность базиса, компактность носителей вейвлетов и т. д.

Теория вейвлетов начала активно развиваться в 80-90-е годы двадцатого века. К настоящему времени опубликовано несколько монографий по теории вейвлетов (И. Добеши, М. Фрейзер, К. Чуй). Классиками теории вейвлетов являются И. Мейер и И. Добеши.

Одним из способов построения вейвлетных базисов является лифтинговая схема, предложенная В. Свелденсом. Лифтинг означает изменение, «приподнимание» низкочастотной составляющей, несущей основную информацию об исходных данных. Величина изменения зависит от вейвлетной составляющей и управляющей функции. Отметим преимущества лифтинговой схемы. Во-первых, за счёт наличия управляющей функции можно влиять на свойства получаемых вейвлетов. Во-вторых, в алгоритме, реализующем лифтин-говую схему разложения функции по вейвлетному базису, все вычисления проводятся «на месте», в одном массиве. В-третьих, лифтинговая схема допускает обращение. Примером применения лифтинговой схемы может служить построение интерполяционных вейвлетов, введённых Донохо.

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

Дискретный гармонический анализ обязан своим становлением открытию в 1965 году быстрого преобразования Фурье (БПФ). К середине 1990-х годов было осознано, что вычислительная схема БПФ связана с построением в пространстве сигналов рекуррентной последовательности ортогональных базисов, имеющих блочную структуру. Это позволило, в частности, сформировать систему вейвлетных базисов (вейвлет-пакет), коэффициенты разложений по которым определяются в процессе вычисления дискретного преобразования Фурье. Разработан также параметрический вариант БПФ.

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

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

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

Кроме разложений элементов пространства по базисам, в дискретном анализе изучаются разложения по фреймам. Фреймы были введены в 1952 году Даффином и Шеффером, однако активное развитие теории фреймов началось лишь после выхода в 1986 году статьи Добешй, Гроссмана и Мейера. К настоящему времени на эту тему опубликованы несколько монографий (О. Кристенсен, Д. Хан и Д. Ларсон) и обзорных статей (П. Казацца, Е. Ковачевич, А. Чебира).

1Желудев В. А., Певный А. Б. Биортогоналъные вейвлетные схемы, основанные на интерполяции дискретными сплайнами // Жури, вычисл. мат. и матем. физ. 2001. Т. 41. №4. С. 537-548.

С\

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

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

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

Также представляет интерес построение фреймов с конкретными свойствами: например, с заданными нормами элементов и заданной матрицей фрейма.

Задача восстановления исходного вектора по его фреймовым коэффициентам потребовала введения понятия двойственных фреймов, среди которых на основе экстремального свойства выделяется канонический двойственный фрейм.

; Фреймы являются одним из важных инструментов цифровой обработки сигналов.

Цель работы.

1) Детальное изучение лифтинговых преобразований дискретных периодических сигналов с точки зрения дискретного гармонического анализа.

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

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

4) Получение быстрых алгоритмов вейвлетных разложений.

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

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

1) Детально разработана теория лифтинговых преобразований в пространстве дискретных периодических сигналов.

2) Изучено влияние управляющих функций на свойства лифтинговых базисов. Найден способ выражения всех элементов лифтингового базиса через базисные функции первого уровня.

3) Исследованы системы векторов специального вида, в которых каждый следующий вектор получается умножением предыдущего на унитарную матрицу. Установлен критерий, когда такая система является жёстким фреймом. Указан способ преобразования системы специального вида в обобщённый гармонический фрейм.

2 Casazza Р. G., Kovaöeviö J. Uniform tight frames with erasures // Adv. Comput. Math. 2003. V. 18. No. 2-4. P. 387-430.

; 4) Выяснены условия, при которых система векторов специального вида является циклическим фреймом. Установлено циклическое свойство фрейма Мерседес-Бенц в п-мерном пространстве.

5) Разработан алгоритм построения фрейма по заданной матрице фрейма и заданным нормам его элементов.

6) Дан детальный анализ методов факторизации полифазных матриц.

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

Апробация работы. По результатам диссертации были сделаны доклады на следующих научных конференциях и семинарах:

• Международная научная конференция «Вейвлеты и приложения» (Санкт-Петербург, 14-20 июня 2009 г.);

• семинар кафедры вычислительной математики математико-механического факультета СПбГУ;

• семинар кафедры исследования операций математико-механического факультета СПбГУ;

• семинар по дискретному гармоническому анализу и геометрическому моделированию (БНА & САвО).

Публикации. По теме диссертации опубликовано пять работ [1-5], перечисленных в конце автореферата. Статьи [1,2] опубликованы в изданиях, входящих в перечень ВАК.

Работы [1,3-5] написаны в соавторстве. В статье [1] В. Н. Малозёмову принадлежит анализ случая ортогональности лифтинговых базисов некоторого уровня. Кроме того, В. Н. Малозёмов предложил некоторые идеи относительно свойств лифтинговых базисов. Реализация идей принадлежит диссертанту. В статье [3] В. Н. Малозёмову принадлежит описание множества управляющих функций, А. Б. Певный внёс некоторые предложения относительно свойств базисов лифтинговых разложений. Детальная реализация идей осуществлена диссертантом. В статье [4] В. Н. Малозёмов предложил упрощение доказательств. Диссертанту принадлежит вывод рекуррентного соотношения для унитарной матрицы и вычисление спектра этой матрицы. В работе [5] В. Н. Малозёмову принадлежит общая постановка задачи и описание матрицы вращений в алгоритме построения фрейма с заданной матрицей фрейма и заданными нормами векторов. Обоснования осуществлены диссертантом.

Структура и объем работы. Диссертация состоит из введения, 2 глав, разбитых на 16 параграфов, списка литературы и одного приложения. Объём диссертации — 133 страницы. Список литературы насчитывает 51 наименование. В диссертации имеется 8 рисунков.

Основные обозначения

С.у — пространство сигналов (комплекснозначных ^-периодических функций целочисленного аргумента, х = ] 6 2);

ын ~ ехр(27гг/ЛГ) — корень степени N из единицы;

Fn — дискретное преобразование Фурье (ДПФ) порядка N, сопоставляющее сигналу х сигнал X = Fn(х) с отсчётами

N-1

X(k) = 1£x(j)urfj, fc'eZ; j=о

F^1 — обратное ДПФ, действующее по формуле

о

In — единичная матрица порядка п.

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

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

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

■ В § 2 вводится лифтинговое преобразование сигнала в спектральной форме. Пусть ш, г — натуральные числа. Пусть сигнал г принадлежит пространству Сдг при N = 2т. Имея в виду дальнейшее развитие событий, введём обозначения

N0 = N, Ni= т, е0 = z.

Лифтинговое преобразование сигнала г осуществляется в три этапа.

I (Split). Расщепим сигнал во на два сигнала

ё1(1) = е0(21), Ml) = eo(2Z + 1), ¿60:^-1.

Обозначим Ei = (ei), Dj = (di).

II (Predict). Вычислим приближённые значения ¿¡(l) с помощью дискретного периодического сплайна S порядка г, определяемого интерполяционными условиями

S(2l) = e1(l), leO'.Ni-l.

Положим <70(/) = 5(2/ + 1), I 6 0 : ЛГ, - 1. Разность

<Щ = <h(l) - <7О(0, I € 0 -. Nx - 1,

вообще говоря, мала. Для спектра этой разности справедлива формула

Di(k) = Di(k) - u>kNaUx(k) Ei(k), keO-.Ni-l.

Здесь

II НА - и с п • N - 1

III(Ы{Ипд). Обновим сигнал ё\. Для этого введём сигнал е\, спектр которого Е\ = Гн, (в!) определим так:

Е1{к) = Ё1{к) + Ш ш^Б^к), ке 0:^,-1. (1)

Здесь ^(к) — произвольный Ар-псриодический сигнал (управляющая функция), удовлетворяющий условию

Р\(к + = —@\{к), к 6 0:М-1.

Ясно, что правая часть (1) является Л^-периодическим сигналом.

Пара {Е\,В\) называется лифтинговым преобразованием сигнала г в спектральной форме. Спектр Е1 содержит основную информацию о спектре Е0 = .?лг0(ео) сигнала г, а спектр — детали.

В § 3 вводится многоуровневое лифтинговое преобразование сигнала. Будем считать, что N = 2я. Обозначим ЛГ„ = ЛГ/2", и = 0,1,..., я. Это обозначение согласовано с обозначениями До, М, введёнными выше. Отметим также, что Лг„ = 1.

Ранее было описано лифтинговое преобразование Ео —> (£1,1)1). Это преобразование можно продолжить:

£1-(£2,Г>2), Е2->{Е3,03)..... ->(Е„ и,)-

Укажем соответствующие формулы. Положим при к е 0 : — 1

пп, (С° '^-("й*

^(«■^♦(«ЬзЙгГ

Здесь /ЗДА.') — произвольная -периодическая функция, удовлетворяющая условию

+ ЛУ = -Д,(£), кеО: N„-1. В § 3 доказывается следующее утверждение: при к 6 0 : Л^ — 1 справедливы равенства Е„[к) = А [МЛ) £„_!(*:) + Л„(А; + ЛУ Е^{к + Ж*) = | &(*) Я-Л*) + + ЛГ„) Е^(к + ЛГ„)].

Набор спектров Д,, ..., В\) называется полным лифтинговым преобразованием сигнала г. Отметим, что Е3 и Ц, — это числа.

По полному лифтинговому преобразованию (Еа, ..., £>1) легко восстановить

спектр £о исходного сигнала г. Для этого введём два вспомогательных сигнала

А„(*) = 1 + ад, дЛк)=и£_1{ к 60:^-1-1.

Имеем

= м*) ад+&(*) Д.(*0.

Е^(к + Ду = А„(* 4- К) Е„{к) + ди{к + ЛУ Ои(к),

При V = 1 получим Е0 = Г

Формула обращения для лифтингового преобразования приводит к лифтинговому разложению сигнала по вейвлетному базису. Этому вопросу посвящён § 4. Введём обозначения Ни = Л1/12 * * • = /ц/12 • • • /1^-1 д

Ъ = ф„ =

ПРЕДЛОЖЕНИЕ 4.2. Пусть N = 2' и £ е 1 : в. Для любого сигнала г 6 Сц справедливо разложение

№-1 4 №,-1 .

= Е й(*) - 2*) + Е Е <*"(*)М - 2"А), ^ € 2, (2)

к=0 1й=1 к=0

где е( = ^(Е,), 4 =

Формула (2) называется лифтинговым разложением сигнала г. При каждом £ 6 1 : в система сигналов

является базисом в Сдг.

При .£ = в формула (2) называется полным лифтинговым разложением сигнала г. Первая сумма в правой части такого разложения вырождается до одного слагаемого ев(0)(р3(з).

ПРЕДЛОЖЕНИЕ 4.3. Имеет место тождество <р,(]) = 1.

На основании предложений 4.2 и 4.3 заключаем, что полное лифтинговое разложение сигнала 2 € С,\- имеет вид

« N„-1

*СЛ = е.(0) + Е Е <Ь{к) Мз - Г к), з € г. (3)

к=1 4=0

Сигналы = и 6 1 : в, вещественны и чётны, поскольку вещественными и

чётными являются их дискретные преобразования Фурье Ни. Разберёмся с сигналом фи = зависящим от управляющей Л^-периодической функции /3„. Пока что на Д, наложено одно условие

Д,(* + К) = -/?„(£), к е 0 : ЛГ„_1 - 1. (4)

ПРЕДЛОЖЕНИЕ 4.4. Допустим, что наряду с (4) функция Д, обладает следующими свойствами:

Д, вещественна и четна,

т =

Тогда сдвинутый сигнал х„(.?') = ^„у + д„), где д„ = 2"~1, будет вещественным и чётным. При этом

ЛГ-1

Е м) = >=0

ПРЕДЛОЖЕНИЕ 4.5. Если исходный сигнал г(]) — вещественный и выполнены условия предложения 4.4, то все коэффициенты полного лифтингового разложения (3) вещественны.

В § 5 и § 6 вводится двойственное лифтинговое преобразование и соответствующее двойственное лифтинговое разложение сигнала. В двойственном лифтинговом преобразовании используется сплайн-интерполяция по нечётным отсчётам.

В § 7 устанавливается биортогональность базисов прямого и двойственного лифтинго-вых разложений.

Параграф 8 посвящён описанию множества управляющих функций /?ь..., Д, удовлетворяющих условиям предложения 4.4. Напомним, что основным периодом /?„(&) является множество 0 : N„-1 — 1.

Функции /3, и /За_1 определяются однозначно: Д,(0) = /3,(1) = —

Отметим, что 1 (2к) = @,(к) при к = О : 1. Потребуем, чтобы и в общем случае при и в — 2,5 — 3,...,1 выполнялось соотношение

Таким образом, нас интересуют управляющие функции которые наряду с усло-

виями предложения 4.4 удовлетворяют еще и условию (5).

Возьмём функцию ¡Зи(к) при I/ Е 1 : в — 2. Её значения на чётных индексах определены формулой (5). В §8 показывается, что достаточно задать значения Д,(2к + 1) только при к 6 0 : N¡,±2 — 1, тогда функция /?„(&) будет определена на всех нечётных индексах основного периода.

После того как построена функция А (А:), к € 0 : N — 1, остальные управляющие функции Р2(к),. ■■, Ра{к) восстанавливаются с помощью процедуры прореживания (5), которую удобно переписать в виде '

ПРЕДЛОЖЕНИЕ 8.1. Размерность множества функций Д равна N/4 — 1.

Отметим, что функции /3\ из предложения 8.1 полностью определяются своими значениями Ук = /3\(к) при к 6 1 : N2 — 1. Для иллюстрации приведём вид Р\(к) на основном периоде при N = 16:

А = У1,2/2, уз, о, -уз, -г/2, -г/1, -г/ь -г/г, -г/з, о, г/з, уг, г/О-

В качестве ри(к) предлагаются функции

Рв(2к) = 0,+1(к), ке 0:ЛГ„-1.

(5)

Р„+1{к) = Р„{2к), ке 0:ЛГ„-1.

(6)

при А; £ 0 : - 1 и к £ + 1 : ЛГ — 1,

при к = и £ = 3

при к 6 ЛГ„+1 + 1 : ЗЛГ„+1 - 1;

= &(*) = и„(к)/(1 + С/„2(/с)), А: 6 0 : ЛГ^ - 1.

Они обладают всеми свойствами, отмеченными в пункте 8.1, включая (5). На рисунках 1, 2, 3 изображены функции &\{к) указанного вида при г = 2 и Л' = 32.

Рис. 1. График функции ^(к) вида (7)

Рис. 2. График функции 0\{к) = | и^к)

Рис. 3. График функции &(*) = их{к)1{\ + ИЦк))

В § 9 изучаются свойства базисных функций лифтинговых разложений. Пусть ^-периодическая функция Р\{к) вещественна, чётна, в нуле равна ^ и сдвиг аргумента на И\ лишь меняет ее знак на противоположный. Пусть остальные управляющие функции /%(&),.. ■, /За(к) строятся с помощью прореживания по правилу (6). При этих предположениях исследуем некоторые свойства базисных функций вейвлетного разложения (2).

ПРЕДЛОЖЕНИЕ 9.2. При всех и е 1: я — 1 справедливы тождества

N-1

1=0

Ф»+1(Л = 1£,¥>1и-21)'ФА1), зея- (9)

;=о

СЛЕДСТВИЕ. Задание <р1, фг определяет 1р„, ф„ для всех уровней V.

Рекуррентные соотношения, аналогичные (8), (9), имеют место и для базисных сигналов двойственных лифтинговых разложений.

Предположим, что управляющая функция Д, удовлетворяет условию (4) и Д(0) = Тогда справедливы следующие утверждения.

ПРЕДЛОЖЕНИЕ 9.5. При всех ) е 0 : N - 1

ПРЕДЛОЖЕНИЕ 9.6. При всех V € 1 : я верно равенство

N-1 7=0

ПРЕДЛОЖЕНИЕ 9.7. При V е 1: -я верны равенства

Я/2-1 N12-1

£ Ч>№) = 2"-1, у„(2д + 1) = 7Г\

5=0 9=0

Если же сигналы /32, ■ •., Д, получаются из А с помощью прореживания, то справедливы следующие равенства: при всех и € 1 : в

N/2-1 Ы/ 2-1

£ 2?) = 0, £ ^(2? + 1) = 0. 9=0 ?=0

Вторая глава диссертации посвящена конечномерным фреймам. В § 10 приводятся эквивалентные определения фреймов и жёстких фреймов. Начнём с общего определения конечномерных фреймов.

Ненулевые векторы ¡р^,^,..., <рт-\ из С" при т ^ п образуют фрейм, если их линейная оболочка совпадает с С,

Обозначим через Ф матрицу со столбцами <р\,...,<рт-\.

ПРЕДЛОЖЕНИЕ 10.1. Система {фк}™=о является фреймом в С" тогда и только тогда, когда эрмитова матрица 5 = ФФ* положительно определена. Матрицу 5 называют матрицей фрейма. Напомним определение жёсткого фрейма.

Жёстким фреймом в С" называется набор ненулевых векторов {¡ро, ц>\,..., Ч>т-\}, такой, что при некотором А > 0 (константа фрейма) соответствующая матрица фрейма имеет вид

■.)8 = А1Я. (10)

Приведём два эквивалентных определения жёсткого фрейма.

ПРЕДЛОЖЕНИЕ 10.3. Система {<Рк}™=о1 является жёстким фреймом в С" с константой А > 0 тогда и только тогда, когда любой вектор х е С" допускает представление

т-1

к=0

ПРЕДЛОЖЕНИЕ 10.4. Система {(р*}]^1 является жёстким фреймом в С" с константой А > 0 тогда и только тогда, когда верно соотношение

т-1

= Л|И|2 ЧхеС.

ь=о

Константа фрейма А необходимо равна такой величине:

ш-1 к=0

Существует ещё одно эквивалентное определение жёсткого фрейма.

ПРЕДЛОЖЕНИЕ 10.5. Система ненулевых векторов {(ро, <Р1,..., Рт-1} из С при т ^ п образует жёсткий фрейм тогда и только тогда, когда

т-1 ет~ 1 ч 2

М=о 1с=0 '

В К2 жёсткий фрейм образуют единичные векторы

<s-.fr')'

(верхний индекс указывает на размерность вектора). Этот жёсткий фрейм называется фреймом Мерседес-Бенц (см. рисунок 4).

%

Аналогичные фреймы были построены в К" при любом п ^ 2 (А. Б. Певный). Приведём соответствующие формулы. Зафиксируем некоторое п> 2. Допустим, что жёсткий фрейм {b"~í}J1=1 в К"-1 уже построен. Фрейм {6"}™^/ определяется конструктивно. Положим 6^+1 = (0,...,0,1)ти

ПРЕДЛОЖЕНИЕ 10.7. Система векторов {Ьу образует жёсткий фрейм и I" с константой А = 1 +

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

Пусть т > п > 1. Возьмём комплексное число с, |с| = 1, и обозначим через сьс2,..., Сп попарно различные корни т-й степени из с. Возьмём также п комплексных чисел 6Ь Ь2, • • •, Ь„, по модулю равных единице. Векторы

М) = Ь^ , jel:n, к е 0 : т - 1,

образуют обобщённый гармонический фрейм. В частности, ^оО) = 3 £ 1 : п. Ясно, что ||0;ь|| = 1 при всех к е 0 : т - 1.

ПРЕДЛОЖЕНИЕ 11.1. Обобщённый гармонический фрейм {фо,Ф1, ■ ■ -,Фт-1} является жёстким фреймом с константой А = —.

Пусть по-прежнему m > п > 1. Возьмём унитарную матрицу U порядка п, единичный вектор <ро ё С" и построим последовательность единичных векторов

'Pk-Uipk-i, fc=l,...,m-l.

Обозначим Ф = {(/¡о,Уь<Pm-l}-

Запишем спектральное разложение унитарной матрицы U:

U = PAP",

где Р — матрица, столбцами которой являются ортонормированные собственные векторы РьРг, ■ • • ,Рп матрицы U, и Л — диагональная матрица, Л = diag(Ab Л2,..., А„), с диагональными элементами, по модулю равными единице. Систему векторов

& = fc60:m-l, (11)

обозначим через Ф.

ТЕОРЕМА 11.1. Если Ф — жёсткий фрейм, то Ф — обобщённый гармонический фрейм.

Условие жёсткости фрейма Ф в теореме 11.1 можно заменить условиями на унитарную матрицу U и начальный вектор tp0.

ТЕОРЕМА 11.2. Система векторов Ф вида (11) является обобщённым гармоническим фреймом тогда и только тогда, когда

(а) собственные числа А^Аг, ...,АЧ матрицы U суть попарно различные корни т-й степени из некоторого числа с £ С, |с] = 1;

{ß) |(Vo>Pj)| = -jz при всех j 6 1 : п.

В § 12 устанавливается критерий, когда система векторов специального вида образует жёсткий фрейм. Пусть U — унитарная матрица порядка п с собственными числами Аг,...,Ап; по модулю равными единице, и соответствующими ортонормированными собственными векторами pi,...,p„. Возьмём единичный вектор (р0 6 С™ и построим при т ^ п систему векторов

(12)

Когда система (12) будет жёстким фреймом?

ТЕОРЕМА 12.1. Для того чтобы система (12) была жёстким фреймом, необходимо и достаточно, чтобы выполнялись два условия:

(а) собственные числа Аь..., А„ матрицы U суть попарно различные корни степени т из некоторого числа с 6 С, |с| = 1;

(ß) |(vo>Pj>| = -fe при всех j е 1 : п.

Теперь зададимся вопросом, когда система векторов вида (12) образует фрейм.

ТЕОРЕМА 12.2. Для того чтобы система (12) была фреймом в С™, необходимо и достаточно, чтобы выполнялись два условия:

(а) собственные числа Aj,... ,АП матрицы U попарно различны;

(ß) |{Vo.Pj)| ^ 0 при всехj el:n.

Отметим, что условия (а) и (0) теоремы 12.2 не зависят от т.

В § 13 указывается, когда система специального вида является циклическим фреймом. Нормированный жёсткий фрейм {<ро,¡pi,...,<Pm-i} в С" при т^п назовём циклическим с константой с 6 С, |с] = 1, если выполняется соотношение

(Vfc+bVs+i) = (<Pk,Vs), fc,s € 0 : m — 1, (13)

где y>m = су0.

ТЕОРЕМА 13.1. Для того чтобы система векторов {<р0, <Р\, ■ ■ •, fm-i} из С" при m > п была циклическим с константой с S С, |с| = 1, нормированным жёстким фреймом, необходимо и достаточно, чтобы нашлась унитарная матрица U порядка п, такая, что

<рк = ик<р0, к € 1 : m - 1,

причём все собственные числа Л],..., Л„ матрицы U суть попарно различные корни степени m из с, а соответствующие ортонормированные собственные векторы pi,... ,рп удовлетворяют условию

= j € 1 : п. (14)

Оказывается, Что фрейм Мерседес-Бенц в n-мерном пространстве также можно представить как жёсткий фрейм специального вида. В §14 устанавливается простое рекуррентное соотношение для соответствующей унитарной матрицы, которое, в частности, позволяет вычислить спектр этой матрицы.

Введём квадратную матрицу Un порядка п с помощью рекуррентного соотношения

К = И];

uk =

' k-1 k-1 1 k-l ,.fc-l

U1 1 - • •, uk-2 ' k 1 ' k uk-l

0 0 V^î -I

O, ..., U, k , k

fc = 2,..., n,

где и* 1 — j-Й столбец матрицы 11к-ь Как и ранее, через обозначаем фрейм Мер-

седес-Бенц в пространстве К". :

ТЕОРЕМА 14.1. Справедливы формулы

и„Ь] = Ь]+1, ¿€1:п; ипЬ^+1=Ь1. (15)

Именно это имеется в виду под циклическим свойством .фрейма Мерседес-Бенц. Выясним свойства матрицы Ч„ при п ^ 2. .

ТЕОРЕМА 14.2. Матрица ип — ортогональная. Её собственными числами являются Чи-пЧи-И"

Параграф 15 посвящён анализу следующей задачи: как связаны собственные числа матрицы фрейма и нормы его элементов? Описывается алгоритм построения фрейма с заданной матрицей фрейма и заданными нормами элементов.

Рассмотрим фрейм в пространстве С" и канонический двойственный фрейм. С произвольным двойственным фреймом {ф\, • • • ,фт} свяжем величину

ТП

Р = ЕМ2-

3=1

В § 16 доказана следующая

ТЕОРЕМА 16.1. Канонический двойственный фрейм является единственным двойственным фреймом, на котором величина Р достигает наименьшего значения.

В диссертационной работе имеется приложение, посвящённое факторизации полифазных матриц. Полифазная матрица сопоставляется паре полиномов Лорана, которые соответствуют фильтрам нижних и верхних частот. Быстрый алгоритм вейвлетного разложения получается при факторизации полифазной матрицы. В. Свелденс и И. Добеши предложили метод факторизации, основанный на алгоритме Евклида для полиномов Лорана. Деление с остатком полиномов Лорана неединственно. Это позволяет получать различные варианты факторизации полифазной матрицы и выбирать среди них наиболее простой вариант. В приложении проводится детальный анализ методов факторизации полифазных матриц. В качестве одного из примеров рассматривается факторизация полифазной матрицы, соответствующей паре фильтров (9-7).

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

1. Малоземов В. Н., Соловьева Н. А. Параметрические лифтинговые схемы вейвлетных разложений // Проблемы матем. анализа. Вып. 42. 2009. С. 15-41 (статья переведена на англ. язык: Journal of Math. Sciences. 2009. V. 162. No. 3. P. 319-347).

2. Соловьева H. А. О жестких фреймах специального вида // Вестник СПбГУ. Сер. 1. 2009. Вып. 3. С. 79-85.

Другие публикации:

3. Малоземов В. Н., Певный А. Б., Селянинова (Соловьева) Н. А. Прямая лифтинговая схема // Вестник Сыктывкарского ун-та. Сер. 1. Вып. 6. 2006. С. 95-110.

4. Малоземов В. Н., Соловьева Н. А. Циклическое свойство фрейма Мерседес-Бенц Ц Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2009-10. 6 с. (http://www.mathsoc.spb.rU/preprint/2009/index.html#10)

5. Малоземов В. Н., Соловьева Н. А. О матрице фрейма // Вестник Сыктывкарского ун-та. Сер. 1. Вып. 10. 2009. С. 75-86.

Подписано к печати 16.06.10. Формат 60 х84 1/16 . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ л. 1,0. Тираж 100 экз. Заказ 4841 Отпечатано в Отделе оперативной полиграфии Химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-40-43,428-69-19

Введение.

Глава I. Вейвлеты в дискретном гармоническом анализе.

§1. Предварительные сведения.

§2. Лифтинговое преобразование сигнала. Формула обращения.

§3. Многоуровневое лифтинговое преобразование.

§ 4. Лифтинговые разложения сигнала.

§5. Двойственное лифтинговое преобразование.

Формула обращения.

§6. Двойственные лифтинговые разложения сигнала.

§ 7. Биортогональность прямого и двойственного базисов.

§ 8. Описание множества управляющих функций.

§ 9. Свойства базисных функций.

Глава II. Конечномерные фреймы.

§ 10. Эквивалентные определения жёстких фреймов.

§11. Обобщённые гармонические фреймы.G

§ 12. Жёсткие фреймы специального вида.

§ 13. Циклические фреймы.

§ 14. Циклическое свойство фрейма Мерседес-Беиц.

§ 15. Матрица фрейма.

§ 16. Двойственные фреймы.

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

Общепринятый базис Фурье хорошо выделяет частоты, но не даёт информации о резких и коротких всплесках и вообще о локальном поведении функции. Желательно, чтобы элементы базиса были лучше локализованы по времени. Вейвлетные базисы удовлетворяют такому требованию. Часто накладываются и дополнительные условия, например, ортогональность базиса, компактность носителей вейвлетов и т. д.

Теория вейвлетов начала активно развиваться в 80-90-е годы двадцатого века. К настоящему времени опубликовано несколько монографий по теории вейвлетов, в том числе [2, 32, 33]. Работа [32] содержит изложение теории вейвлетов с точки зрения линейной алгебры. Классиками теории вейвлетов являются И. Мейер [48] и И. Добеши [2].

Одним из способов построения вейвлетных базисов является лифтии-говая схема, предложенная В. Свелденсом [49 51]. Лифтинг означает изменение, «приподнимание» низкочастотной составляющей, несущей основную информацию об исходных данных. Величина изменения зависит от вейвлетной составляющей pi управляющей функции. Отметим преимущества лифтинговой схемы. Во-первых, за счёт наличия управляющей функции можно влиять на свойства получаемых вейвлетов. Во-вторых, в алгоритме, реализующем лифтинговую схему разложения функции по вейвлетному базису, все вычисления проводятся «на месте», в одном массиве. В-третьих, лифтинговая схема допускает обращение. Примером применения лифтинговой схемы может служить построение интерполяционных вейвлетов, введённых Донохо [42].

Лифтинговая схема была предложена также в случае дискретных периодических сигналов [4] и стала одним из инструментов дискретного гармонического анализа. Основы дискретного гармонического анализа изложены в [8].

Дискретный гармонический анализ обязан своим становлением открытию в 1965 году быстрого преобразования Фурье (БПФ) [1, 5, 39]. К середине 1990-х годов было осознано, что вычислительная схема БПФ связана с построением в пространстве сигналов рекуррентной последовательности ортогональных базисов, имеющих блочную структуру [25]. Это позволило, в частности, сформировать систему вейвлетных базисов (вейвлет-пакет), коэффициенты разложений по которым определяются в процессе вычисления дискретного преобразования Фурье [9, 26]. Разработан также параметрический вариант БПФ [16].

Важную роль в дискретном гармоническом анализе играют дискретные периодические сплайны [10, 11]. Сплайн-интерполяция используется при описании лифтинговой схемы.

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

Вейвлеты активно используются во многих областях вычислительной математики, в том числе в цифровой обработке сигналов [6].

Кроме разложений элементов пространства по базисам, в дискретном анализе изучаются разложения по фреймам. Фреймы были введены в 1952 году Даффином и Шеффером [43], однако активное развитие теории фреймов началось лишь после выхода в 1986 году статьи Добеши, Гроссмана и Мейера [40].

Введение в теорию фреймов содержится, например, в книге Добеши [2]. К настоящему времени на эту тему опубликованы несколько монографий, в том числе [38, 45], и обзорных статей [34, 46, 47]. Работа [47] посвящена приложениям фреймов в цифровой обработке сигналов.

Обратимся к фреймам в конечномерных пространствах. Конечномерный фрейм — избыточная система векторов, порождающая всё пространство. Именно свойство избыточности позволяет восстановить исходный сигнал, если при передаче по сети некоторые из коэффициентов его разложения по фрейму были потеряны [36, 44].

Понятие фрейма очень широко — фреймом является любая система векторов, содержащая базис. Основной интерес представляют фреймы, близкие в некотором смысле к ортогональным базисам. Такие фреймы называются жёсткими [40]. Именно жёсткие фреймы оказываются наиболее удобными во многих прикладных задачах [44].

Среди жёстких фреймов выделяют отдельные классы, важные с точки зрения приложений: гармонические и обобщённые гармонические фреймы, равноугольные жёсткие фреймы, жёсткие фреймы, обладающие групповой структурой. Способы построения и свойства этих фреймов изучаются в [14, 36].

Также представляет интерес построение фреймов с конкретными свойствами: например, с заданными нормами элементов и заданной матрицей фрейма [36, 37].

Задача восстановления исходного век гора по его фреймовым коэффициентам потребовала введения понятия двойственных фреймов, среди которых на основе экстремального свойства выделяется канонический двойственный фрейм [2].

Фреймы являются одним из важных инструментов цифровой обработки сигналов [6].

Целью диссертационной работы является:

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

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

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

4- Получение быстрых алгоритмов вейвлетных разложений.

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

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

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

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

Лифтинговое преобразование можно продолжить. Управляющие функции на каждом уровне выбираются независимо. Многоуровневому лифтинговому преобразования сигнала посвящён третий параграф.

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

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

В седьмом параграфе устанавливается биортогональность базисов прямого и двойственного лифтинговых разложений.

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

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

Вторая глава посвящена конечномерным фреймам.

В десятом параграфе приводятся эквивалентные определения фреймов и жёстких фреймов. В качестве примера жёсткого фрейма рассматривается фрейм Мерседес-Бенц в n-мерном пространстве [12]. Вводится понятие матрицы Мерседес-Бенц.

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

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

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

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

Пятнадцатый параграф посвящён анализу следующей задачи: как связаны собственные числа матрицы фрейма и нормы его элементов? Описывается алгоритм построения фрейма с заданной матрицей фрейма и заданными нормами элементов.

В последнем, шестнадцатом, параграфе вводятся понятия двойственного фрейма и канонического двойственного фрейма. Переформулируется известное (см. [2]) экстремальное свойство канонического двойственного фрейма. Кроме того, напоминается способ преобразования любого фрейма во фрейм Парсеваля — жёсткий фрейм, чей канонический двойственный фрейм совпадает с ним самим.

В диссертационной работе имеется приложение, посвящёиное факторизации полифазных матриц. Полифазная матрица сопоставляется паре полиномов Лорана, которые соответствуют фильтрам нижних и верхних частот. Быстрый алгоритм вейвлетного разложения получается при факторизации полифазной матрицы. В [41] предлагается метод факторизации, основанный на алгоритме Евклида для полиномов Лорана. Деление с остатком полиномов Лорана неединственно. Это позволяет получать различные варианты факторизации полифазной матрицы и выбирать среди них наиболее простой вариант. В приложении проводится детальный анализ методов факторизации полифазных матриц. В качестве одного из примеров рассматривается факторизация полифазной матрицы, соответствующей паре фильтров (9-7).

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

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

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

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

4. Выяснены условия, при которых система векторов специального вида, является циклическим фреймом. Установлено циклическое свойство фрейма Мерседес-Бепц в n-мерном пространстве.

5. Разработан алгоритм построения фрейма по заданной матрице фрейма и заданным нормам его элементов.

6. Дан детальный анализ методов факторизации полифазных матриц.

Основные результаты опубликованы в работах [15, 19, 21, 23, 31]. Предварительные результаты обсуждались на семинаре «Дискретный гармонический анализ и геометрическое моделирование» ([17, 18, 20, 22, 24, 28, 29]). По результатам работы были сделаны доклады па международной научной конференции «Вейвлеты и приложения» [30] и на семинарах кафедры вычислительной математики и кафедры исследования операций математико-механического факультета СПбГУ.

Автор глубоко признателен своему научному руководителю профессору В. Н. Малозёмову за постановку интересных задач, обсуждение полученных результатов и постоянное внимание в процессе работы над диссертацией. Также автор благодарен профессору А. Б. Певному за внимание к работе и поддержку, О. В. Просекову и М. И. Григорьеву за советы по оформлению текстов, формул и рисунков в издательской системе

Основные обозначения

Сn — пространство сигналов (комплекснозначных iV-периодических функций целочисленного аргумента, х = x(j), j Е Z); SnU) — единичный TV-периодический импульс, равный единице, когда j делится на N, и равный нулю в остальных случаях; сом — ехр(27H/N) — корень степени N из единицы;

Tn ~ дискретное преобразование Фурье (ДПФ) порядка iV, сопоставляющее сигналу х сигнал X = J-^(x) с отсчётами

N-1 i=о

Т^1 ~ обратное ДПФ, действующее по формуле

N—1 j=о и — с * х — циклическая свёртка сигналов с их (сигнал с отсчётами

N-1 u(k) = J2c(j)<k-j), keZy, j=о

In - единичная матрица порядка п.

1. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989. 448 с.

2. Добеши И. Десять лекций по вейвлетам. Пер. с англ. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 464 с.

3. Дурягин А. М. Максимальная избыточность вещественных гармонических фреймов // Семинар но дискретному гармоническому анализу и геометрическому моделированию (DHA& CAGD). Избранные доклады. 28 марта 2008 г. 7 с.http://dha.spb.ru/reps08.shtml#0328).

4. Желудев В. А., Певный А. Б. Биортогональные вейвлетные схемы, основанные на интерполяции дискретными сплайналш // Журн. вычисл. мат. и матем. физ. 2001. Т. 41. №4. С. 537-548.

5. Макклеллан Дж. X., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983. 264 с.

6. Малла С. Вэйвлеты в обработке сигналов. Пер. с англ. М.: Мир, 2005. 671 с.

7. Малоземов В. Н. Линейная алгебра без определителей. Квадратичная функция. СПб.: Изд-во СПбГУ, 1997. 80 с.

8. Малоземов В. Н., Машарский С. М. Основы дискретного гармонического анализа. Части 1-3. СПб.: НИИММ СПбГУ, 2003. 288 с.

9. Малоземов В. Н., Машарский С. М., Формула Глассмана, быстрое преобразование Фурье и вейлетные разложения // Труды Санкт-Петербургского матем. об-ва. 2001. Т. 9. С. 97-119.

10. Малоземов В. Н., Певный А. Б. Дискретные периодические В-сплай-ны // Вестник СПбГУ. Сер. 1. 1997. Вып. 4 (№22). С. 14-19.

11. Малоземов В. Н., Певный А. Б. Дискретные периодические сплайны и их вычислительные применения // Журн. вычисл. мат. и матем. физ. 1998. Т. 38. №8. С. 1235-1246.

12. Малоземов В. Н., Певный А. Б. Фрейм Мерседес-Бенц в п-мерном пространстве // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA&CAGD). Избранные доклады. 16 января 2007 г. 7 с.http://dha.spb.ru/reps07.shtml#0116).

13. Малоземов В. H., Певный А. Б. Четвертое определение жесткого фрейма // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA&CAGD). Избранные доклады. 30 мая 2007 г. 5 с.http://dha.spb.ru/reps07.shtml#0530).

14. Малоземов В. H., Певный А. Б. Равноугольные жесткие фреймы // Проблемы матем. анализа. 2009. Вып. 39. С. 3-25.

15. Малоземов В. Н., Певный А. Б., Селянинова (Соловьева) Н. А. Прямая лифтинговая схема // Вестник Сыктывкарского ун-та. Сер. 1. Вып. 6. 2006. С. 95-110.

16. Малоземов В. Н., Просеков О. В. Параметрические варианты быстрого преобразования Фурье // Доклады РАН. 2008. Т. 421. № 5. С. 593-595.

17. Малоземов В. Н., Селянинова (Соловьева) Н. А. Прямая лифтинговая, схема // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA&CAGD). Избранные доклады. 26 апреля 2005 г. 10 с. (http://dha.spb.ni/reps05.shtml#0426).

18. Малоземов В. Н., Селянинова (Соловьева) Н. А. Двойственная лиф-тинговая схема // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA&CAGD). Избранные доклады. 14 марта 2006 г. 10 с.http: / / dha.spb.ru/reps06.shtml#0314).

19. Малоземов В. Н., Соловьева Н. А. Параметрические лифтинговые схемы вейвлетных разлоэюений // Проблемы матем. анализа. Вып. 42. 2009. С. 15-41.

20. Малоземов В. И., Соловьева Н. А. Двойственные фреймы // Семинар но дискретному гармоническому анализу pi геометрическому моделированию (DHA& CAGD). Избранные доклады. 21 августа 2007 г. 4 с. (http://dha.spb.ru/reps07.shtml#0821).

21. Малоземов В. Н., Соловьева Н. А. Циклическое свойство фрейлш Мерседес-Бенц // Электронный архив препринтов С.-Петербургского матем. общества. Препринт 2009-10. 6 с.http://www.mathsoc.spb.ru/preprint/2009/index.html#10)

22. Малоземов В. H., Соловьева Н. А. О матрице фрейма // Вестник Сыктывкарского ун-та. Сер. 1. Вып. 10. 2009. С. 75-86.

23. Малоземов В. Н., Соловьева Н. А. Факторизация полифазных матриц II Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA&CAGD). Избранные доклады.31 октября 2009 г. 7 с.http://dha.spb.ru/reps09.shtml#1031).

24. Малоземов В. H., Третьяков А. А. Новый подход к алгоритму Кули-Тъюки // Вестник СПбГУ. Сер. 1. 1997. Вып. 3 (№15). С. 57-60.

25. Малоземов В. Н., Третьяков А. А. Алгоритм Кули-Тъюки и дискретное преобразование Хаара j j Вестник СПбГУ. Сер. 1. 1998. Вып. 3 (№15). С. 31-34.

26. Певный А. Б. Максимальная избыточность гармонических фреймов // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA&CAGD). Избранные доклады. 28 марта 2007 г. 4 с.http://dha.spb.ru/reps07.shtml#0328).

27. Соловьева H. А. Обобщенные гармонические фреймы // Семинар по дискретному гармоническому анализу и геометрическому моделированию (DHA&CAGD). Избранные доклады. 16 апреля 2008 г. 9 с. (http://dha. spb.ru/reps08. shtml#0416).

28. SolovjovaN. A. Tight frames of special form. In: International Conference Wavelets and Applications. June 14-20. 2009, St. Petersburg, Russia. Abstracts. Санкт-Петербург 2009. С. 57-58.

29. Соловьева H. А. О oicecrriKux фреймах специального вида // Вестник СПбГУ. Сер. 1. 2009. Вып. 3. С. 79-85.113

30. Фрейзер М. Введение в вэйвлеты в свете линейной алгебры. Пер. с англ. М.: БИНОМ, 2007. 487 с.

31. Чуй К. Введение в вейвлеты. Пер. с англ. М.: Мир, 2001. 412 с.

32. Casazza P. G. The art of frame theory // Taiwanese J. Math. 2000. V. 4. No. 2. P. 129-202.

33. Casazza P. G. Custom building finite frames // Contemporary Math. 2004. V. 345. P. 61-86.

34. Casazza P. G., Kovacevic J. Uniform tight frames with erasures // Adv. Comput. Math. 2003. V. 18. No. 2-4. P. 387-430.

35. Casazza P. G., Leon M. T. Frames with a given frame operator. 2002. Preprint. 6 p.

36. Christensen O. Introduction to frames and Riesz bases. Cambridge: MA, Birkhauser, 2002. 468 p.

37. Cooley J. W., Tukey J. W. An algorithm for the machine calculation of complex Fourier series // Math. Comput. 1965. V. 19. No. 90. P. 297-301.

38. Daubechies I., Grossman A., Meyer Y. Painless nonorthogonal expansions // J. Math. Phys. 1986. V. 27. P. 1271-1283.

39. Daubechies I., Sweldens W. Factoring wavelets transforms into lifting steps // J. Fourier Anal. Appl. 1998. Vol. 4. No. 3. P. 247-269.

40. Donoho D. L. Interpolating wavelet transform / Preprint 408, Department of Statistics, Stanford University, 1992. 54 p.

41. Duffin R. J., Schaeffer A. C. A class of nonharmonic Fourier series // Trans. Amer. Math. Soc. 1952. V. 72. No. 4. P. 341-366.

42. Goyal V. К., Kovacevic J., Kelner J. A. Quantized frame expansions with erasures // Journal of Appl. and Comput. Harmonic Analysis. May 2001. V. 10. No. 3. P. 203-233.

43. Han D. and Larson D. R. Frames, bases and group representations / Memoirs AMS American Mathematical Society. 2000. V. 147. No. 697. 110 p.

44. Kovacevic J., Chebira A. Life beyond bases: The advent of frames (Part I) // IEEE Signal Processing Magazine. 2007. V. 24. No. 4. P. 86-104.

45. Kovacevic J., Chebira A. Life beyond bases: The advent of frames (Part II) // IEEE Signal Processing Magazine. 2007. V. 24. No. 5. P. 115-125.

46. Meyer Y. Wavelets and fast numerical algorithms // Handbook of Numerical Analysis. 1997. V. 5. P. 639-713.

47. Sweldens W. The lifting scheme: a custom design construction of biorthogonal wavelets. // Appl. Comput. Harm. Anal. 1996. V. 3. No. 2. P. 186-200.

48. Sweldens W. The lifting scheme: a new philosophy in biorthogonal wavelet constructions. In: Wavelet Applications in Signal and Image Processing III, vol. 2569 of Proceedings of SPIE, 1995. P. 68-79.

49. Sweldens W., Schroder P. Building your own wavelets at home. In: Wavelets in Computer Graphics. 1996. ACM SIGGRAPH Course notes. P. 15-87.