2

Белорусский государственный университет

Факультет прикладной математики и информатики

Кафедра математической физики

ГРОМОВА МАРИЯ МИХАЙЛОВНА

ОПРЕАТОРЫ В ВЕЙВЛЕТНОМ БАЗИСЕ

Курсовая работа студентки 4 курса

Научный руководитель:

Глушцов Анатолий Ильич

кафедры МФ

кандидат физ.-мат. наук

Минск 2004

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………..………………………………………………………..3

1. МНОГОМАСШТАБНЫЙ АНАЛИЗ И ВЕЙВЛЕТЫ………………...5

2. БЫСТРОЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ….……………………...9

3. ДВУМЕРНЫЕ ВЕЙВЛЕТЫ…………………………………………..12

4. МАТРИЧНЫЕ ОПЕРАЦИИ………………………………………….13

4.1. Матричное умножение………………………………………...13

4.2. Обращение матрицы…………………………………………...16

4.3. Вычисление экспоненты, синуса и косинуса от матрицы.….16

ЛИТЕРАТУРА……………………………………………………………18

ВВЕДЕНИЕ

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

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

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

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

При исследовании же нестационарных сигналов требуется использование некоторых локализованных во времени компактных волн, коэффициенты разложения по которым сохраняют информацию о дрейфе параметров аппроксимируемой функции. Первые попытки построения таких систем функций сводились к сегментированию сигнала на фрагменты ("окна") с применением разложения Фурье для этих фрагментов. Соответствующее преобразование - оконное преобразование Фурье - было предложено в 1946-47 годах Jean Ville и, независимо, Dennis Gabor. В 1950-70-х годах разными авторами было опубликовано много модификаций времени-частотных представлений сигналов.

В конце 70-х инженер-геофизик Морли (Jean Morlet) столкнулся с проблемой анализа сигналов, которые характеризовались высокочастотной компонентой в течение короткого промежутка времени и низкочастотными колебаниями при рассмотрении больших временных масштабов. Оконные преобразования позволяли проанализировать либо высокие частоты в коротком окне времени, либо низкочастотную компоненту, но не оба колебания одновременно. В результате был предложен подход, в котором для различных диапазонов частот использовались временные окна различной длительности. Оконные функции получались в результате растяжения-сжатия и смещения по времени гаусиана. Морли назвал эти базисные функции вейвлетами (wavelets) - компактными волнами. В дальнейшем благодаря работам Мейера (Yves Meyer), Добеши (Ingrid Daubechies), Койфмана (Ronald Coifman), Маллы (Stephane Mallat) и других теория вейвлетов приобрела свое современное состояние.

Среди российских ученых, работавших в области теории вейвлетов, необходимо отметить С.Б. Стечкина, И.Я. Новикова, В.И. Бердышева.

1. МНОГОМАСШТАБНЫЙ АНАЛИЗ И ВЕЙВЛЕТЫ

Определение 1. Многомасштабный анализ (multiresolutional analysis) – разложение гильбертова пространства L²(R^d), d1, в последовательность замкнутых подпространств

, (1.1)

обладающих следующими свойствами:

1. , и полно в L²(R^d),

2. Для любого f L²(R^d), для любого j Z, f(x)V_j тогда и только тогда, когда

f(2x) V_j-1,

3. Для любого f L²(R^d), для любого k Z^d, f(x)V₀ тогда и только тогда, когда f(x-k)V₀,

4. Существует масштабирующая (scaling) функция V₀, что {(x-k)}_kZ^d образует

базис Ритца в V₀.

Для ортонормальных базисов можно переписать свойство 4 в виде:

4’. Существует масштабирующая функция V₀, что {(x-k)}_kZ^d образует ортонормальный базис в V₀.

Определим подпространство W_j как ортогональное дополнение к V_j в V_j-1,

, (1.2)

и представим пространство L²(R^d) в виде прямой суммы

(1.3)

Выбирая масштаб n, можем заменить последовательность (1.1) следующей последовательностью:

(1.4)

и получить

(1.5)

Если имеем конечное число масштабов, то, не нарушая общности, можно положить j=0 и рассматривать

, V₀ L²(R^d) (1.6)

вместо (1.4). В числовой реализации подпространство V₀ конечномерно.

Функция  - так называемая масштабирующая (скейлинг-) функция. С ее помощью можно определить функцию  - вейвлет - такую, что набор {(x-k)}_kZ образует ортонормальный базис в W₀. Тогда

, m=0..M-1. (1.7)

Из свойства 4’ непосредственно следует, что, во-первых, функция  может быть представлена в виде линейной комбинации базисных функций пространства V_-1 . Так как функции {_j,k(x)=2^-j/2(2^-jx-k)}_kZ образуют ортонормальный базис в V_j, то имеем

. (1.8)

Вообще говоря, сумма в выражении (1.8) не обязана быть конечной. Можно переписать (1.8) в виде

, (1.9)

где

, (1.10)

а 2-периодическая функция m₀ определяется следующим образом:

. (1.11)

Во-вторых, ортогональность {(x-k)}_kZ подразумевает, что

(1.12)

и значит

(1.13)

и . (1.14)

Используя (1.9), получаем

(1.15)

и, рассматривая сумму в (1.15) по четным и нечетным индексам, имеем

. (1.16)

Используя 2-периодичность функции m₀ и (1.14), после замены /2 на , получаем необходимое условие

(1.17)

для коэффициентов h_k в (1.11). Заметив, что

(1.18)

и определив функцию  следующим образом:

, (1.19)

где

, k=0,…,L-1 , (1.20)

или преобразование Фурье для 

, (1.21)

где

, (1.22)

можно показать, что при каждом фиксированном масштабе jZ вейвлеты

{_j,k(x)=2^-j/2(2^-jx-k)}_kZ образуют ортонормальный базис пространства W_j.

Равенство (1.17) определяет пару квадратурных зеркальных фильтров (quadrature mirror filters, QMF) H и G, где и . Коэффициенты QMF H и G вычисляются с помощью решения системы алгебраических уравнений. Число L коэффициентов фильтра в (1.11) и (1.22) связано с числом исчезающих моментов М, и всегда четно.

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

4. ОПЕРАТОРЫ

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

Нестандартная форма оператора Т с ядром K(x,y) достигается вычислением следующих выражений:

(4.1)

(4.2)

(4.3)

4.1 Оператор d/dx в вейвлетном базисе

Нестандартные формы некоторых часто используемых операторов могут быть вычислены явно. Построим нестандартную форму оператора d/dx. Матричные элементы , , матриц , , и матрицы , где i, l, j Z для оператора d/dx легко вычисляются как

(4.4)

(4.5)

(4.6)

(4.7)

где

(4.8)

(4.9)

(4.10)