Матричные операции в вейвлетном базисеВейвлет-представление сигналов (функций времени) является промежуточным между полностью спектральным и полностью временным представлениями. Компактные волны относительно независимо были предложены в квантовой физике, физике электромагнитных явлений, математике, электронике и сейсмогеологии. Междисциплинарные исследования привели к новым приложениям данных методов, в частности, в сжатии образов для архивов и телекоммуникаций, в исследованиях турбулентности, в физиологии зрительной системы, в анализе радарных сигналов и предсказании землетрясений. К сожалению, объем русскоязычной научной литературы по тематике вейвлет-преобразований (да и нейронных сетей) относительно невелик. Базовая идея восходит к временам 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 ) – разложение гильбертова пространства L 2 ( R d ), d ³ 1, в последовательность замкнутых подпространств Функция j - так называемая масштабирующая (скейлинг-) функция. С ее помощью можно определить функцию y - вейвлет - такую, что набор { y ( x - k )} k Z образует ортонормальный базис в W 0 . Тогда Выбранный фильтр Н полностью определяет функции j и y и, таким образом, многомасштабный анализ. Кроме того, в правильно построенных алгоритмах значения функций j и y почти никогда не вычисляются. Благодаря рекурсивному определению вейвлетного базиса, все операции проводятся с квадратурными зеркальными фильтрами H и G , даже если в них используются величины, связаные с j и y . 2. БЫСТРОЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ После того, как вычислены коэффициенты h k и g k , т.е. выбран определенный вейвлет, можно проводить вейвлет-преобразование сигнала f ( x ), поскольку задан ортонормальный базис ( y j , k , j j , k ). Любая функция f ( x ) L 2 ( R ) полностью характеризуется ее вейвлет-коэффициентами разложения по этому базису и потому может быть представлена формулой Коэффициенты s j , k и d j , k содердат информацию о составе сигнала на разных масштабах и вычисляются по формулам: Опишем более быстрый алгоритм. В реальных ситуациях с оцифрованным сигналом мы всегда имеем дело с конечным набором цифр (точек). Поэтому всегда существует наилучший уровень разрешения, когда каждый интервал содержит по одному числу. Соответственно и суммирование по k будет идти в конечных пределах. Удобно изменить шкалу разрешения (или шкалу f ), приписав значение j =0 этому наилучшему уровню разрешения. В этом случае легко вычислить вейвлет-коэффициенты для более усредненных уровней j ³ 1. Многомасштабный анализ приводит естественным путем к иерархической и быстрой схеме вычисления вейвлет-коэффициентов заданной функции. В общем случае итерационные формулы быстрого вейвлет-преобразования имеют вид: Простая форма полученных итерационных уравнений служит единственным оправданием введения множителя Однако, уравнения (2.4), (2.5) используются на практике значительно чаще других, и поэтому эту нормировку не изменяют. Любые дополнительные сомножители в них могут привести лишь к усложнению численных расчетов. Остающиеся проблемы связаны с начальными данными. Если известен явный вид функции f ( x ), то коэффициенты s 0, k можно вычислить, используя формулу (2.6). Но ситуация отличается от этой, если доступны только дискретные значения f ( x ). Чтобы достичь высокой точности, хорошо бы задать очень малые интервалы (плотную решетку), но это зачастую недоступно из-за конечности интервалов сбора информации. В таком случае простейшее принимаемое решение состоит в непосредственном использовании величин f ( k ) из доступного набора данных в виде коэффициентов s 0, k и применении быстрого вейвлет-преобразования с использованием формул (2.4), (2.5). Это безопасная операция, т.к. пирамидальный алгоритм обеспечивает полную реконструкцию сигнала, а коэффициенты s 0, k по сути представляют собой локальные средние значения сигнала, взвешенные со скейлинг-функцией. В общем случае можно выбрать Существует два способа обобщить его на двумерный случай, но чаще используется построение, заданное тензорными произведениями. Тривиальный путь построения двумерного ортонормального базиса исходя из одномерного ортонормального вейвлет-базиса y j , k ( x )=2 j /2 y (2 j x - k ) состоит в том, чтобы путем тензорного произведения образовать соответствующие функции из двух одномерных базисов: Больший интерес для многих приложений имеет другая конструкция, в которой масштабирование полученного ортонормального вейлет-базиса происходит по обеим переменным одинаковым образом и двумерные вейвлеты задаются следующим выражением: Рассмотрим структуру тех элементов матричного представления некоторого оператора Т, которые достаточно велики. Матричные элементы удовлетворяют следующим соотношениям. Рассметрим действие оператора Т на функцию f , которое превращает ее в функцию g . Имеется связь между разными уровнями, потому что все s - коэффициенты на этом (j n -1) - м уровне должны быть разложены с помощью быстрого вейвлет-преобразования на s - и d -коэффициенты более высоких уровней. Поэтому, даже имея почти диагональный вид на начальном этапе, стандартная матрица преобретает затем довольно сложный вид, как это показано на рис.1. На конечном этапе мы имеем дело с вейвлет-представлением, описываемым формулой (2.1), в которой в векторах остается только один sкоэффициент, представляющий взвешенное среднее функции по всему интервалу ее задания, а SS - переход от f к g описывается верхним левым квадратиком на этом рисунке. В то же время на пути к этой формуле от скейлинг-представления нам приходилось иметь дело со средними величинами на промежуточных уровнях, разлагая их затем на каждом этапе на части, s и d , последующих уровней разрешения. Эти промежуточные s - коэффициенты были опущены, потому что мы заменяли их на s - и d-коэффициенты поледующих уровней. Именно поэтому окончательная матрица при стандартном подходе приобретает такой сложный вид. Сохраним эти усредненные величины в виде соответствующих промежуточных s - коэффициентов как в начальных, так и в конечных векторах, представляющих функции f и g . Конечно, в этом случае придется иметь дело с приводимыми векторами, которые намного больше требуемых для конечного ответа. Однако, известен алгоритм приведения этих переопределенных выражений к окончательной непереопределенной форме. В то же время таким образом можно существенно упростить вид матрицы преобразования и численные расчеты. Рис.2. Нестандартное матричное умножение при вейвлет-анализе. Различные уровни оказались полностью развязанными, потому что в матрице теперь полностью отсутствуют блоки, которые ранее перепутывали их. Блок с SS - элементами извлечен, а на его место вставлена нулевая матрица. Полная матрица соответстваенно искусственным образом увеличилась. Вместе с ней увеличились и векторы, характеризующие функции f и g . Теперь здесь удерживаются все промежуточные s - коэффициенты вейвлет-разложения функции f . Каждый блок S j+1 получается из S j и D j . В матрице преобразования равны нулю все SS - элементы за исключением их величин на низшем уровне S 0 S 0 . Все остальные SD -, DS-, DDматрицы почти диагональны вследствие конечности области задания вейвлетов и скейлинг функций. Приведенная на рис. 2 форма функции g преобразуется в ее обычное вейвлет-представление из рис. 1 путем разделения каждого S j в S j-1 и D j-1 стандартным методом. Затем эти S j-1 и D j-1 добавляются в соответствующие компоненты вектора. Эта процедура итерируется, начиная теперь уже с S j-1 , вполоть до S 0 , когда мы приходим к обычному вейвлет-представлению функции g . Таким способом мы избавляемся от всех s - коэффициентов за исключением s 0 . Вычисления можно теперь проделать очень быстро. 4 .2 Обращение матрицы Утверждение 1. Последовательность матриц X k такова, что X k+1 =2 X k - X k А X k , (4.2.1) X 0 = a А * , (4.2.2) где А * - сопряженная матрица и a выбирается таким образом, чтобы наибольшее собственное значение матрицы a А * А меньше двух. Тогда последовательность сходится к обобщенной обратной матрице А -1 . Если это утверждение скомбинировать с алгоритмом быстрого матричного умножения, то получается алгоритм для построения обратной матрицы в стандартной форме с трудоемкостью Алгоритм вычисления экспоненты матрицы основывается на тождестве |
оценка лицензии в Смоленске
оценка машин для наследства в Курске