| |||
Реферат: Матричные операции в вейвлетном базисеБелорусский государственный университет Факультет прикладной математики и информатики Кафедра математической физики ГРОМОВА МАРИЯ МИХАЙЛОВНА МАТРИЧНЫЕ ОПЕРАЦИИ В ВЕЙВЛЕТНОМ БАЗИСЕ Курсовая работа студентки 3 курса Научный руководитель: Глушцов Анатолий Ильич кафедры МФ кандидит физ.-мат. наук Минск 2003 СОДЕРЖАНИЕ ВВЕДЕНИЕ………..………………………………………………………..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) столкнулся с
проблемой анализа сигналов, которые характеризовались высокочастотной
компонентой в течение короткого промежутка времени и низкочастотными
колебаниями при рассмотрении больших временных масштабов. Оконные
преобразования позволяли проанализировать либо высокие частоты в коротком
окне времени, либо низкочастотную компоненту, но не оба колебания
одновременно. В результате был предложен подход, в котором для различных
диапазонов частот использовались временные окна различной длительности. Среди российских ученых, работавших в области теории вейвлетов, необходимо отметить С.Б. Стечкина, И.Я. Новикова, В.И. Бердышева. 1. МНОГОМАСШТАБНЫЙ АНАЛИЗ И ВЕЙВЛЕТЫ Определение 1. Многомасштабный анализ (multiresolutional analysis) – разложение гильбертова пространства L2(Rd), d(1, в последовательность замкнутых подпространств [pic], (1.1)
обладающих следующими свойствами: 2. Для любого f( L2(Rd), для любого j( Z, f(x)(Vj тогда и только
тогда, когда
f(2x) (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) [pic]. (1.8) [pic], (1.9) где [pic], (1.10) а 2(-периодическая функция m0 определяется следующим образом: [pic]. (1.11) Во-вторых, ортогональность {((x-k)}k(Z подразумевает, что [pic] [pic] (1.13) и [pic]. (1.14) [pic] (1.15) и, рассматривая сумму в (1.15) по четным и нечетным индексам, имеем [pic]. (1.16) [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 вейвлеты Равенство (1.17) определяет пару квадратурных зеркальных фильтров Выбранный фильтр Н полностью определяет функции ( и ( и, таким образом, многомасштабный анализ. Кроме того, в правильно построенных алгоритмах значения функций ( и ( почти никогда не вычисляются. Благодаря рекурсивному определению вейвлетного базиса, все операции проводятся с квадратурными зеркальными фильтрами H и G, даже если в них используются величины, связаные с ( и (. 2. БЫСТРОЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ После того, как вычислены коэффициенты hk и gk, т.е. выбран определенный вейвлет, можно проводить вейвлет-преобразование сигнала f(x), поскольку задан ортонормальный базис ((j,k, ( j,k). Любая функция f(x)(L2(R) полностью характеризуется ее вейвлет- коэффициентами разложения по этому базису и потому может быть представлена формулой [pic]. (2.1) [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) Остающиеся проблемы связаны с начальными данными. Если известен явный
вид функции f(x), то коэффициенты s0,k можно вычислить, используя формулу В общем случае можно выбрать [pic]. (2.7) Обратное быстрое вейвлет-преобразование позволяет реконструировать функцию по значениям ее вейвлет-коэффициентов. 3. ДВУМЕРНЫЕ ВЕЙВЛЕТЫ Многомасштабный анализ можно проводить и с многомерными функциями. Тривиальный путь построения двумерного ортонормального базиса исходя из одномерного ортонормального вейвлет-базиса (j,k(x)=2j/2((2jx-k) состоит в том, чтобы путем тензорного произведения образовать соответствующие функции из двух одномерных базисов: [pic]. (3.1) Больший интерес для многих приложений имеет другая конструкция, в которой масштабирование полученного ортонормального вейлет-базиса происходит по обеим переменным одинаковым образом и двумерные вейвлеты задаются следующим выражением: [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) [pic]. (4.1.4) [pic], (4.1.5) [pic], (4.1.6) где [pic] и замена нижних индексов S(D соответствует подстановке ((( под знаком интеграла. Имеется связь между разными уровнями, потому что все s-коэффициенты на этом (jn-1)-м уровне должны быть разложены с помощью быстрого вейвлет- преобразования на s- и d-коэффициенты более высоких уровней. Поэтому, даже имея почти диагональный вид на начальном этапе, стандартная матрица преобретает затем довольно сложный вид, как это показано на рис.1. На конечном этапе мы имеем дело с вейвлет-представлением, описываемым
формулой (2.1), в которой в векторах остается только один s-коэффициент,
представляющий взвешенное среднее функции по всему интервалу ее задания, а Рис.1. Матричное представление при стандартном подходе к вейвлет-анализу. Части матрицы с ненулевыми вейвлет-коэффициентами заштрихованы. С целью упрощения вида матричного представления было предложено
использовать переопределенный набор вейвлет-коэффициентов. Сохраним эти
усредненные величины в виде соответствующих промежуточных s-коэффициентов
как в начальных, так и в конечных векторах, представляющих функции f и g. Рис.2. Нестандартное матричное умножение при вейвлет-анализе. Различные уровни оказались полностью развязанными, потому что в матрице
теперь полностью отсутствуют блоки, которые ранее перепутывали их. Блок с 4.2 Обращение матрицы Утверждение 1. Последовательность матриц Xk такова, что Xk+1=2Xk -XkАXk, (4.2.1) X0=(А*, (4.2.2) где А* - сопряженная матрица и ( выбирается таким образом, чтобы наибольшее собственное значение матрицы (А*А меньше двух. Тогда последовательность сходится к обобщенной обратной матрице А-1. Если это утверждение скомбинировать с алгоритмом быстрого матричного умножения, то получается алгоритм для построения обратной матрицы в стандартной форме с трудоемкостью [pic] и в нестандартной форме с трудоемкостью [pic], где R – число обусловленности матрицы. С помощью числа R можно оценить соотношение между наибольшим и наименьшим сингулярными числами выше порога точности. 4.3 Вычисление экспоненты, синуса и косинуса от матрицы. При обращения матрицы использовался ранее известный алгоритм, который выходит на совершенно иной уровень, когда применяется вместе с вейвлет- представлением. Алгоритм вычисления экспоненты матрицы основывается на тождестве [pic]. (4.3.1) Аналогично, синус и косинус от матрицы могут быть посчитаны с исподьзованием формул двойного угла. [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, с помощью рядов Тейлора, а затем используем формулы Обычно такие алгоритмы требуют по меньшей мере 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]
|
|