Вейвлеты и фреймы в дискретном анализе тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Соловьева, Наталья Анатольевна

• Соловьева, Наталья Анатольевна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Соловьева, Наталья Анатольевна

Введение.

Глава 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 - единичная матрица порядка п.

Список литературы диссертационного исследования кандидат физико-математических наук Соловьева, Наталья Анатольевна, 2010 год

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.