Матричные операції в вейвлетном базисе

Білоруський державний университет.

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

Кафедра математичної физики.

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

МАТРИЧНІ ОПЕРАЦІЇ У ВЕЙВЛЕТНОМ БАЗИСЕ.

Курсова робота студентки 3 курса.

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

Глушцов Анатолій Ілліч кафедри МВ кандидит физ.-мат. наук.

Мінськ 2003.

ВВЕДЕНИЕ

…3.

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

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

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

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

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

4.2. Звернення матрицы…16.

4.3. Обчислення експоненти, синуса і косинуса від матрицы…16.

ЛИТЕРАТУРА

…18.

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

Компактні хвилі щодо незалежно було запропоновано в квантової фізиці, фізиці електромагнітних явищ, математиці, електроніці і сейсмогеологии. Міждисциплінарні дослідження сприяли новим додатків даних методів, зокрема, в стисканні образів для архівів і телекомунікацій, в дослідженнях турбулентності, в фізіології зорової системи, в аналізі радарних сигналів і пророкуванні землетрусів. До жалю, обсяг російськомовної наукової літератури з тематиці вейвлетперетворень (та й нейронних мереж) щодо невелик.

Базова ідея перегукується з часів 200-летней давності й належить Фур'є: апроксимувати складну функцію виваженої сумою простих функцій, кожна з яких, своєю чергою, виходить з однієї функции-прототипа. Ця функция-прототип виконує роль будівельного блоку, а бажана апроксимація виходить комбінуванням однакових структурою блоків. У цьому, якщо «хороша «апроксимація виходить під час використання небагатьох блоків, тим самим досягається значне ущільнення інформації. Як таких блоків Фур'є використовував синусоїди з різними периодами.

Що ви насамперед відрізняє вейвлет-анализ від аналізу Фур'є? Основним недоліком Фурье-преобразования є його «глобальна «чутливість до «локальним «стрибків і списам функції. У цьому модифікація коефіцієнтів Фур'є (наприклад, обрізання високих гармонік з єдиною метою фільтрації шуму) вносить однакові зміни у поведінка сигналу на області визначення. Це особливість виявляється корисною для стаціонарних сигналів, властивості що у цілому мало змінюються зі временем.

При дослідженні ж нестаціонарних сигналів потрібно використання деяких локалізованих у часі компактних хвиль, коефіцієнти розкладання якими зберігають інформацію про дрейфі параметрів аппроксимируемой функції. Першим спробував побудови таких систем функцій полягали в сегментированию сигналу на фрагменти («вікна ») із застосуванням розкладання Фур'є тих фрагментів. Відповідне перетворення — віконне перетворення Фур'є - було запропоновано 1946;47 роках Jean Ville і, незалежно, Dennis Gabor. У 1950;70-х роках різними авторами було опубліковано багато модифікацій времени-частотных уявлень сигналов.

Наприкінці 70-х инженер-геофизик Морли (Jean Morlet) зіштовхнувся з проблемою аналізу сигналів, які характеризувалися високочастотної компонентом протягом короткого проміжку часу й низкочастотными коливаннями під час розгляду великих тимчасових масштабів. Віконні перетворення дозволяли проаналізувати або високі частоти в короткому вікні часу, або низкочастотную компоненту, але з обидва коливання одночасно. У результаті запропонований підхід, у якому щодо різноманітних діапазонів частот використовувалися тимчасові вікна різної тривалості. Віконні функції виходили внаслідок растяжения-сжатия і усунення по часу гаусиана. 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 конечномерно.

