Операторы в вейвлетном базисе
Формат: doc
Дата создания: 16.05.2004
Размер: 82.51 KB
Скачать рефератБелорусский государственный университет
Факультет прикладной математики и информатики
Кафедра математической физики
ГРОМОВА МАРИЯ МИХАЙЛОВНА
ОПРЕАТОРЫ В ВЕЙВЛЕТНОМ БАЗИСЕ
Курсовая работа студентки 4 курса
Научный руководитель:
Глушцов Анатолий Ильич
кафедры МФ
кандидат физ.-мат. наук
Минск 2004
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………..………………………………………………………..3
-
МНОГОМАСШТАБНЫЙ АНАЛИЗ И ВЕЙВЛЕТЫ………………...5
-
БЫСТРОЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ….……………………...9
-
ДВУМЕРНЫЕ ВЕЙВЛЕТЫ…………………………………………..12
-
МАТРИЧНЫЕ ОПЕРАЦИИ………………………………………….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) – разложение гильбертова пространства L2(Rd), d1, в последовательность замкнутых подпространств
, (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) функция V0, что {(x-k)}kZd образует
базис Ритца в V0.
Для ортонормальных базисов можно переписать свойство 4 в виде:
4’. Существует масштабирующая функция V0, что {(x-k)}kZd образует ортонормальный базис в 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 конечномерно.
Функция - так называемая масштабирующая (скейлинг-) функция. С ее помощью можно определить функцию - вейвлет - такую, что набор {(x-k)}kZ образует ортонормальный базис в W0. Тогда
, m=0..M-1. (1.7)
Из свойства 4’ непосредственно следует, что, во-первых, функция может быть представлена в виде линейной комбинации базисных функций пространства V-1 . Так как функции {j,k(x)=2-j/2(2-jx-k)}kZ образуют ортонормальный базис в Vj, то имеем
. (1.8)
Вообще говоря, сумма в выражении (1.8) не обязана быть конечной. Можно переписать (1.8) в виде
, (1.9)
где
, (1.10)
а 2-периодическая функция m0 определяется следующим образом:
. (1.11)
Во-вторых, ортогональность {(x-k)}kZ подразумевает, что
(1.12)
и значит
(1.13)
и . (1.14)
Используя (1.9), получаем
(1.15)
и, рассматривая сумму в (1.15) по четным и нечетным индексам, имеем
. (1.16)
Используя 2-периодичность функции m0 и (1.14), после замены /2 на , получаем необходимое условие
(1.17)
для коэффициентов hk в (1.11). Заметив, что
(1.18)
и определив функцию следующим образом:
, (1.19)
где
, k=0,…,L-1 , (1.20)
или преобразование Фурье для
, (1.21)
где
, (1.22)
можно показать, что при каждом фиксированном масштабе jZ вейвлеты
{j,k(x)=2-j/2(2-jx-k)}kZ образуют ортонормальный базис пространства Wj.
Равенство (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)
(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. Если , тогда система (4.15)-(4.16) имеет единственное решение с конечным числом ненулевых , а именно с и .
Замечание. Если М=1, тогда система (4.15)-(4.16) имеет единственное решение, но интеграл (4.11) может не быть абсолютно сходящимся. Для базиса Хаара ( ) , мы получаем простейший конечный дифференциальный оператор .
Замечание 2. Заметим, что выражения (4.12) и (4.13) для и ( ) могут быть упрощены с помощью смены порядка суммирования в (5.10) и (5.11) и введения коэффициентов корреляции , и . Выражение для особенно просто: .
Для доказательства Предложения 4.1 можно обратиться к [2].
Для решения системы (4.15)-(4.16) можно также воспользоваться итерационным алгоритмом. Начать можно с и , а дальше итерировать, используя (4.15) для вычисления .
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)<len-2);
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)<len-2);
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)<length(R)+1)&&((2*i+k-k1+L)>0))
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
-
Вейвлет Добеши с M=2. a1=1.1250 a3=-0.1250 r1=-0.6667 r2=0.0833
-
Вейвлет Добеши с M=3. a1=1.1719 a3=-0.1953 a5=0.0234
r1=-0.7452 r2=0.1452 r3=-0.0146 r4=-0.0003
-
Вейвлет Добеши с M=4. a1=1.19628906249870 a3=-0.23925781249914 a5=0.04785156250041 a7=-0.00488281249997
r1=-0.79300950497055 r2=0.19199897079726 r3=-0.03358020705113
r4= 0.00222404967066 r5=0.00017220619000 r6=-0.00000084085054
-
Вейвлет Добеши с M=5. a1=1.21124267578280 a3=-0.26916503906311 a5=0.06921386718738
a7=-0.01235961914130 a9=0.00106811523422
r1=-0.82590601185686 r2=0.22882018706986 r3=-0.05335257193327
r4=0.00746139636621 r5=-0.00023923581985 r6=-0.00005404730164
r7=-0.00000025241171 r8=-0.00000000026960
-
Вейвлет Добеши с M=6.
a1=1.22133636474683 a3=-0.29079437255810 a5=0.08723831176674
a7=-0.02077102661228 a9=0.00323104858448 a11=-0.00024032592766
r1=-0.85013666156022 r2=0.25855294414318 r3=-0.07244058999853
r4=0.01454551104340 r5=-0.00158856154379 r6=0.00000429689148
r7=0.00001202657519 r8=0.00000042069120 r9=-0.00000000289967
r10=0.00000000000070
-
Вейвлет Койфмана с M=2. a1=1.20035616471068 a3=-0.24753371156550 a5=0.05401594511476
a7=-0.00724698442340 a9=0.00043220193586 a11=-0.00002361577240
r1=-0.80177838961957 r2=0.20214744976459 r3=-0.03943577686925
r4=0.00404789045961 r5=-0.00008445623632 r6=0.00000255044096
r7=0.00000088836508 r8=0.00000000237860 r9=-0.00000000002099
r10=0.00000000000000
-
Симлет с M=2.
a1=1.12499999999971 a3=-0.12499999999971
r1=-0.66666666666616 r2=0.08333333333308
-
Симлет с M=3.
a1=1.17187500000666 a3=-0.19531250000432 a5=0.02343749999766 r1=-0.74520547946903 r2=0.14520547945865 r3=-0.01461187214494 r4=-0.00034246575336
-
Симлет с M=4.
a1=1.19628906249990 a3=-0.23925781249985 a5=0.04785156249993
a7=-0.00488281249998
r1=-0.79300950497424 r2=0.19199897079876 r3=-0.03358020705098
r4=0.00222404967071 r5=0.00017220619000 r6=-0.00000084085054
ПРИЛОЖЕНИЕ 4
-
Вейвлет Добеши с 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
-
Вейвлет Добеши с 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 |
-
Симлет с 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 |
ЛИТЕРАТУРА
-
Beylkin G. Wavelets and Fast Numerical Algorithms
-
Beylkin G. Wavelets, Multiresolution Analysis and Fast Numerical Algorithms
-
Beylkin G. In The Representation.of Operators in Bases of Compactly Supported Wavelets
-
Bradley K. Alpert A Class of Bases in L2 for the Sparse Representation of Integral Operators
-
Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование // Успехи физических наук – 2001, №5. – С.465-500