Операторы в вейвлетном базисе
| Примечание | от автора: Криво проставлена нумерация разделов и неправильное содержание. Все остальное - в порядке |
| Загрузить архив: | |
| Файл: ref19515.zip (82kb [zip], Скачиваний: 52) скачать |
Белорусский государственный университет
Факультет прикладной математики и информатики
Кафедра математической физики
ГРОМОВА МАРИЯ МИХАЙЛОВНА
ОПРЕАТОРЫ В ВЕЙВЛЕТНОМ БАЗИСЕ
Курсовая работа студентки 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. Многомасштабный анализ (multiresolutionalanalysis) – разложение гильбертова пространства L2(Rd), d³1, впоследовательность замкнутых подпространств
(1.1)
обладающих следующими свойствами:
1. 
,и 
полно в L2(Rd),
2. Для любого fÎL2(Rd), для любого jÎZ, f(x)ÎVj тогда и только тогда, когда
f(2x) ÎVj-1,
3. Для любого fÎL2(Rd), для любого kÎZd, f(x)ÎV0 тогда и только тогда, когда f(x-k)ÎV0,
4. Существует масштабирующая (scaling) функция jÎV0, что {j(x-k)}kÎZdобразует
базис Ритца в V0.
Для ортонормальных базисов можно переписать свойство 4 в виде:
4’. Существует масштабирующая функция jÎV0, что {j(x-k)}kÎZdобразует ортонормальный базис в V0.
Определим подпространство Wjкак ортогональное дополнение к Vj в Vj-1,
(1.2)
и представим пространство L2(Rd) в виде прямой суммы
(1.3)
Выбирая масштаб n, можем заменить последовательность (1.1) следующей последовательностью:
(1.4)
и получить
(1.5)
Если имеем конечное число масштабов, то, не нарушая общности, можно положить j=0 и рассматривать
V0ÎL2(Rd) (1.6)
вместо (1.4). В числовой реализации подпространство V0 конечномерно.
Функция j - так называемая масштабирующая (скейлинг-) функция. С ее помощью можно определить функцию y - вейвлет - такую, что набор{y(x-k)}kÎZобразует ортонормальный базис в W0. Тогда
m=0..M-1. (1.7)
Из свойства 4’ непосредственно следует, что, во-первых, функция j может быть представлена в виде линейной комбинации базисных функций пространства V-1 . Так как функции{jj,k(x)=2-j/2j(2-jx-k)}kÎZ образуют ортонормальный базис в Vj, то имеем
(1.8)
Вообще говоря, сумма в выражении (1.8) не обязана быть конечной. Можно переписать (1.8) в виде
(1.9)
где
(1.10)
а 2p-периодическая функция m0 определяется следующим образом:
(1.11)
Во-вторых, ортогональность {j(x-k)}kÎZ подразумевает, что
(1.12)
и значит
(1.13)
и
(1.14)
Используя (1.9), получаем
(1.15)
и, рассматривая сумму в (1.15) по четным и нечетным индексам, имеем
(1.16)
Используя 2p-периодичность функции m0 и (1.14), после замены x/2 на x, получаем необходимое условие
(1.17)
для коэффициентов hk в (1.11). Заметив, что
(1.18)
и определив функцию y следующим образом:
(1.19)
где
k=0,…,L-1 , (1.20)
или преобразование Фурье для y
(1.21)
где
(1.22)
можнопоказать, что при каждом фиксированном масштабе jÎZ вейвлеты
{yj,k(x)=2-j/2y(2-jx-k)}kÎZобразуют ортонормальный базис пространства Wj.
Равенство
(1.17) определяет пару квадратурных
зеркальных фильтров (quadrature
mirror filters, QMF) H и G, где 
и 
QMFH и G вычисляются с помощью решения
системы алгебраических уравнений. Число L коэффициентов фильтра в
(1.11) и (1.22) связано с числом исчезающих моментов М, ивсегда четно.
Выбранный фильтр Нполностью определяет функции j и y и, таким образом, многомасштабный анализ. Кроме того, в правильно построенных алгоритмах значения функций j и y почти никогда не вычисляются. Благодаря рекурсивному определению вейвлетного базиса, все операции проводятся с квадратурными зеркальными фильтрами H и G, даже если в них используются величины, связанные с j и y.
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)
(4.11)
Кроме того, используя (1.8)и (1.19), имеем
(4.12)
(4.13)
(4.14)
Таким образом представление d/dxполностью
определяется величинами 
или, другими словами,
отображением d/dxна подпространство V0.
Предложение 4.1.
1. Если существует интеграл (4.11), тогда коэффициенты lÎZв (5.8) удлвлетворяют следующей системе
линейных алгебраических уравнений:
(4.15)
(4.16)
где
(4.17)
2. Если 
а именно с 
и 
Замечание. Если М=1, тогда система (4.15)-(4.16) имеет единственное решение, но
интеграл (4.11) может не быть абсолютно сходящимся. Для базиса Хаара (
мы получаем простейший
конечный дифференциальный оператор 
Замечание 2. Заметим, что
выражения (4.12) и (4.13) для 
и 
(
и
особенно просто: 
Для доказательства Предложения 4.1 можно обратиться к [2].
Для решения
системы (4.15)-(4.16) можно также воспользоваться итерационным алгоритмом. Начать
можно с 
и 
4.2 Оператор dn/dxnв вейвлетном базисе
Так же как и для оператора d/dx, нестандартная форма оператора dn/dxnполностью определяется своим отображением на подпространство V0, т.е. коэффициентами
lÎZ, (4.18)
если интеграл существует.
Предложение
4.2. 1. Если интеграл в выражении (4.18) существует, тогда коэффициенты
lÎZудовлетворяют следующей системе линейных
алгебраических уравнений
(4.19)
(4.20)
где 
дано в формуле (4.17).
2. Пусть M≥ (n+1)/2, где М – число
исчезающих моментов. Если интеграл в (4.18) существует, тогда система
(4.19)-(4.20) имеет единственное решение с конечным числом нулевых
коэффициентов 
для n
(4.21)
(4.22)
(4.23)
а для нечетных n
(4.24)
(4.25)
Замечание 3. Если M≥ (n+1)/2, тогда решение линейной системы в Предложении 2 может существовать, когда интеграл в (4.18) не является абсолютно сходящимся.
Интегральные уравнения второго рода
Линейное интегральное уравнение Фредгольма есть выражение вида
где ядро 
f(x) и
функция в правой части 
и 
Предположим, что {φ1, φ1,…} – ортонормальный базис для 
где коэффициенты Kijвычисляются по формуле
Аналогично функции fи gпредставимы в виде
где коэффициенты fiи giвычисляются по формулам:
i=1,2,…
Интегральное уравнение в этом случае соответствует бесконечной системе уравнений
i=1,2,…
Представление ядра может быть урезано до конечного числа слагаемых, что приводит к представлению интегрального оператора R:
который аппроксимирует K. Тогда интегральное уравнение аппроксимируется системой nуравнений с nнеизвестными:
i=1,2,…,n
ПРИЛОЖЕНИЕ 1
function [a,r]=dif_r(wname)
[LO_D,HI_D,LO_R,HI_R] = wfilters(wname);
% вычисление коэффициентов a2k-1
len=length(LO_D);
a=zeros(len-1,1);
for k=1:len-1;
for i=0:len-2*k;
a(2*k-1)=a(2*k-1)+2*LO_D(i+1)*LO_D(i+2*k);
end;
end;
% вычисление коэффициентов rl
f=zeros(len-2,1);
f(1)=-1/2;
R=zeros(len-2);
for l=len-2:-1:2;
R(l,l)=-1;
if (2*l<=len-2)
R(l,2*l)=2;
end;
for n=1:2:len-1;
if (abs(2*l-n) if ((2*l-n)<0);
R(l,abs(2*l-n))=-a(n)+R(l,abs(2*l-n)); else R(l,2*l-n)=a(n)+R(l,2*l-n); end; end; if (abs(2*l+n) if ((2*l+n)<0);
R(l,abs(2*l+n))=-a(n)+R(l,abs(2*l+n)); else R(l,2*l+n)=a(n)+R(1,2*l+n); end; end; end; end; for
j=1:len-2; R(1,j)=j; end; r=inv(R)*f; ПРИЛОЖЕНИЕ 2 function
[al, bet, gam]=difcoef(wname,N) % извлечение
коэффициентов rl [LO_D,HI_D,LO_R,HI_R]
= wfilters(wname); [a,r]=dif_r(wname); L=length(LO_D); % вычисление значений αl, βl,γl J=length(r):-1:1; R=[-r(J);0;
r]; K=L+1; al=zeros(2*L+1,1); bet=al; gam=al; for
i=-L+1:L+1; for
k=L+1:2*L; for k1=L+1:2*L;
if(((2*i+k-k1+L)
al(i+L)=HI_D(k-L)*HI_D(k1-L)*R(2*i+k-k1+L)+al(i+L);
bet(i+L)=HI_D(k-L)*LO_D(k1-L)*R(2*i+k-k1+L)+bet(i+L);
gam(i+L)=LO_D(k-L)*HI_D(k1-L)*R(2*i+k-k1+L)+gam(i+L); end; end; end; end; ПРИЛОЖЕНИЕ 3 1.Вейвлет Добеши с M=2. 2.
ВейвлетДобешис M=3. r1=-0.7452 r2=0.1452r3=-0.0146r4=-0.0003 3.
ВейвлетДобешис M=4. r1=-0.79300950497055
r2=0.19199897079726r3=-0.03358020705113 r4= 0.00222404967066
r5=0.00017220619000r6=-0.00000084085054 4.
Вейвлет
Добеши с M=5. a7=-0.01235961914130a9=0.00106811523422 r1=-0.82590601185686r2=0.22882018706986r3=-0.05335257193327 r4=0.00746139636621r5=-0.00023923581985r6=-0.00005404730164 r7=-0.00000025241171r8=-0.00000000026960 5.
ВейвлетДобешис M=6. a1=1.22133636474683a3=-0.29079437255810a5=0.08723831176674 a7=-0.02077102661228a9=0.00323104858448a11=-0.00024032592766 r1=-0.85013666156022r2=0.25855294414318
r3=-0.07244058999853 r4=0.01454551104340r5=-0.00158856154379r6=0.00000429689148 r7=0.00001202657519r8=0.00000042069120 r9=-0.00000000289967 r10=0.00000000000070 6.Вейвлет Койфмана с M=2. a7=-0.00724698442340a9=0.00043220193586a11=-0.00002361577240 r1=-0.80177838961957r2=0.20214744976459r3=-0.03943577686925 r4=0.00404789045961r5=-0.00008445623632r6=0.00000255044096 r7=0.00000088836508r8=0.00000000237860r9=-0.00000000002099 r10=0.00000000000000 7.
Симлет
с M=2. a1=1.12499999999971a3=-0.12499999999971 r1=-0.66666666666616 r2=0.08333333333308 8.
Симлет
с M=3. a1=1.17187500000666a3=-0.19531250000432a5=0.02343749999766 9.
Симлет
с M=4. a1=1.19628906249990a3=-0.23925781249985a5=0.04785156249993 a7=-0.00488281249998 r1=-0.79300950497424r2=0.19199897079876r3=-0.03358020705098 r4=0.00222404967071r5=0.00017220619000r6=-0.00000084085054 ПРИЛОЖЕНИЕ 4 1.Вейвлет Добеши с M=2. α-3=-0.00520833333331 β-3 =-0.00139556871057 γ-3=0.01943776462271 α-2=0.04687500000004 β-2=0.02222890204378 γ-2=-0.04027109795592 α-1=0.71874999999873 β-1=-0.03887552924536 γ-1=0.00279113742108 α1=-0.71874999999873 β1=-0.00279113742108 γ1=0.03887552924536 α2=-0.04687500000004 β2=0.04027109795592 γ2=-0.02222890204378 α3=0.00520833333331 β3=-0.01943776462271 γ3=0.00139556871057 2.Вейвлет Добеши с M=3. α-5= -0.00000401327055 β-5 =0.00000042496289 γ-5=-0.00003790058109 α-4=0.00173507063342 β-4=-0.00018594182937 γ-4= 0.01618803080395 α-3= -0.01438088613327 β-3= 0.00249383057321 γ-3= -0.05023776816965 α-2= 0.09779091752885 β-2=-0.02225975249164 γ-2=0.03807446337594 α-1=0.84450449488848 β-1=0.05176823864378 γ-1=0.02782997442973 α1= -0.84450449488848 β1= -0.02782997442973 γ1=-0.05176823864378 α2=-0.09779091752885 β2= -0.03807446337594 γ2= 0.02225975249164 α3= 0.01438088613327 β3= 0.05023776816965 γ3= -0.00249383057321 α4= -0.00173507063342 β4=-0.01618803080395 γ4=0.00018594182937 α5=0.00000401327055 β5=0.00003790058109 γ5=-0.00000042496289 ВейвлетДобешис M=4. α-7=0.00000000205286 β-7 =0.00000000009443 γ-7=-0.00000004462725 α-6=-0.00000544992677 β-6 =-0.00000025123058 γ-6=0.00011822433115 α-5=-0.00041543477135 β-5 =-0.00001769213018 γ-5=0.00969983443149 α-4=0.00432716179594 β-4=0.00030224225713 γ-4= -0.04151919818136 α-3=-0.02134228538239 β-3=-0.00242879427312 γ-3= 0.05677199535135 α-2=0.14516544960962 β-2=0.01699891329704 γ-2=-0.00862627283270 α-1=0.93050197130889 β-1=-0.04758076037403 γ-1=-0.04917088083201 α1=-0.93050197130889 β1= 0.04917088083201 γ1=0.04758076037403 a2=-0.14516544960962 β2= 0.00862627283270 γ2=-0.01699891329704 a3=0.02134228538239 β3= -0.05677199535135 γ3=0.00242879427312 α4=-0.00432716179594 β4=0.04151919818136 γ4=-0.00030224225713 a5=0.00041543477135 β5=-0.00969983443149 γ5=0.00001769213018 a6=0.00000544992677 β6=-0.00011822433115 γ6=0.00000025123058 α7=-0.00000000205286 β7= 0.00000004462725 γ7=-0.00000000009443 3.
Симлет с M=2. α-3=-0.00520833333331 β-3 =-0.00139556871057 γ-3=0.01943776462271 α-2=0.04687500000004 β-2=0.02222890204378 γ-2=-0.04027109795592 α-1=0.71874999999873 β-1=-0.03887552924536 γ-1=0.00279113742108 α1=-0.71874999999873 β1=-0.00279113742108 γ1=0.03887552924536 α2=-0.04687500000004 β2=0.04027109795592 γ2=-0.02222890204378 α3=0.00520833333331 β3=-0.01943776462271 γ3=0.00139556871057 ЛИТЕРАТУРА 1.Beylkin G. Wavelets and Fast
Numerical Algorithms 2.Beylkin G. Wavelets, Multiresolution
Analysis and Fast Numerical Algorithms 3.Beylkin G. In The Representation.of
Operators in Bases of Compactly Supported Wavelets 4.Bradley K. Alpert A Class of Bases in L2 for the Sparse
Representation of Integral Operators 5.
// Успехи
физических наук – 2001, №5. – С.465-500
a1=1.1250 a3=-0.1250
r1=-0.6667r2=0.0833
a1=1.1719a3=-0.1953a5=0.0234
a1=1.19628906249870a3=-0.23925781249914
a5=0.04785156250041a7=-0.00488281249997
a1=1.21124267578280
a3=-0.26916503906311 a5=0.06921386718738
a1=1.20035616471068
a3=-0.24753371156550a5=0.05401594511476
r1=-0.74520547946903r2=0.14520547945865
r3=-0.01461187214494
r4=-0.00034246575336