Функція (- так звана масштабирующая (скейлинг-) функція. З її допомогою можна визначити функцію (- вейвлет — таку, що набір {((xk)}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, навіть тоді як них використовуються величини, пов’язані з (і (.

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

Потому, як враховано коефіцієнти hk і gk, тобто. обраний певний вейвлет, робити вейвлет-преобразование сигналу f (x), оскільки заданий ортонормальный базис ((j, k, (j, k). Будь-яка функція f (x)(L2® повністю характеризується її вейвлеткоефіцієнтами розкладання у цій базису і тому то, можливо представлена формулой.

[pic].

(2.1) Поставимо усі межі підсумовування у формулі (2.1). Функцію f (x) можна розглядати будь-якою n-ою рівні дозволу jn. Тоді поділ між її усередненими значеннями в таких межах і флуктуаціями навколо них виглядають как.

[pic].

(2.4) На нескінченному інтервалі перша сума то, можливо опущене, і цього виходить «чисте» вейвлет-разложение.

Коефіцієнти sj, k і dj, k содердат інформацію складу сигналу на різних масштабах і обчислюються по формулам:

[pic],.

(2.2).

[pic].

(2.3).

Однак цьому комп’ютерні розрахунки займають досить довгий час, т.к. при обчисленні доводиться проводити O (N2) операцій, де N — число наявних значень функції. Наведемо швидший алгоритм.

У реальних ситуаціях з оцифрованным сигналом ми завжди маємо працювати з кінцевим набором цифр (точок). Тому завжди існує найкращий рівень дозволу, коли кожний інтервал містить за одним числу. Відповідно і підсумовування по k йтиме у кінцевих межах. Зручно змінити шкалу дозволу (чи шкалу f), приписавши значення j=0 цьому найкращому рівню дозволу. І тут легко обчислити вейвлет-коэффициенты ще усереднених рівнів j (1. Многомасштабный аналіз наводить природним шляхом до ієрархічної і швидкої схемою обчислення вейвлет-коэффициентов заданої функции.

У випадку итерационные формули швидкого вейвлет-преобразования мають вид:

[pic],.

(2.4).

[pic].

(2.5) с.

[pic].

(2.6) Ці рівняння забезпечують швидкі (чи пірамідальні) алгоритми обчислення вейвлет-коэффициентов, оскільки вимагають лише O (N) операцій для свого завершення. Почавши з s0, k, ми обчислимо й інші вейвлет-коэффициенты, якщо параметри вейвлета hm і gm відомі. Явний вид вейвлета у своїй не використовується. Проста форма отриманих итерационных рівнянь служить єдиним виправданням запровадження множника [pic] в функціональне рівняння (1.8). У принципі так, коефіцієнти hm і gm можна було б перенормировать. Проте, рівняння (2.4), (2.5) використовуються практично значно частіше від інших, і тому цю нормировку не змінюють. Будь-які додаткові сомножители у яких можуть призвести тільки в ускладнення про чисельні расчетов.

Залишаються проблеми пов’язані з початковими даними. Якщо відомий явний вид функції f (x), то коефіцієнти s0, k можна визначити, використовуючи формулу (2.6). Але ситуація відрізняється від цього, якщо доступні лише дискретні значення f (x). Аби високої точності, хоча б поставити дуже малі інтервали (щільну грати), але ці найчастіше недоступно через кінцівки інтервалів збору інформації. У разі найпростіше прийняте рішення полягає у безпосередньому використанні величин f (k) з доступного набору даних як коефіцієнтів s0, k і застосування швидкого вейвлетперетворення з допомогою формул (2.4), (2.5). Це безпечна операція, т.к. пірамідальний алгоритм забезпечує повну реконструкцію сигналу, а коефіцієнти s0, k власне є локальні середні значення сигналу, зважені зі скейлинг-функцией.

У випадку можна выбрать.

[pic].

(2.7) Розглянута ситуація відповідає умові s0, k=f (k), що він відповідає cm=(0m.

Протилежне швидке вейвлет-преобразование дозволяє реконструювати функцію по значенням її вейвлет-коэффициентов.

3. ДВОМІРНІ ВЕЙВЛЕТЫ.

Многомасштабный аналіз можна й з многомерными функціями. Існує дві способу узагальнити його за двомірний випадок, але частіше використовується побудова, заданий тензорными произведениями.

Тривіальний шлях побудови двумерного ортонормального базису виходячи з одномірного ортонормального вейвлет-базиса (j, k (x)=2j/2((2jx-k) полягає у цьому, щоб шляхом тензорного твори утворити відповідні функції з цих двох одномірних базисов:

[pic].

(3.1) У цьому вся базисі дві змінних x1 і x2 стискуються по-разному.

Більший інтерес багатьом додатків має інша конструкція, в якої масштабирование отриманого ортонормального вейлет-базиса іде за рахунок обом змінним однаковим способом мислення й двомірні вейвлеты задаються наступним выражением:

[pic], j, k, l (Z,.

(3.2) але (вже є єдиною функцією, навпаки, вона сформована із трьох елементарних вейвлетов. Щоб створити ортонормальный базис W0, тепер доведеться використовувати три семейства.

[pic], [pic], [pic]. Тоді двомірні вейвлеты запишуться в виде.

[pic], [pic], [pic]. На двумерной площині відбувається аналіз по горизонталям, вертикалям і діагоналям з дозволом відповідно до трьома виписаними вище вейвлетами.

4. МАТРИЧНІ ОПЕРАЦИИ.

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

Існує дві можливих способу впливати оператором на функцію у межах вейвлет-теории. Вони називаються стандартним і нестандартним матричним умножением.

У досить гладких функцій більшість їх вейвлет-коэффициентов досить маленькі. Для широкого класу операторів більшість їх матричних елементів також виявляються невеликими. Розглянемо структуру тих елементів матричного уявлення деякого оператора Т, які досить великі. Матричні елементи задовольняють наступним соотношениям.

[pic] при [pic],.

(4.1.1).

[pic] при [pic],.

(4.1.2).

Топологія розподілу цих матричних елементів всередині матриці може бути вельми запутанной.

Рассметрим дію оператора Т на функцію f, який перетворює їх у функцію g.

[pic].

(4.1.3) Як g, і f можуть бути як вейвлет-рядов з вейвлеткоефіцієнтами (f sj, k;f dj, k) і (g sj, k;g dj, k). На найдетальнішому рівні дозволу jn відмінні від нуля лише s-коэффициенты, і перетворення має вид.

[pic].

(4.1.4) На наступному рівні получаем.

[pic], (4.1.5).

[pic], (4.1.6) где.

[pic] і заміна нижніх індексів S (D відповідає підстановці (((під знаком интеграла.

Є зв’язок між різними рівнями, оскільки всі s-коэффициенты у цьому (jn-1)-м рівні повинні прагнути бути розкладені з допомогою швидкого вейвлетперетворення на p. sі d-коэффициенты вищих рівнів. Тому, навіть маючи майже діагональний вид на початковому етапі знають, стандартна матриця преобретает потім досить складний вид, як і показано на рис. 1.

На кінцевому етапі ми маємо справу з вейвлет-представлением, описуваних формулою (2.1), у якій в вектори залишається тільки один s-коэффициент, що становить зважене середнє функції всьому інтервалу її завдання, а SS-переход від f до g описується верхнім лівим квадратиком у цьому малюнку. У той самий час шляху до цієї формули від скейлинг-представления нам доводилося мати справу зі середніми величинами на проміжних рівнях, розкладаючи їх потім кожному етапі на частини, p. s і d, наступних рівнів дозволу. Ці проміжні s-коэффициенты були вкинуті, тому що ми заміняли їх у p. sі d-коэффициенты поледующих рівнів. Саме тому остаточна матриця за стандартного на підході набуває таке складне вид.

Мал.1. Матричне уявлення за стандартного на підході до вейвлет-анализу.

Частини матриці з ненульовими вейвлет-коэффициентами заштрихованы.

З метою спрощення виду матричного уявлення запропонували використовувати переопределенный набір вейвлет-коэффициентов. Збережемо ці усереднені величини як відповідних проміжних s-коэффициентов як і початкових, і у кінцевих вектори, які мають функції f і g. Звісно, у разі доведеться поводитися з які приводилися векторами, які набагато більше необхідних кінцевого відповіді. Проте, відомий алгоритм приведення цих переопределенных висловів до остаточної непереопределенной формі. У той самий час в такий спосіб можна істотно спростити вид матриці перетворення і чисельні расчеты.

Рис. 2. Нестандартне матричне множення при вейвлет-анализе.

Различные рівні виявилися повністю розв’язаними, оскільки у матриці тепер повністю відсутні блоки, які раніше перепутывали їх. Блок з SS-элементами витягнутий, але в його місце вставлена нульова матриця. Повна матриця соответстваенно штучно збільшилася. Разом із нею збільшилися і вектори, що характеризують функції f і g. Тут тепер утримуються все проміжні s-коэффициенты вейвлет-разложения функції f. Кожен блок Sj+1 виходить з Sj і Dj. У матриці перетворення рівні нулю все SS-элементы крім їх величин на нижчому рівні S0S0. Решта SD-, DS-, DD-матрицы майже диагональны внаслідок кінцівки області завдання вейвлетов і скейлинг функцій. Наведена на рис. 2 форма функції g перетворюється на її звичайне вейвлет-представление з мал. 1 шляхом поділу кожного Sj в Sj-1 і Dj-1 стандартним методом. Потім ці Sj-1 і Dj-1 додаються на відповідні компоненти вектора. Цю процедуру итерируется, починаючи сьогодні вже з Sj-1, вполоть до S0, ми дійшли звичайному вейвлет-представлению функції g. У такий спосіб ми позбуваємося всіх s-коэффициентов крім s0. Обчислення можна тепер проробити дуже быстро.

4.2 Звернення матрицы Утверждение 1. Послідовність матриць Xk така, что.

Xk+1=2XkXkАXk,.

(4.2.1).

X0=(А*,.

(4.2.2) де А* - сполучена матриця і (вибирається в такий спосіб, щоб найбільше власне значення матриці (А*А менше двох. Тоді послідовність сходиться до узагальненої зворотної матриці А-1.

Якщо це твердження скомбінувати з алгоритмом швидкого матричного множення, виходить алгоритм для побудови зворотної матриці в стандартної формі з трудомісткістю [pic] й у нестандартній формі з трудомісткістю [pic], де R — число зумовленості матриці. З допомогою числа R можна оцінити співвідношення між найбільшим і найменшим сингулярними числами вище порога точности.

4.3 Обчислення експоненти, синуса і косинуса від матрицы.

При звернення матриці використовувався раніше відомий алгоритм, який входить у зовсім інший рівень, коли застосовується разом із вейвлетпредставлением.

Алгоритм обчислення експоненти матриці полягає в тождестве.

[pic].

(4.3.1) По-перше, exp (2-LA) то, можливо порахована, наприклад, з допомогою низки Тейлора. Кількість L вибирається в такий спосіб, щоб найбільше сингулярне число матриці 2-LA було менше одиниці. З другого краю кроці алгоритму для досягнення результату матриця 2-LA зводиться у квадрат L раз.

Аналогічно, синус і косинус від матриці може бути пораховані з исподьзованием формул подвійного угла.

[pic].

(4.3.2).

[pic],.

(4.3.3) при l=0,…, L-1.

[pic].

(4.3.4).

[pic],.

(4.3.5) де I — тотожність. Знову вибираємо L в такий спосіб, щоб найбільше сингулярне число матриці 2-LA було менше одиниці, обчислюємо синус і косинус матриці 2-LA, з допомогою рядів Тейлора, та був використовуємо формули (4.3.4) і (4.3.5).

Зазвичай такі алгоритми вимагають по меншою мірою O (N3) операцій, так як должне виконати досить багато операцій із множенню густих матриць. Швидкий алгоритм для множення матриць у кімнаті стандартного формі зменшує складність до ніж [pic] операцій, а швидкий алгоритм для множення матриць в нестандартній формі - до O (N) операций.

1. Beylkin G. Wavelets and Fast Numerical Algorithms.

2. Beylkin G. Wavelets, Multiresolution Analysis and Fast Numerical.

Algorithms.

3. Дремин І.М., Іванов О.В., Нечитайло В. А. Вейвлеты та його использование.

// Успіхи фізичних наук — 2001, № 5. — С.465−500 ———————————- [pic].

[pic].