Быстрое вейвлет-преобразование

После того, как вычислены коэффициенты h_k и g_k, т.е. выбран определенный вейвлет, можно проводить вейвлет-преобразование сигнала f(x), поскольку задан ортонормальный базис (y_j,k, j _j,k). Любая функция f(x)ÎL²(R) полностью характеризуется ее вейвлет-коэффициентами разложения по этому базису и потому может быть представлена формулой

. (2.1)

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

. (2.4)

На бесконечном интервале первая сумма может быть опущена, и в результате получается «чистое» вейвлет-разложение.

Коэффициенты s_j,k и d_j,k содердат информацию о составе сигнала на разных масштабах и вычисляются по формулам:

, (2.2)

. (2.3)

Однако при этом компьютерные расчеты занимают довольно длительное время, т.к. при вычислении приходится проводить O(N²) операций, где N – число имеющихся значений функции. Опишем более быстрый алгоритм.

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

В общем случае итерационные формулы быстрого вейвлет-преобразования имеют вид:

, (2.4)

(2.5)

с

. (2.6)

Эти уравнения обеспечивают быстрые (или пирамидальные) алгоритмы вычисления вейвлет-коэффициентов, поскольку требуют только O(N) операций для своего завершения. Начав с s_0,k, мы вычислим все другие вейвлет-коэффициенты, если параметры вейвлета h_m и g_m известны. Явный вид вейвлета при этом не используется. Простая форма полученных итерационных уравнений служит единственным оправданием введения множителя в функциональное уравнение (1.8). В принципе, коэффициенты h_m и g_m можно было бы перенормировать. Однако, уравнения (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 по сути представляют собой локальные средние значения сигнала, взвешенные со скейлинг-функцией.

В общем случае можно выбрать

. (2.7)

Рассмотренная ситуация отвечает условию s_0,k=f(k), что соответствует c_m=d_0m.

Обратное быстрое вейвлет-преобразование позволяет реконструировать функцию по значениям ее вейвлет-коэффициентов.

Двумерные вейвлеты

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

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

. (3.1)

В этом базисе две переменных x₁ и x₂ сжимаются по-разному.

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

, j,k,lÎZ, (3.2)

но Y уже не является единственной функцией, наоборот, она будет сформирована из трех элементарных вейвлетов. Чтобы создать ортонормальный базис W₀, теперь придется использовать три семейства

, , .

Тогда двумерные вейвлеты запишутся в виде

, , .

На двумерной плоскости происходит анализ по горизонталям, вертикалям и диагоналям с одинаковым разрешением в соответствии с тремя выписанными выше вейвлетами.

Матричные операции

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

Существует два возможных способа воздействовать оператором на функцию в рамках вейвлет-теории. Они называются стандартным и нестандартным матричным умножением.

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

при , (4.1.1)

при , (4.1.2)

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

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

(4.1.3)

Как g, так и f могут быть представлены в виде вейвлет-рядов с вейвлет-коэффициентами (_f s_j,k;_f d_j,k) и (_g s_j,k;_g d_j,k). На наиболее детальном уровне разрешения j_n отличны от нуля только s-коэффициенты, и преобразование имеет вид

. (4.1.4)

На следующем уровне получаем

, (4.1.5)

, (4.1.6)

где

и замена нижних индексов S®D соответствует подстановке j®y под знаком интеграла.

Имеется связь между разными уровнями, потому что все s-коэффициенты на этом (j_n-1)-м уровне должны быть разложены с помощью быстрого вейвлет-преобразования на s- и d-коэффициенты более высоких уровней. Поэтому, даже имея почти диагональный вид на начальном этапе, стандартная матрица преобретает затем довольно сложный вид, как это показано на рис.1.

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

Рис.1. Матричное представление при стандартном подходе к вейвлет-анализу.

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

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

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

Различные уровни оказались полностью развязанными, потому что в матрице теперь полностью отсутствуют блоки, которые ранее перепутывали их. Блок с SS-элементами извлечен, а на его место вставлена нулевая матрица. Полная матрица соответстваенно искусственным образом увеличилась. Вместе с ней увеличились и векторы, характеризующие функции f и g. Теперь здесь удерживаются все промежуточные s-коэффициенты вейвлет-разложения функции f. Каждый блок S_j+1 получается из S_j и D_j. В матрице преобразования равны нулю все SS-элементы за исключением их величин на низшем уровне S₀S₀. Все остальные SD-, DS-, DD-матрицы почти диагональны вследствие конечности области задания вейвлетов и скейлинг функций. Приведенная на рис. 2 форма функции g преобразуется в ее обычное вейвлет-представление из рис. 1 путем разделения каждого S_j в S_j-1 и D_j-1 стандартным методом. Затем эти S_j-1 и D_j-1 добавляются в соответствующие компоненты вектора. Эта процедура итерируется, начиная теперь уже с S_j-1, вполоть до S₀, когда мы приходим к обычному вейвлет-представлению функции g. Таким способом мы избавляемся от всех s-коэффициентов за исключением s₀. Вычисления можно теперь проделать очень быстро.

Обращение матрицы

Утверждение 1. Последовательность матриц X_k такова, что

X_k+1=2X_k -X_kАX_k, (4.2.1)

X₀=aА^*, (4.2.2)

где А^* - сопряженная матрица и a выбирается таким образом, чтобы наибольшее собственное значение матрицы aА^*А меньше двух. Тогда последовательность сходится к обобщенной обратной матрице А^-1.

Если это утверждение скомбинировать с алгоритмом быстрого матричного умножения, то получается алгоритм для построения обратной матрицы в стандартной форме с трудоемкостью и в нестандартной форме с трудоемкостью , где R – число обусловленности матрицы. С помощью числа R можно оценить соотношение между наибольшим и наименьшим сингулярными числами выше порога точности.

4.3 Вычисление экспоненты, синуса и косинуса от матрицы.

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

Алгоритм вычисления экспоненты матрицы основывается на тождестве

. (4.3.1)

Во-первых, exp(2^-LA) может быть посчитана, например, с помощью ряда Тейлора. Число L выбирается таким образом, чтобы наибольшее сингулярное число матрицы 2^-LA было меньше единицы. На втором шаге алгоритма для достижения результата матрица 2^-LA возводится в квадрат L раз.

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

(4.3.2)

, (4.3.3)

при l=0,…,L-1

(4.3.4)

, (4.3.5)

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

Обычно такие алгоритмы требуют по меньшей мере O(N³) операций, так как должне быть выполнено достаточно много операций по умножению густых матриц. Быстрый алгоритм для умножения матриц в стандартной форме уменьшает сложность до не более чем операций, а быстрый алгоритм для умножения матриц в нестандартной форме – до O(N) операций.

Список литературы

Beylkin G. Wavelets and Fast Numerical Algorithms.

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

Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование // Успехи физических наук – 2001, №5. – С.465-500