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

На конечном этапе мы имеем дело с вейвлет-представлением, описываемым  формулой (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₀. Вычисления можно теперь проделать очень быстро.

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

Утверждение 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