Математика

Операторы в вейвлетном базисе

Белорусский государственный университет
                Факультет прикладной математики и информатики


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



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


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



                      Курсовая работа студентки 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)   –
разложение  гильбертова  пространства  L2(Rd),  d(1,  в   последовательность
замкнутых подпространств
                                                                      [pic],
                (1.1)
обладающих следующими свойствами:
1.          [pic],        и          [pic]       полно       в       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)}k(Zd
образует
базис Ритца в V0.
Для ортонормальных базисов можно переписать свойство 4 в виде:
4’.  Существует  масштабирующая  функция  ((V0,  что  {((x-k)}k(Zd  образует
  ортонормальный базис в V0.
Определим подпространство Wj как ортогональное дополнение к Vj в Vj-1,
                                                                      [pic],
                                               (1.2)
и представим пространство L2(Rd) в виде прямой суммы
                                                                       [pic]
                                          (1.3)
      Выбирая масштаб n, можем заменить последовательность  (1.1)  следующей
последовательностью:
                                                                       [pic]
       (1.4)
и получить
                                                                       [pic]
                                     (1.5)
      Если имеем конечное число масштабов, то, не  нарушая  общности,  можно
положить j=0 и рассматривать
                                                   [pic],      V0(    L2(Rd)
                          (1.6)
вместо (1.4). В числовой реализации подпространство V0 конечномерно.
      Функция ( - так называемая масштабирующая (скейлинг-)  функция.  С  ее
помощью можно определить функцию ( -  вейвлет  -  такую,  что  набор   {((x-
k)}k(Z  образует ортонормальный базис в W0. Тогда
                                                        [pic],     m=0..M-1.
                                     (1.7)
Из свойства 4’ непосредственно следует,  что,  во-первых,  функция  (  может
быть представлена в виде линейной комбинации базисных  функций  пространства
V-1   .   Так   как    функции     {(j,k(x)=2-j/2((2-jx-k)}k(Z      образуют
ортонормальный базис в Vj, то имеем
                                                                      [pic].
                              (1.8)
Вообще говоря, сумма в выражении  (1.8)  не  обязана  быть  конечной.  Можно
переписать (1.8) в виде
                                                                      [pic],
                                (1.9)
где
                                                                      [pic],
                            (1.10)
а 2(-периодическая функция m0 определяется следующим образом:
                                                                      [pic].
                                  (1.11)
      Во-вторых, ортогональность {((x-k)}k(Z подразумевает, что
                                                                       [pic]
  (1.12)
и значит
                                                                       [pic]
                    (1.13)
и                                                                     [pic].
                                     (1.14)
Используя (1.9), получаем
                                                                       [pic]
            (1.15)
и, рассматривая сумму в (1.15) по четным и нечетным индексам, имеем
     [pic].   (1.16)
Используя 2(-периодичность функции m0 и  (1.14),  после  замены  (/2  на  (,
получаем необходимое условие
                                                                       [pic]
                           (1.17)
для коэффициентов hk в (1.11). Заметив, что
                                                                       [pic]
                                (1.18)
и определив функцию ( следующим образом:
                                                                      [pic],
                           (1.19)
где
                                               [pic],         k=0,…,L-1    ,
                                  (1.20)
или преобразование Фурье для (
                                                                      [pic],
                              (1.21)
где
                                                                      [pic],
                                  (1.22)
можно   показать,       что    при     каждом     фиксированном     масштабе
j(Z     вейвлеты
{(j,k(x)=2-j/2((2-jx-k)}k(Z  образуют ортонормальный базис пространства Wj.
      Равенство (1.17)  определяет  пару  квадратурных  зеркальных  фильтров
(quadrature mirror filters, QMF) H и G, где [pic] и [pic]. Коэффициенты  QMF
H и G вычисляются с помощью решения системы алгебраических уравнений.  Число
L коэффициентов фильтра в  (1.11)  и  (1.22)  связано  с  числом  исчезающих
моментов М, и  всегда четно.
      Выбранный фильтр Н  полностью  определяет  функции  (  и  (  и,  таким
образом,  многомасштабный  анализ.  Кроме  того,  в  правильно   построенных
алгоритмах значения функций ( и ( почти никогда  не  вычисляются.  Благодаря
рекурсивному определению  вейвлетного  базиса,  все  операции  проводятся  с
квадратурными зеркальными фильтрами H и G,  даже  если  в  них  используются
величины, связанные с ( и (.



                                4. ОПЕРАТОРЫ


      Сжатие операторов или, другими словами, представление их в разреженном
виде  в  ортонормированном  базисе  непосредственно   влияет   на   скорость
вычислительных алгоритмов.
      Нестандартная форма оператора Т с ядром K(x,y) достигается вычислением
следующих выражений:
                                           [pic]
         (4.1)
                                           [pic]
         (4.2)
                                           [pic]
          (4.3)

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

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

                                  [pic]                           (4.5)
                                 [pic]                            (4.6)
                                  [pic]                              (4.7)
где
                                                   [pic]
                            (4.8)
                                                                       [pic]
                            (4.9)
                                                                       [pic]
                           (4.10)
                                                                       [pic]
                             (4.11)
Кроме того, используя (1.8)  и (1.19), имеем
                                                        [pic]
                             (4.12)
                                                        [pic]
                              (4.13)
                                                                       [pic]
                             (4.14)
Таким образом представление d/dx  полностью  определяется  величинами  [pic]
или, другими словами, отображением d/dx на подпространство V0.
Предложение 4.1.  1. Если существует  интеграл  (4.11),  тогда  коэффициенты
[pic], l( Z в (5.8) удлвлетворяют следующей системе линейных  алгебраических
уравнений:
                                           [pic]
     (4.15)
                                                                  [pic]
                                                   (4.16)
где
                                                [pic]  [pic]
                    (4.17)
2. Если [pic], тогда система  (4.15)-(4.16)  имеет  единственное  решение  с
конечным числом ненулевых [pic], а именно с [pic] и [pic].
Замечание.  Если  М=1,  тогда  система  (4.15)-(4.16)   имеет   единственное
решение, но интеграл (4.11) может не быть абсолютно сходящимся.  Для  базиса
Хаара ([pic]) [pic], [pic] мы получаем простейший конечный  дифференциальный
оператор [pic].
Замечание 2. Заметим, что выражения  (4.12)  и  (4.13)  для  [pic]  и  [pic]
([pic]) могут быть упрощены с помощью смены порядка суммирования в (5.10)  и
(5.11)  и  введения  коэффициентов  корреляции  [pic],   [pic]   и    [pic].
Выражение для [pic] особенно просто: [pic].
      Для доказательства Предложения 4.1 можно обратиться к [2].
      Для  решения  системы  (4.15)-(4.16)   можно   также   воспользоваться
итерационным  алгоритмом.  Начать  можно  с  [pic]   и   [pic],   а   дальше
итерировать, используя (4.15) для вычисления [pic].


      4.2 Оператор dn/dxn в вейвлетном базисе

      Так же как и для оператора d/dx, нестандартная форма оператора  dn/dxn
полностью  определяется  своим  отображением  на  подпространство  V0,  т.е.
коэффициентами
                                             [pic],   l( Z,
              (4.18)
если интеграл существует.
Предложение 4.2. 1. Если интеграл в выражении (4.18) существует, тогда
коэффициенты [pic], l( Z удовлетворяют следующей системе линейных
алгебраических уравнений
                                           [pic]
(4.19)
                                                                [pic]
                                     (4.20)
где [pic]  дано в формуле (4.17).
2. Пусть M ? (n+1)/2, где М – число исчезающих  моментов.  Если  интеграл  в
(4.18) существует, тогда система (4.19)-(4.20) имеет единственное решение  с
конечным числом нулевых коэффициентов  [pic],  а  именно  [pic]  для  [pic].
Также для четных n
                                                                 [pic]
                                                    (4.21)
                                                [pic]  [pic]
                         (4.22)
                                                                       [pic]
                                                  (4.23)
а для нечетных n
                                                                       [pic]
                                                 (4.24)
                                                        [pic]          [pic]
                      (4.25)
Замечание 3. Если M ? (n+1)/2, тогда решение линейной системы в  Предложении
2  может  существовать,  когда  интеграл  в  (4.18)  не  является  абсолютно
сходящимся.


Интегральные уравнения второго рода

      Линейное интегральное уравнение Фредгольма есть выражение вида
                                   [pic],
где ядро [pic], а неизвестная функция f(x) и функция в правой  части  [pic],
[pic]. Для простоты будем рассматривать  интервал  [pic]и  введём  следующее
обозначение для всех [pic] и [pic]:
                                    [pic]
Предположим,  что  {?1,  ?1,…}  –  ортонормальный  базис  для  [pic];   ядро
представимо в этом базисе в следующем виде:
                                    [pic]
где коэффициенты Kij вычисляются по формуле
                                [pic],  [pic]
Аналогично функции f и g представимы в виде
                               [pic],  [pic],
где коэффициенты fi и gi вычисляются по формулам:
                          [pic],  [pic],   i=1,2,…
Интегральное уравнение  в  этом  случае  соответствует  бесконечной  системе
уравнений
                              [pic],   i=1,2,…
Представление ядра может быть урезано  до  конечного  числа  слагаемых,  что
приводит к представлению интегрального оператора R:
                            [pic],  [pic], [pic],
который аппроксимирует  K.  Тогда  интегральное  уравнение  аппроксимируется
системой n уравнений с n неизвестными:
                              [pic],  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)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


   1. Вейвлет Добеши с M=2.

      a1=1.1250 a3=-0.1250

      r1=-0.6667  r2=0.0833
   2. Вейвлет Добеши с M=3.

      a1=1.1719  a3=-0.1953  a5=0.0234
      r1=-0.7452 r2=0.1452  r3=-0.0146  r4=-0.0003
   3. Вейвлет Добеши с 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
   4. Вейвлет Добеши с 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
   5. Вейвлет Добеши с 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
   6. Вейвлет Койфмана с 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
   7. Симлет с M=2.
      a1=1.12499999999971  a3=-0.12499999999971
      r1=-0.66666666666616 r2=0.08333333333308
   8. Симлет с M=3.
      a1=1.17187500000666  a3=-0.19531250000432  a5=0.02343749999766

      r1=-0.74520547946903  r2=0.14520547945865  r3=-0.01461187214494

      r4=-0.00034246575336
   9. Симлет с 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


   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.00018594182937  |?-4= 0.01618803080395  |
|?-4=0.00173507063342   |                       |                       |
|?-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


смотреть на рефераты похожие на "Операторы в вейвлетном базисе "