\documentstyle{amsppt} %\documentstyle{lhamsppt} \pagewidth{6.5in} \pageheight{9in} \magnification1200 \TagsOnRight \define\Lt{\Bbb L^2(\Bbb R)} \define\z{\Bbb Z} \define\R{\Bbb R} \define\vf{\varphi} \define\sign{\text{sign\,}} \define\dfn{\,\overset\text{def}\to=\,} \topmatter \title Биортогональные базисы всплесков с рациональными масками и их приложения\footnotemark \endtitle \rightheadtext{Биортогональные базисы всплесков с рациональными масками} \author А.П.Петухов \endauthor \email petukhov\@pdmi.ras.ru \endemail \abstract\nofrills Рассмотрены общие принципы построения биортогональных базисов всплесков, ассоциированных с рекурсивными фильтрами. Представлены быстрые алгоритмы разложения функций по данным базисам, в том числе, алгоритмы, опирающиеся на факторизации полифазных матриц. Приведены результаты численного моделирования алгоритмов сжатия изображений, основанные на разложении изображений по предлагаемому базису, которые позволяют сделать вывод о высокой эффективности предлагаемых алгоритмов, как с точки зрения вычислительных затрат, так и с точки зрения величины коэффициентов сжатия. \endabstract \endtopmatter \document \footnotetext{ Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант \# 97-01-00443).} \head \S 1. Введение. \endhead За последние 10 лет базисы всплесков стали мощным инструментом как для многих теоретических задач анализа так и для прикладных проблем, связанных с обработкой сигналов. Наибольшее развитие получила та часть теории базисов всплесков, которая связана с базисами, чьи функции имеют компактные носители. Алгоритмы разложения функций по таким базисам реализуются в виде набора дискретных сверток с числовыми последовательностями, имеющими лишь конечное число ненулевых коэффициентов. В радиотехнике действующие на бесконечных последовательностях перестановочные со сдвигом линейные операторы (т.е. операторы свертки) называют {\it (цифровыми) фильтрами}. Последовательность чисел, формирующая ядро свертки называют {\it импульсной характеристикой} фильтра. Таким образом, разложение по базисам всплесков с компактными носителями реализуется при помощи фильтров, имеющих конечную импульсную характеристику (КИХ-фильтров). Преобразование Фурье импульсной характеристики фильтра называют его {\it частотной характеристикой}. Следовательно, частотная характеристика фильтра с конечной импульсной характеристикой является тригонометрическим полиномом. Во многих разделах математики, например в теории аппроксимации, рациональные функции оказываются более гибким и эффективным инструментом, чем полиномы. Мы рассмотрим здесь базисы всплесков, разложение по которым реализовано на фильтрах с рациональной частотной характеристикой. Разумеется, появление новых видов базисов всплесков дает новые возможности применительно к прикладным задачам обработки сигналов и изображений. \par Несмотря на тот факт, что этот вид фильтров имеет бесконечную импульсную характеристику (БИХ-фильтры), существует их эффективная численная реализация в виде композиции хорошо известных в радиотехнике, так называемых, рекурсивных фильтров. Причем вычислительные затраты на реализацию фильтров с рациональной частотной характеристикой оказываются пропорциональными сумме степеней числителя и знаменателя, что сравнимо с затратами на реализацию разложений по базисам с компактными носителями, которые пропорциональны степеням соответствующих полиномов. %ВСТАВКА РИСУНКОВ К ЛЕММЕ 1 %\vbox{\hskip 1.5 true cm %РИСУНОК 1а %\special{em:graph lemma1_1.pcx} %\special{em:graph pic.pcx} %\hskip 6.5 true cm %РИСУНОК 1б %\special{em:graph lemma1_2.pcx} %} \par Впервые подобные базисы были подвергнуты систематическому исследованию в работе К.Херли и М.Веттерли [1], где был рассмотрен случай, когда соответствующие базисы ортогональны и образуют кратномасштабный анализ (КМА) пространства $\Lt$. Как известно (см. [4]), за исключением хааровских базисов, не существует ортогональных базисов всплесков с компактными носителями, функции которых с точностью до сдвига аргумента являются четными или нечетными. Однако для базисов, порожденных рекурсивными БИХ-фильтрами, это не так. В [1] были найдены четные и нечетные базисы, ассоциированные с рекурсивными фильтрами. Ортогональность базисов позволяет получать результаты, гарантирующие сходимость и устойчивость алгоритмов разложения, значительно меньшими усилиями, чем в случаях, когда ортогональность отсутствует. Однако для того, чтобы использовать ортогональность нужно, по меньшей мере, иметь в исследуемом пространстве скалярное произведение. Но даже если скалярное произведение определено, для эффективного использования ортогональных базисов в прикладных задачах требуется, чтобы евклидово расстояние было естественным для данной задачи. К сожалению, это не всегда так. В частности, в обработке изображений наиболее эффективными оказались не ортогональные базисы всплесков, а биортогональные пары базисов. Например, для сжатия изображений наиболее часто используются так называемые 9/7-всплески с компактными носителями, полученные в работе [2]. Что касается базисов, построенных в [1], сочетающих ортогональность и симметрию, то ввиду жесткости требований их адаптация к конкретной задаче весьма проблематична. Результаты численного моделирования алгоритмов сжатия изображений с использованием таких базисов показали, что их эффективность достаточно мала по крайней мере для малых порядков рекурсивных фильтров. Напротив, инструмент биортогональных пар базисов, порожденных рекурсивными фильтрами, по гибкости заметно превосходит инструмент биортогональных пар базисов с компактными носителями. \par О возможности построения биортогональных пар фильтров с рациональной частотной характеристикой говорится, например, в книге Г.Стренга и Т.Нгуена [7]. Там же имеется несколько примеров таких базисов, получающихся как побочный продукт при построении "хороших" базисов с компактными носителями. Мы будем здесь строить именно биортогональную теорию базисов, ассоциированных с рекурсивными фильтрами. Как мы увидим, использование такого подхода ведет в некоторых задачах к существенной экономии вычислительных затрат. \par Изначально теория базисов всплесков развивалась независимо от возникшей несколько ранее в радиотехнике теории субполосного кодирования. Однако скоро стала ясна их почти полная идентичность. Во всяком случае, это можно утверждать в большинстве практически важных случаев. В \S 2 мы остановимся на их связи. К сожалению, в общем случае вопрос о том, когда пара фильтров, определяющая алгоритм субполосного кодирования, порождает пару биортогональных базисов, остается до сих пор открытым. К настоящему времени для биортогонального случая наиболее полно этот вопрос был исследован в работах [2], [5], но только для случая, когда ассоциированные с субполосным кодированием базисы принадлежат $\Lt$ и имеют компактный носитель. Поэтому в \S 3 мы временно оставим вопрос о соответствии с базисами всплесков и, оставаясь на платформе субполосного кодирования, займемся построением биортогональных пар фильтров с рациональной частотной характеристикой. \par В \S 4 будет для БИХ-фильтров построен алгоритм реализации субполосного кодирования и восстановления сигналов, основанный на, так называемой, лифтинг-схеме (см. [3], [6]), позволившей получить асимптотически двукратный выигрыш в вычислительных затратах по сравнению с прямой реализацией алгоритмов сверток при реализации субполосного кодирования на КИХ-фильтрах. \par В \S 5 произведен подсчет вычислительной сложности предлагаемых алгоритмов и приведено сравнение с вычислительными затратами при прямой реализации алгоритмов разложения по всплескам. \par В \S 6 мы приведем результаты численного моделирования алгоритмов сжатия изображений, позволяющие сравнить эффективность новых алгоритмов по сравнению с известными как по коэффициенту сжатия, так и по вычислительным затратам. Кроме того, будут приведены соображения, показывающие, что использованные в расчетах фильтры ассоциируются с некоторыми парами биортогональных базисов всплесков пространства $\Lt$. %******************* \head \S 2. Кратномасштабный анализ квазибанаховых пространств распределений. \endhead %******************* Сначала мы перенесем определение Кратномасштабного анализа на квазибанаховы пространства, отличные от $\Lt$. Напомним, что квазибанаховы пространства порождаются квазинормой, т.е. функционалом, чье отличие от нормы заключается в том, что неравенство треугольника для нее справедливо лишь в виде $\|f+g\|\le C(\|f\|+\|g\|)$, где $C>1$. Такое ослабление свойств нормы позволяет включить в общее рассмотрение много полезных пространств типа пространств Харди. Полное рассмотрение теории Кратномасштабного анализа пространств периодических распределений можно найти в нашей статье [8] (см. также [9], [11]), случай периодических всплесков на дискретной сетке рассмотрен в [10]. Приводимые ниже определения всплесков в квазибанаховых пространствах непериодических распределений ни в коей мере не являются завешенной теорией. Это лишь набросок возможной схемы построения теории всплесков, который здесь нам необходим только для того, чтобы показать место тех частных базисов, построением которых мы будем здесь заниматься. \par Обозначим через $S^\prime$ и $S$ соответственно пространство распределений умеренного роста и пространство основных функций \par %\definition{Определение 1} %Набор линейных подпространств %$\{V^j\}_{j\in\z}$ пространства $S^\prime$, замкнутых %в топологии пространства $S^\prime$, %называется Кратномасштабным анализом (КМА) пространства %$S^\prime$, если он удовлетворяет следующим условиям: %\par %a) $\dots\subset V^{-2}\subset V^{-1}\subset V^0\subset V^1 \dots$; %\par %b) $\overline{\cup V^j}=S^\prime$; %, $\cap \overline{V^j}$ %содержит константы или $\delta$-функцию; %\par %c) $f(x)\in V^j\Leftrightarrow f(2x)\in V^{j+1}$; %\par %d) найдется такое распределение $\varphi\in V^0$, называемое %{\it масштабирующей функцией}, %что линейная оболочка системы распределений %$\varphi(\bullet - k)$, $k\in\z$ плотна в $V^0$. %\enddefinition \definition{Определение 1} Набор замкнутых линейных подпространств $\{V^j\}_{j\in\z}$ квазибанахова пространства $X$, $S\subset X\subset S^\prime$ называется {\it кратномасштабным анализом} КМА пространства $X$, если он удовлетворяет следующим условиям: \par a) $\dots\subset V^{-2}\subset V^{-1}\subset V^0\subset V^1\subset \dots$; \par b) $\overline{\cup V^j}=X$; %, $\cap \overline{V^j}$ %содержит константы или $\delta$-функцию; \par c) $f(x)\in V^j\Leftrightarrow f(2x)\in V^{j+1}$; \par d) найдется такое распределение $\varphi\in V^0$, называемое {\it масштабирующей функцией}, что линейная оболочка системы распределений $\varphi(\bullet - k)$, $k\in\z$ плотна в $V^0$. \enddefinition %***************** %\definition{Определение 2} %Набор замкнутых линейных подпространств $\{V^j\}_{j\in\z}$ %квазибанахова пространства %$X$, $S\subset X\subset S^\prime$ %называется КМА пространства %$X$, если замыкания этих линейных пространств в топологии %пространства $S^\prime$ образуют КМА пространства $S^\prime$. %\enddefinition \par Согласно пункту b) Определения 1 функция $\varphi(x)$ может быть приближена линейными комбинациями функции $\{\varphi(2x-k)\}$. Нас будет интересовать лишь случай, когда КМА образуется вещественными пространствами и имеет место {\it масштабирующее уравнение} $$ \varphi(x)=\sqrt2\sum_{n\in\z} h_n \varphi(2x-n),\tag 2.1 $$ где $h_n$ --- коэффициенты Фурье рациональной функции $$ \sqrt2m_0(\omega)=\frac{{\Cal P}(e^{i\omega})}{{\Cal Q}(e^{i\omega})}= \sum_{n\in\z} h_ne^{-in\omega}.\tag {2.2} $$ Ясно, что при этом $h_n$ --- вещественная последовательность. В (2.2) функции ${\Cal P}(z)$ и ${\Cal Q}(z)$ являются Лорановскими полиномами. Заметим, что мы используем здесь традиционный множитель $\sqrt2$, поскольку, если функции $\{\varphi (x-n)\}$ образуют ортонормированный базис пространства $V^0\in \Lt$, то функции $\{\sqrt2\varphi(2x-n)\}$ образуют ортонормированный базис в $V^1$. Соотношение (2.1) после применения к нему преобразования Фурье может быть переписано в виде $$ \hat\varphi(\omega)=m_0\left(\frac\omega2\right)\hat\varphi \left(\frac\omega2\right). \tag{2.3} $$ Если предположить, что $\hat\varphi$ --- непрерывная функция и $\hat\varphi(0)\ne0$, то ясно, что $m_0(0)=1$. Таким образом, воспользовавшись (2.3), предполагая, что $\hat\varphi(0)=(2\pi)^{-1/2}$, можно доказать, что $$ \hat\varphi(\omega)=(2\pi)^{-1/2}\prod_{k=1}^\infty m_0 \left(\frac\omega{2^k}\right), $$ где произведение в правой части сходится равномерно на компактных множествах. %Случай, когда все пространства $V^j$ содержат $\delta$-функцию, %также является рациональным(даже полиномиальным) %и укладывается в предыдущую схему, %поскольку, если $\varphi(x)=\delta(x)$, то $m_0(\omega)\equiv1$. \par Пусть $\{V^j\}$ КМА квазибанахова пространства $X$. Обозначим через $Z^\circ$ пополнение пространства $S$ относительно квазинормы пространства $Z$. Будем в дальнейшем считать $X=X^\circ$. Для того чтобы ввести понятие всплеск-разложения пространства $X$ нам понадобится КМА $\{\tilde V^j\}$ двойственного пространства $Y=X^{*\circ}$. При этом пространства $$ W^j=\{f\in V^{j+1} | \langle f,g\rangle=0, \text{ для любых } g\in \tilde V^j\} $$ будем называть пространствами всплесков. Аналогичным образом определяются двойстенные пространства всплесков $$ \tilde W^j=\{g\in \tilde V^{j+1} | \langle f,g\rangle=0, \text{ для любых } f\in V^j\}. $$ Мы не будем здесь обсуждать дополнительные условия для правильного определения пространств всплесков, однако отметим, что КМА $\{\tilde V^j\}$ сопряженного пространства должно быть выбранно так, чтобы $V^j\cap W^j={0}$, тогда $$ V^{j+1}= W^j\oplus V^j=\left(\bigoplus_{i=0}^k W^{j-i}\right)\bigoplus V^{j-k}= \left(\bigoplus_{i=0}^{+\infty}W^{j-i}\right) \bigoplus\left(\bigcap_{i\in\z} V^{i}\right), $$ где значок $\oplus$ означает прямую сумму пространств. Добавка пересечения пространств $V^i$ в последней формуле не могла появиться в случае КМА пространств $\Lt$, поскольку для $\Lt$ такое пересечение всегда пусто. Совсем по другому обстоит дело в общем случае. Нетрудно придумать примеры КМА, имеющие в пересечении полиномы фиксированной степени, $\delta$-функцию Дирака или ее обобщенные производные. \par Прокомментируем проведенное построение. С одной стороны, ясно, что классическое определение КМА пространства $\Lt$ нуждается в обобщении на другие функциональные пространства, в которых не определено скалярное произведение. Однако, на первый взгляд, может показаться, что Определение 1 охватывает слишком обширный класс пространств и для приложений можно ограничиться классическими функциональными пространствами, не переходя к обобщенным функциям. С этим можно было бы согласиться, если бы пространства $V^j$ использовались лишь как аппроксимации пространства $X$. Однако в определении пространств всплесков участвуют два КМА взаимно-сопряженных пространств, причем один из них служит для приближения, а второй --- для определения проекции. А поскольку, чем \'уже исходное пространство, тем шире пространство сопряженное, то для определения проекции на пространство достаточно гладких функций может оказаться недостаточным наличия функционалов, определяемых обычными функциями. Например, при определении интерполяционных всплесков, примеры которых будут приведены ниже, проекторы задаются сдвигами дельта-функции Дирака --- самым простым примером обобщенной функции. Этот пример является вполне естественным следствием того, что пространством, сопряженным к пространству непрерывных функций, является пространство конечных борелевских мер. Заметим, что пространство конечных борелевских мер не является сепарабельным. Поэтому, если $X=\Bbb C(\Bbb R)$ --- пространство непрерывных функций, стремящихся к нулю на бесконечности, то пространство конечных борелевских мер $\Bbb C^*(\Bbb R)$ не совпадает с $\Bbb C^{*\circ}(\Bbb R)$. Однако если в качестве $X$ взять чуть более узкое пространство (например, определяемое каким-нибудь модулем непрерывности), то пространство борелевских мер войдет в сепарабельное подпространство пространства $X^*$. \par Напомним, что две системы функций $\{f_n\}\subset X$ и $\{g_n\}\subset X^*$ называются биортогональными, если справедливы соотношения $$ \langle f_k,g_m\rangle=\cases 1,\quad &k=m,\\ 0, &k\ne m. \endcases $$ Предположим, что в пространстве $\tilde V^0$ имеется биортогональный (базису $\{\varphi(x-n)\}$) базис $\{\tilde\varphi(x-n)\}$, порожденный рациональной функцией $$ \tilde m_0(\omega)= \frac{1}{\sqrt2}\frac{\tilde{\Cal P}(e^{i\omega})}{\tilde{\Cal Q}(e^{i\omega})}= \frac1{\sqrt2}\sum_{n\in\z} \tilde h_ne^{-in\omega}.%\label{2.4} $$ Ввиду условия биортогональности нетрудно получить, что $m_0$ и $\tilde m_0$ должны удовлетворять условию $$ m_0(\omega)\overline{\tilde m_0(\omega)}+ m_0(\omega+\pi)\overline{\tilde m_0(\omega+\pi)}=1.%\label{5} $$ Заметим, что поскольку сходимость бесконечных произведений, определяющих фун\-кции $\hat\varphi$ и $\hat{\tilde\varphi}$, влечет равенства $m(0)=\tilde m(0)=1$, получим, что из условие биортогональности имеем $m(\pi)\overline{\tilde m(\pi)}=0$. Это означает, что хотя бы один из сомножителей $m(\pi)$ и $\tilde m(\pi)$ равен нулю. \par Из определения $W^j$ получим, что преобразование Фурье функции $\psi$, порождающей базис $\{\psi(x-n)\}$ пространства $W^0$, может быть вычислено по формуле $$ \hat\psi(\omega)=m_1(\frac\omega2)\hat\varphi(\frac\omega2),%\label{6} $$ где $m_1$ удовлетворяет уравнению $$ m_1(\omega)\overline{\tilde m_0(\omega)}+ m_1(\omega+\pi)\overline{\tilde m_0(\omega+\pi)}=0.%\label{7} $$ Отсюда $$ m_1(\omega)=\alpha(\omega)e^{-i\omega}\overline{\tilde m_0(\omega+\pi)}, $$ где $\alpha$ --- некоторое $\pi$-периодическое распределение. В дальнейшем, скорее следуя традициям в обозначениях, а не сути дела, мы будем для определенности считать $\alpha(\omega)\equiv 1$. Аналогичным образом введем в рассмотрение функцию $$ \tilde m_1(\omega)=e^{-i\omega}\overline{m_0(\omega+\pi)}, $$ которая порождает базис в двойственном пространстве всплесков $\tilde W^0$. Таким образом, имеет место матричное соотношение $$ \left(\matrix m_0(\omega) &m_0(\omega+\pi)\\ m_1(\omega) &m_1(\omega+\pi) \endmatrix \right) \cdot \left( \matrix \tilde m_0(\omega) &\tilde m_0(\omega+\pi)\\ \tilde m_1(\omega) &\tilde m_1(\omega+\pi) \endmatrix \right)^* = I,\tag{2.4} $$ где $I= \left( \matrix 1&0\\ 0 &1 \endmatrix \right) $. \par Таким образом, уравнение (2.4) дает необходимое условие для того, чтобы функции $m_0$ и $\tilde m_0$ порождали непрерывные масштабирующие функции $\varphi$, $\tilde\varphi$, которые определяют пару двойственных КМА. Что касается достаточных условий, то в настоящее время эта проблема далека от полного разрешения, хотя в большинстве практически важных случаев не составляет труда показать, что конкретное решение уравнения (2.4), действительно, генерирует биортогональную пару базисов некоторых двойственных КМА. \par В случае домножения функции $m_1(\omega)$ на $\pi$-периодическую функцию $\alpha(\omega)$ равенство (2.4) нарушится. Для его восстановления необходимо функцию $\tilde m_1(\omega)$ домножить на $1/\overline{\alpha(\omega)}$, получив при этом $$ \left(\matrix m_0(\omega) &m_0(\omega+\pi)\\ m_1(\omega)\alpha(\omega) &m_1(\omega+\pi)\alpha(\omega) \endmatrix \right) \cdot \left( \matrix \tilde m_0(\omega) &\tilde m_0(\omega+\pi)\\ \tilde m_1(\omega)/\overline{\alpha(\omega)} & \tilde m_1(\omega+\pi)/\overline{\alpha(\omega)} \endmatrix \right)^* = I.\tag{$2.4^\prime$} $$ Разумеется, выбор $\alpha(\omega)$ никак не влияет ни на пару двойственных КМА, которые определяются функциями $m_0$, $\tilde m_0$, ни на выбор базисов в соответствующих пространствах $V^j$ и $\tilde V^j$, ни на выбор пространств всплесков $W^j$ и $\tilde W^j$. Однако варьирование функции $\alpha$ дает дополнительную степень свободы при выборе базисов всплесков в наибольшей степени соответствующих конкретной прикладной задаче. В дальнейшем мы увидим, что базис, наиболее подходящий для сжатия изображений, использует эту степень свободы. Причина невостребованности этого приема в текущей литературе носит объективный характер. Дело в том, что рассматривая биортогональные базисы всплесков, ассоциированные с КИХ-фильтрами мы вынуждены искать полиномиальные решения уравнения (2.4). Если $m_0$ и $\tilde m_0$ --- полиномы, то традиционный выбор функций $m_1$ и $\tilde m_1$ также является полиномиальным. Если же мы домножим функцию $m_1$ на $\pi$-периодический полином $\alpha$, то мы обязаны разделить $\tilde m_1$ на $\overline{\alpha}$. Предположим, что найдется такой $\pi$-периодический полином $\alpha$, что вторая матрица в $(2.4^\prime)$ является полиномиальной. В вырожденном случае, когда $\alpha$ --- одночлен, т.е. с точностью до умножения на постоянную имеем $\alpha(\omega)=e^{i2k\omega}$, $k\in\z$, такой выбор приводит к сдвигу элементов базисов в $W^{-1}$ и $\tilde W^{-1}$ на 2, т.е. фактически лишь к перенумерации элементов базиса. Если же $\alpha$ --- невырожденный полином, то для того, чтобы функция $\tilde m_1/\overline{\alpha}$ была полиномом, требуется совпадение нулей $\tilde m_1$ с нулями полинома $\overline{\alpha}$, но тогда ввиду $\pi$-периодичности полинома $\alpha$ полином $\tilde m_1(\omega+\pi)$ также имеет нули в тех точках, где $\alpha(\omega)=0$. Таким образом, найдется точка $\omega_0$, в которой вектор $(\tilde m_1(\omega_0),\tilde m_1(\omega_0+\pi))$ становится нулевым, а соответствующая матрица в $(2.4)$, становится вырожденной, что приводит к нарушению равенства $(2.4)$ не только в самой этой точке, но, ввиду непрерывности компонент, и в некоторой ее окрестности. В случае же, когда допускаются рациональные решения уравнения $(2.4)$, нулям определителя одной из матриц в $(2.4^\prime)$ можно поставить в соответствие полюсы другого определителя. Таким образом, традиционный выбор функций $m_1$ и $\tilde m_1$ хотя и вполне оправдан, но является единственно возможным только для полиномиальных решений. \par Двойственные КМА $\{V^j\}$ и $\{\tilde V^j\}$ в определенном смысле равноправны и могут рассматриваться как в качестве вложенной последовательности пространств в пространстве сигналов, так и для определения операторов проектирования, которые в свою очередь позволяют определить пространства всплесков. Мы в дальнейшем условимся считать, что сигналы проектируются на пространства $\tilde V^j$ при помощи пространств $V^j$. Такая договоренность принята в подавляющем большинстве публикаций. \par Введем в рассмотрение функции $$ h(z)=\sum_{n\in \z} h_ne^{-in\omega}=\sqrt{2} m_0(\omega),\quad \tilde h(z)=\sum_{n\in \z} \tilde h_ne^{-in\omega}= \sqrt{2} \tilde m_0(\omega),\tag{2.5} $$ где $z=e^{i\omega}$, и $$ g(z)=z^{-1}\tilde h(-z^{-1}),\quad \tilde g(z)=z^{-1} h(-z^{-1}).\tag{2.6} $$ Функции $h$ и $\tilde h$ будем называть {\it биортогональной парой фильтров}. Теперь равенство (2.4) в случае вещественных $\{h_n\}$ и $\{\tilde h_n\}$ может быть переписано в виде $$ M(z)\tilde M^t(z^{-1})=2I,\tag{2.7} $$ где символ $t$ означает транспонирование матрицы, а $$ M(z)=\left(\matrix h(z) &h(-z)\\ g(z) &g(-z) \endmatrix \right),\quad \tilde M(z)=\left(\matrix \tilde h(z) &\tilde h(-z)\\ \tilde g(z) &\tilde g(-z) \endmatrix \right) \text{ ---} %\label{9} $$ так называемые, {\it модуляционные матрицы}, чьи компоненты в нашем случае являются рациональными функциями. Из (2.6) и (2.7) нетрудно получить, что $\det|M(z)|=\det|\tilde M(z)|=-2z^{-1}$. \par Поясним смысл и назначение модуляционных матриц $M$ и $\tilde M$. Пусть $\tilde v^0(x)=\sum_n c^0_n\tilde \vf(x-n)\in \tilde V^0$ и требуется найти проекции $\tilde v^{-1}(x)=\sum_n c^{-1}_n\tilde \vf(x/2-n)$ и $\tilde w^{-1}(x)=\sum_n d^{-1}_n\tilde \psi(x/2-n)$ распределения $\tilde v^0$ на пространства $\tilde V^{-1}$ и $\tilde W^{-1}$. Воспользовавшись масштабирующим уравнением (2.1), получим $$ c^{-1}_m= \langle \tilde v^0(x),\vf(x/2-m)\rangle= \sqrt2\langle \sum_{n\in\z}c^0_n \tilde\vf(x-n),\sum_{k\in\z} h_k\vf(x-k-2m)\rangle= \sqrt2\sum_{n\in\z}c^0_nh_{n-2m}, $$ Последнее равенство в терминах $z$-преобразований последовательностей можно записать в виде $с^{-1}(z^{-2})=\frac{1}{\sqrt2}(h(z)c^0(z^{-1})+h(-z)c^0(-z^{-1}))$, где $c^0(z)=\sum_{n}c^0_n z^{-n}$, $c^{-1}(z)=\sum_{n}c^{-1}_n z^{-n}$. Заметим, что сходимость рядов здесь и в дальнейшем обеспечивается экспоненциальным убыванием последовательностей $\{h_n\}$ и $\{\tilde h_n\}$. Аналогичным образом получается равенство $d^{-1}_m=\sqrt2\sum_{n\in\z}c^0_ng_{n-2m}$, а значит, $d^{-1}(z^{-2})=\frac{1}{\sqrt2}(g(z)c^0(z^{-1})+g(-z)c^0(-z^{-1}))$. \par Таким образом, после перехода к $z$-преобразованиям матрица $M$ становится матрицей перехода от пространства $\tilde V^0$ к прямой сумме пространств $\tilde V^{-1}$ и $\tilde W^{-1}$, определяемого по формуле $$ \left(\matrix c^{-1}(z^{-2})\\ d^{-1}(z^{-2}) \endmatrix \right) =\dsize\frac{1}{\sqrt2} \left(\matrix h(z) &h(-z)\\ g(z) &g(-z) \endmatrix \right) \left(\matrix c^{0}(z^{-1})\\ c^{0}(-z^{-1}) \endmatrix \right).\tag{2.8} $$ Для восстановления коэффициентов разложения функции в базисе пространства $\tilde V^0$ по ее проекциям на пространства $\tilde V^{-1}$ и $\tilde W^{-1}$ имеет место формула $$ \left(\matrix c^{0}(z^{-1})\\ с^{0}(-z^{-1}) \endmatrix \right) =\dsize\frac{1}{\sqrt2} \left(\matrix \tilde h(z^{-1}) &\tilde g(z^{-1})\\ \tilde h(-z^{-1}) &\tilde g(-z^{-1}) \endmatrix \right) \left(\matrix c^{-1}(z^{-2})\\ d^{-1}(z^{-2}) \endmatrix \right). $$ Разумеется, последние формулы удобны для аналитического представления операции разложения по всплескам и восстановления по проекциям, но содержат много повторяющихся операций и потому не могут быть рекомендованы для непосредственного вычисления коэффициентов. \par В каком-то смысле альтернативным методом представления операции разложения пространства $\tilde V^0$ в прямую сумму пространств $\tilde V^{-1}$ и $\tilde W^{-1}$ является его реализация при помощи, так называемой, полифазной матрицы. Для произвольного формального ряда Лорана $f(z)=\sum_n f_nz^{-n}$ введем обозначения $f_e(z)=\sum_n f_{2n}z^{-n}$ и $f_o(z)=\sum_n f_{2n+1}z^{-n}$. Тогда справедливо представление $f(z)=f_e(z^2) +z^{-1}f_o(z^2)$. Если теперь воспользоваться этим представлением, заменив им все компоненты формулы (2.8), то после несложных преобразований правой части получим $$ \left(\matrix c^{-1}(z^{-1})\\ d^{-1}(z^{-1}) \endmatrix \right) =\left (\matrix h_e (z) &h_o (z) \\ g_e (z) &g_o (z) \endmatrix \right) \left(\matrix c_e^{0}(z^{-1})\\ c_o^{0}(z^{-1}) \endmatrix \right).\tag{2.9} $$ Именно эта формула является отправной точкой для построения быстрых алгоритмов разложения и восстановления сигналов, объединенных общим названием лифтинг-схема. Матрицу в выражении (2.9) называют {\it полифазной}. Ее мы будем обозначать через $P(z)$, а полифазную матрицу двойственного КМА --- через $\tilde P(z)$. Нетрудно проверить, что $$ P(z)\tilde P^t(z^{-1})=I.\tag2.10 $$ \par Кроме того, поскольку для полифазных матриц $P$ и $\tilde P$ справедливы представления $$ P(z^2)=\frac12 M(z)\left(\matrix 1&z\\1&-z\endmatrix\right),\quad \tilde P(z^2)=\frac12 \tilde M(z)\left(\matrix 1&z\\1&-z\endmatrix\right), $$ из равенств $\det M=\det \tilde M=-2z^{-1}$ имеем $\det P=\det \tilde P=1$. %**************************** \head \S 3. Примеры. \endhead %**************************** % Для нахождения рациональных решений матричного уравнения (2.7) достаточно %решенить уравнение %$$ %\Cal H(z)+\Cal H(-z)=2 %h(z)\tilde h(z^{-1})+h(-z)\tilde h(-z^{-1})=2, %$$ %с последующей факторизацией $\Cal H(z)=h(z)\tilde h(z^{-1})$. Уравнение (2.7) имеет много рациональных решений. Хотя из дальнейших рассуждений легко видеть, как можно получить все возможные решения такого типа, нас будут здесь интересовать лишь некоторые из них, которые имеют минимальный порядок числителя и знаменателя и соответствуют базисам всплесков, чьи масштабирующие функции являются симметричными относительно целых или полуцелых точек. При этом мы покажем, что после подходящего сдвига аргумента соответствующие базисы всплесков являются в первом случае нечетными, а во втором случае --- четными функциями. Поэтому для краткости будем говорить, что имеет место соответственно нечетный или четный случай. \par Рассмотрим сначала четный случай. Заметим, что домножение функции $h(z)$ на $z^k$ означает переход от масштабирующей функции $\vf(z)$ к масштабирующей функции $\vf(z+k)$, т.е. переход к одной из функций базисной системы сдвигов. Нетрудно видеть, что домножив $h$, если нужно, на подходящую целую степень переменной $z$, мы получим, что в (2.5) $h_n=h_{-n}$ для всех $n=1,2,\dots$. Функция $h(z)$ вместе с каждым полюсом $z=z_0$ обладает и полюсом $z=z_0^{-1}$. Таким образом, рациональная функция $h$ представима в виде отношения двух полиномов $S(z)=\sum_{n=-l}^l s_nz^{-n}$ и $Q(z)=\sum_{n=-m}^m q_nz^{-n}$ с симметричными последовательностями коэффициентов $s_{-n}=s_n$ и $q_{-n}=q_n$, а значит, инвариантных относительно замены переменной $z\to z^{-1}$. \par В нечетном случае, домножив $h$, если нужно, на подходящую целую степень переменной $z$, получим $h_n=h_{1-n}$ для всех $n=1,2,\dots$. Ясно, что функция $f(z)=(1+z)h(z)$ имеет симметричную последовательность лорановских коэффициентов. Последовательность лорановских коэффициентов функции $f(z)/((1+z)(1+z^{-1}))$ симметрична, а сама эта функция является рациональной и представима в виде $S(z)/Q(z)$, где $S$ и $Q$ --- лорановские полиномы с симметричными последовательностями коэффициентов, инвариантные относительно замены $z\mapsto z^{-1}$. Таким образом, $$ h(z)=\frac{(1+z^{-1})S(z)}{Q(z)}. $$ \par Покажем, что фильтры $h$ и $\tilde h$ могут иметь разноименную четность, т.е., когда одна функция соответствует четному случаю, а другая --- нечетному, лишь для пары фильтров $h(z)=(1+z^{-1})/\sqrt{2}$ и $\tilde h(z)=\sqrt{2}$. Несмотря на то, что данная пара фильтров приводит к двум КМА, порожденным соответственно базисом Хаара и базисом, состоящим из сдвигов $\delta$-функции, ввиду разрывности хааровских функций эти базисы не образуют биортогональной пары. \par Из (2.7) для произвольной пары $h$ и $\tilde h$ получим, что $$ h(z)\tilde h(z^{-1})+h(-z)\tilde h(-z^{-1})=2 $$ или, подставляя представление $h(z)$ и $\tilde h(z)$ в виде рациональных функций и сокращая при необходимости общие множители числителя и знаменателя, получим выражение вида $$ \frac{A(z)}{B(z)} + \frac{A(-z)}{B(-z)}=2,\tag3.1 $$ где $A$, $B$ --- лорановские полиномы от $z$. Слагаемые в (3.1) должны иметь общие с учетом кратности полюсы. Отсюда, в частности, следует, что полиномы $B(z)$ и $B(-z)$ имеют одни и те же нули. Таким образом, получим, что в полиноме $B$, по крайней мере после домножения в случае необходимости на подходящий множитель $z^k$, присутствуют лишь четные степени, т.е. $B(z)=\Cal B(z^2)$, где $\Cal B(z)$ --- некоторый лорановский полином. При этом уравнение (3.1) можно переписать в виде $$ {A(z)} + {A(-z)}=2{\Cal B(z^2)}.\tag3.2 $$ Последнее уравнение является простым источником всех возможных КМА. В самом деле, из уравнения (3.2) видно, что лорановский полином $A$ может быть выбран в определенной степени произвольно. %Поскольку $B(z)\not\equiv0$, то можно В качестве $A_e(z)=\Cal B(z)$ можно взять произвольный лорановский полином, не имеющий корней на единичной окружности $|z|=1$. При этом, поскольку $A(-1)=m_0(\pi)\overline{\tilde m_0(\pi)}=0$, полином $A_o$ должен удовлетворять равенству $A_o(1)=A_e(1)$, т.е. должны совпадать суммы коэффициентов полиномов $A_o$ и $A_e$. Все возможные биортогональные фильтры $h$ и $\tilde h$ получаются факторизацией $h(z)\tilde h(z^{-1})=A(z)/B(z)$, где $h(1)=\tilde h(1)=\sqrt{2}$. Разумеется, не все факторизации приводят к биортогональным парам базисов всплесков, однако все такие пары базисов порождаются этими факторизациями. \par Предположим теперь, что одна из функций $h$ и $\tilde h$ порождает четный КМА, а другая --- нечетный. Тогда справедливо представление $A(z)=(1+z^{-1})\Cal A(z)$, где $\Cal A(z)$ --- лорановский полином с симметричной последовательностью коэффициентов. Подставляя это представление в (3.2), получим $$ {(1+z^{-1})\Cal A(z)} + {(1-z^{-1})\Cal A(-z)}=2{\Cal B(z^2)},\tag3.3 $$ где без ограничения общности можно считать, что полиномы $\Cal A$ и $\Cal B$ не имеют общих нулей. Правая часть равенства (3.3) инвариантна относительно замены переменной $z\to z^{-1}$, поскольку она является произведением полиномов, обладающих этим свойством. Значит, и левая его часть инвариантна относительно такой замены. Следовательно, $$ {(1+z^{-1})\Cal A(z)} + {(1-z^{-1})\Cal A(-z)}= {(1+z)\Cal A(z^{-1})} + {(1-z)\Cal A(-z^{-1})}. $$ А поскольку $\Cal A(z)=\Cal A(z^{-1})$, то последнее равенство преобразуется к виду $$ (z^{-1}-z)(\Cal A(z) - \Cal A(-z))=0, $$ что означает отсутствие у многочлена $\Cal A$ нечетных степеней. Но тогда, вернувшись к (3.3), увидим, что $\Cal A(z)=\Cal B(z^2)$. А значит, ввиду отсутствия у этих многочленов общих делителей имеем $\Cal A\equiv 1$. Данному случаю соответствует биортогональная пара фильтров $h(z)=(1+z^{-1})/\sqrt{2}$ и $\tilde h(z)=\sqrt{2}$. %Однако такой вывод противоречит предположению, что функции $h$ и $\tilde h$ %порождают КМА, а потому обе делятся на $1+z^{-1}$. Отсюда ясно, что %полином $A$ делится на $(1+1/z)(1+z)$, а полином $\Cal A$ должен делиться %на $1+z$. Таким образом, $h$ и $\tilde h$ могут обладать разной четностью лишь для приведенного выше тривиального случая, который не порождает биортогональные базисы всплесков. \par Итак, рассмотрим четные и нечетные биортогональные пары с малыми порядками числителя и знаменателя функций $h$ и $\tilde h$. Начнем с нечетного случая. Самая простая правая часть в (3.2) может быть представлена в виде $\Cal B\equiv 1$. На первый взгляд, этот случай может показаться вырожденным, соответствующим биортогональным базисам с компактным носителем. Тем не менее, могло оказаться, что число, бывшее корнем одной из функций $h(z)$ и $\tilde h(z^{-1})$ оказалось полюсом другой функции. Тогда соответствующие множители в произведении $h(z)\tilde h(z^{-1})$ сократятся и потому никак не будут учтены в (3.1). Специфика КМА вынуждает нас рассматривать не все решения уравнения (3.2). Главное из ограничений заключается в том, что поскольку для нечетного случая $h(-1)=\tilde h(-1)=0$, то $A(z)= (1+z)(1+z^{-1})\Cal A_1(z)$. Таким образом, многочлен $\Cal A_1(z)$ минимально возможной степени равен константе, $\Cal A_1(z)\equiv 1/2$. А учитывая, что рациональные функции $h(z)/(1+z^{-1})$ и $\tilde h(z)/(1+z^{-1})$ имеют симметричные последовательности лорановских коэффициентов, получим, что биортогональная рациональная пара фильтров минимально возможного порядка имеет вид $$ h(z)=\alpha\frac{1+z^{-1}}{\sqrt{2}(z^{-1}+a+z)},\qquad \tilde h(z)=\frac{1}{\sqrt{2}\alpha}(1+z^{-1})(z^{-1}+a+z), $$ где $\alpha=2+a$ --- множитель, который обеспечивает нормировку $h(1)=\tilde h(1)=\sqrt2$. \par Для теории всплесков интерес представляет лишь случай $|a|>2$. В самом деле, полином $1+az+z^2$ имеет корни $z_{1,2}=-\frac{a}{2}\pm\sqrt{\frac{a^2}{4}-1}$. При $|a|\le 2$ оба корня равны по модулю единице, т.е. $z_{1,2}=e^{\pm i\omega_0}$. Следовательно, в этом случае функция $m_0(\omega)$ имеет особенности в точках $\omega=\pm\omega_0$ и не только несуммируема, но и не является даже распределением. \par Рассмотренный пример показывает, как можно варьировать имеющиеся КМА (в нашем случае КМА, порожденные базисами Хаара) путем введения дополнительного множителя $z^{-1}+a+z$ в знаменатель одного из фильтров $h$, $\tilde h$ и того же множителя --- в числитель другого. С качественной точки зрения этот прием ведет к "перекачке гладкости" из одного базиса биортогональной пары в двойственный ему базис при сохранении суммарной гладкости базисов. Такой прием может быть использован для варьирования любой биортогональной пары, и это следует иметь в виду, хотя мы о нем далее упоминать не будем. \par Теперь рассмотрим менее тривиальный случай, когда полином $\Cal B$ невырожден. В простейшем случае $\Cal B(z)=z^{-1}+a+z$. По приведенным выше причинам здесь также имеем $|a|>2$. При этом получаем, что удовлетворяющий (3.2) полином $\Cal A_1$ минимально возможной степени имеет вид $\Cal A_1(z)=z^{-1}+(\frac{a}{2}-1)+z$. Таким образом, существует две биортогональные пары, соответствующие данному выбору полинома $\Cal B$: $$ h(z)=\sqrt{2}\frac{(1+z^{-1})(z^{-1}+(\frac{a}{2}-1)+z)}% {z^{-2}+a+z^2},\qquad \tilde h(z)=\frac{1+z^{-1}}{\sqrt{2}} $$ и $$ h(z)=\alpha\frac{(1+z^{-1})}% {z^{-2}+a+z^2},\qquad \tilde h(z)=\frac{(1+z^{-1})(z^{-1}+(\frac{a}{2}-1)+z)}{\alpha}, \text{ где } \alpha=\frac{a+2}{\sqrt{2}} $$ \par Рассмотрим теперь простейшие решения в четном случае. Поскольку в (3.1) $A(-1)=0$, то один из полиномов $h$ или $\tilde h$ имеет нуль в точке $z=-1$. А так как последовательность его коэффициентов симметрична, то кратность корня четна. Значит, полином $A(z)$ включает в себя множитель $z^{-1}+2+z$. Таким образом, в простейшем случае $A(z)=\frac12(z^{-1}+2+z)$, $\Cal B(z)\equiv1$, $$ h(z)=\sqrt2,\qquad \tilde h(z)=\frac{z^{-1}+2+z}{2\sqrt2}. $$ Данная пара КИХ-фильтров приводит к паре биортогональных КМА, первый из которых порождается сдвигами $\delta$-функции, а другой - сдвигами линейного B-сплайна. На первый взгляд, может показаться, что этот пример является вырожденным и не имеет перспективы найти применение в приложениях. В самом деле, "дефекты" этой пары состоят в том, что одно из пространств двойственной пары состоит из обобщенных функций, кроме того, функции базисов кусочно-линейных всплесков не имеют нулевого среднего. Второе свойство с общепринятой точки зрения кажется особенно неприятным, поскольку считается, что хорошие для аппроксимации (в частности для сжатия информации) базисы должны иметь много нулевых моментов или, что то же самое, полином $h(z)$ должен иметь высокую кратность нуля в точке $z=-1$. Тем не менее, оказывается, что в большинстве случаев использование этой пары базисов для сжатия изображений приводит к б\'ольшим коэффициентам сжатия, чем использование вполне благополучных хааровских базисов. Учитывая высокую вычислительную эффективность этих базисов, можно предположить, что они вполне могут быть востребованы в приложениях. \par Рассмотрим теперь случай, когда $\Cal B(z)=z^{-1}+a+z$. Для выбранного ранее полинома $\Cal A_1$ возможны четыре варианта четной факторизации $h(z)\tilde h(z^{-1})=(z^{-1} +2+z)\Cal A_1(z)$: $$ h(z)=\frac{(z^{-1} +2+z)(z^{-1} +(\frac{a}2-1)+z)}{\sqrt{2}(z^{-2}+a+z^2)},\qquad \tilde h(z)=\sqrt{2};% \text $$ $$ h(z)=\frac{(a+2)(z^{-1} +2+z)}{2\sqrt{2}(z^{-2}+a+z^2)},\qquad \tilde h(z)=2\sqrt{2}\frac{z^{-1} +(\frac{a}2-1)+z}{a+2};% \text $$ $$ h(z)=\frac{z^{-1} +2+z}{2\sqrt{2}},\qquad \tilde h(z)=2\sqrt{2}\frac{z^{-1} +(\frac{a}2-1)+z}{z^{-2}+a+z^2};% \text $$ $$ h(z)=\frac{(z^{-1} +(\frac{a}2-1)+z)(z^{-1} +2+z)}{\sqrt{2}(a+2)},\qquad \tilde h(z)=\frac{\sqrt{2}(a+2)}{z^{-2}+a+z^2}. $$ Заметим, во всех четырех случаях $\tilde h(-1)\ne0$. \par Ясно, что для выполнения соотношения $h(-1)=\tilde h(-1)=0$ в четном случае приходится потребовать, чтобы полином $A(z)$ в (3.2) имел в точке $-1$ нуль по крайней мере четвертого порядка. Таким образом, справедливо представление $A(z)= (1+z)^2(1+z^{-1})^2\Cal A_2(z)$. Пусть снова $\Cal B(z)=z^{-1} + a +z$. Тогда, решая уравнение (3.2) для $\Cal A_2(z)$ вида $bz^{-1}+c+bz$, получим, что $$ \Cal A_2(z)=\frac{6-a}{16}z^{-1}+\frac{a-2}{4}+\frac{6-a}{16}z, $$ где, как и ранее, $|a|>2$. Таким образом, полагая $b=\frac{6-a}{16}$, $c=\frac{a-2}{4}$, получим две различные биортогональные пары $$ h(z)=\frac{2(z^{-1}+2+z)(bz^{-1}+c+bz)}% {\sqrt{2}(z^{-2}+a+z^2)},\qquad \tilde h(z)=\frac{z^{-1}+2+z}{2\sqrt{2}}\tag3.4 $$ и $$ h(z)=\frac{4(z^{-1}+2+z)(bz^{-1}+c+bz)}{\sqrt{2}(a+2)},\quad \tilde h(z)=\frac{\sqrt{2}(a+2)(z^{-1}+2+z)}{4(z^{-2}+a+z^2)}.\tag3.5 $$ \par Формулы (3.4) и (3.5) имеют два важных частных случая, когда алгоритмы разложения по всплескам значительно упрощаются. Первый из этих случаев $a=6$ приводит нас к упрощенной биортогональной паре $$ h(z)=\frac{z^{-1}+2+z}{2\sqrt{2}}. \qquad \tilde h(z)=\frac{2\sqrt{2}(z^{-1}+2+z)}% {z^{-2}+6+z^2}, $$ \par Второй случай при предельном переходе $a\to\infty$ приводит к известной (см. [2], [4, с. 277]) биортогональной паре базисов с компактным носителем, определяемой функциями $$ h(z)=\frac{(z^{-1}+2+z)(-z^{-1}+4-z)}% {4\sqrt{2}},\qquad \tilde h(z)=\frac{z^{-1}+2+z}{2\sqrt{2}}. $$ Наконец, еще две важные пары фильтров получаются при $a=10/3$. При данном значении параметра $a$ получаются фильтры, имеющие максимальную суммарную кратность нуля в точке $-1$, равную 6. Фильтры (3.4) трансформируется при этом в фильтры $$ h(z)=\frac{\sqrt{2}(z^{-1}+2+z)^2}% {3z^{-2}+10+3z^2},\qquad \tilde h(z)=\frac{z^{-1}+2+z}{2\sqrt{2}} $$ а (3.5) --- в фильтры $$ h(z)=\frac{(z^{-1}+2+z)^2}{8\sqrt{2}},\qquad \tilde h(z)=\frac{4\sqrt{2}(z^{-1}+2+z)}{3z^{-2}+10a+3z^2}. $$ \par Заметим, что кроме двух пар (3.4) и (3.5) в данном случае существует еще четыре различных факторизации, у которых один из фильтров $h$ или $\tilde h$ не имеет нуля в точке $-1$. %****************************************** \head \S4. Метод лифтинга. \endhead %****************************************** Наибольший прогресс в проблеме ускорения работы алгоритмов разложения функций по базисам всплесков и их восстановления по коэффициентам разложения связан с так называемой лифтинг-схемой, принявшей завершенный вид в работе [3]. Близкие идеи были реализованы в [6] и [15]. Именно на подход, рассмотренный в последней работе [6] мы и будем здесь опираться. \par Введем необходимые обозначения. Пусть $\Pi(z)$ --- лорановский полином $\Pi(z)=\sum_{n=k_1}^{k_2} p_nz^n$, где $k_1,k_2\in\z$, тогда $l(\Pi)\dfn k_1$, $u(\Pi)\dfn k_2$, $L(\Pi)\dfn p_{l(\Pi)}$, $U(\Pi)\dfn p_{u(\Pi)}$. Величину $d(\Pi)\dfn u(\Pi)-l(\Pi)$ будем называть порядком полинома $\Pi$. \par Сначала мы рассмотрим случай, когда каждая из рациональных функций $h$ и $\tilde h$ не имеет нулей, являющихся полюсами другой функции. В этом случае, как было показано в предыдущем, параграфе знаменатели этих функций являются лорановскими полиномами от $z^2$, что позволяет записать компоненты полифазной матрицы $P$ в виде: $$ h_e(z)=\frac{E_1(z)}{Q_1(z)},\quad h_o(z)=\frac{O_1(z)}{Q_1(z)},\quad g_e(z)=\frac{E_2(z)}{Q_2(z)},\quad g_o(z)=\frac{O_2(z)}{Q_2(z)}.\tag4.1 $$ Равенство единице определителя полифазной матрицы влечет выполнение соотношения $$ \det\left(\matrix E_1(z)&E_2(z)\\O_1(z)&O_2(z)\endmatrix\right)=Q_1(z)Q_2(z). \tag4.2 $$ Отсюда ясно, что справедливы два неравенства $$ \Cal L(P)\dfn l(Q_1Q_2)-\min \{l(E_1O_2), l(O_1E_2)\}\ge0 ; $$ $$ \Cal U(P)\dfn \max \{u(E_1O_2), u(O_1E_2)\}- u(Q_1Q_2)\ge0. $$ Число $\Cal D(P)\dfn\Cal L(P)+\Cal U(P)$ назовем {\it дефектом} матрицы $P$. \par Матрицы вида $$ T^+(k,a)=\left(\matrix 1&az^{k}\\0&1\endmatrix\right),\qquad T^-(m,b)=\left(\matrix 1&0\\ bz^{m}&1\endmatrix\right), $$ где $a,b\in\R$; $k,m\in\z$ будем называть {\it элементарными лифтингами}. \proclaim{Теорема 1} Любая полифазная матрица $P$ с рациональными компонентами вида (4.1) может быть представлена в виде $$ P(z)=P_0 (z)T^{\sigma(1)}(k_1,a_1)T^{\sigma(2)}(k_2,a_2)\dots T^{\sigma(\Cal D(P))}(k_{\Cal D(P)},a_{\Cal D(P)}),\tag4.3 $$ где $P_0(z)$ --- матрица с нулевым дефектом, $k_i\in\z$, $a_i\in\R$, $\sigma(i)$ --- подходящим образом выбранный знак; $i=1,2,..., \Cal D(P)$. \endproclaim \remark{Замечание 1} В формулировке теоремы 1 не утверждается, что все элементарные лифтинги в (4.3) невырождены, некоторые из них могут быть равны единичной матрице. \endremark \remark{Замечание 2} Факторизация (4.3) определяется не единственным образом. \endremark \demo{Доказательство теоремы 1} Для доказательства теоремы нам достаточно показать, что любая полифазная матрица с ненулевым дефектом $P$ может быть представлена в виде $P(z)=P^\prime (z)T^{\sigma}(k,a)$, где $\Cal D(P^1)<\Cal D(P)$. \par Сначала докажем следующее вспомогательное утверждение \proclaim{Лемма 1} Если для полифазной матрицы $P(z)$ с рациональными компонентами вида (4.1) справедливо неравенство $\Cal L(P)>0$ (или $\Cal U(P)>0$), то $l(E_1)+l(O_2)=l(E_2)+l(O_1)$ (или $u(E_1)+u(O_2)=u(E_2)+u(O_1)$) и определитель матрицы $$ A=\left(\matrix L(E_1)z^{l(E_1)}&L(E_2)z^{l(E_2)}\\ L(O_1)z^{l(O_1)}&L(O_2)z^{l(O_2)} \endmatrix\right)\quad \left(\text{ или } B=\left(\matrix U(E_1)z^{u(E_1)}&U(E_2)z^{u(E_2)}\\ U(O_1)z^{u(O_1)}&U(O_2)z^{u(O_2)} \endmatrix\right)\right) $$ равен нулю. \endproclaim \demo{Доказательство Леммы 1} В случае невыполнения равенства $l(E_1)+l(O_2)=l(E_2)+l(O_1)$ мы вошли бы в противоречие с равенством (4.2), поскольку минимальная степень в левой части равнялась бы $\min \{l(E_1O_2),l(E_2,O_1)\}$, что по условию леммы меньше минимальной степени правой части равенства (4.2). \par По той же причине определитель матрицы $A$ равен нулю, поскольку в противном случае минимальная степень полинома в левой части (4.2) была бы меньше минимальной степени правой части. \par Утверждение относительно матрицы $B$ доказывается аналогичным образом. \enddemo Вернемся к доказательству Теоремы 1. \par Пусть для определенности $\Cal L(P)>0$. Тогда из Леммы 1 получим $$ l(E_1)+l(O_2)=l(E_2)+l(O_1).\tag4.4 $$ Для определенности также будем предполагать, что $$d(E_1)\le d(O_1).\tag4.5 $$ \par Рассмотрим два случая: 1) $\Cal U(P)>0$; 2) $\Cal U(P)=0$. \par В первом случае согласно Лемме 1 имеем $u(E_1)+u(O_2)=u(E_2)+u(O_1)$. Вычитая отсюда (4.4), получим $d(E_1)+d(O_2)=d(E_2)+d(O_1)$, что в совокупности с (4.5) дает $d(E_2)\le d(O_2)$. Таким образом, выполнив преобразование $E_1^\prime(z)=E_1(z)$, $E_2^\prime(z)=E_2(z)$, $O_1^\prime(z)=O_1(z)-a z^k E_1(z)$, $O_2^\prime(z)=O_2(z)-a z^k E_2(z)$, где $a=L(O_1)/L(E_1)$, $k=l(O_1)-l(E_1)$, учитывая равенство нулю определителя матрицы $A$, получим, что $l(O_1^\prime)=l(O_1)+1$, $l(O_2^\prime)=l(O_2)+1$. В то же время, справедливы неравенства $u(O_1^\prime)\le u(O_1)$, $u(O_2^\prime)\le u(O_2)$ Следовательно, дефект матрицы $$ P^\prime (z) \dfn P (z)\left (\matrix 1 &-az^k \\0&1\endmatrix\right) \tag4.6 $$ строго меньше дефекта матрицы $P$. Что и требовалось доказать. \par Пусть теперь $\Cal U(P)=0$. Покажем, что преобразование (4.6) понижает дефект матрицы $P$ по крайней мере на единицу. Если $d(E_2)\le d(O_2)$, то приведенные выше рассуждения остаются в силе. Рассмотрим случай $d(E_2)>d(O_2)$. Поскольку после преобразование (4.6) имеем $\Cal L(P')\le\Cal L(P)-1$, то нам остается доказать неизменность величины $\Cal U(P)$. Нетрудно видеть, что $u(O_2^\prime)=u(E_2)+k$ и $u(O_1^\prime)\le u(O_1)$. Таким образом, $u(E_2O_1^\prime)\le u(E_2O_1)$ и $u(E_1O_2^\prime)=u(E_1)+u(E_2)+k\le u(O_1)+u(E_2)=u(E_2O_1)$. Следовательно, $$ \multline \Cal U(P')=\max\{u(E_1O'_2), u(O'_1E_2)\}- u(Q_1Q_2)\le\\ \max\{u(E_1O_2), u(O_1E_2)\}- u(Q_1Q_2)=\Cal U(P)=0. \endmultline $$ Таким образом, $\Cal D(P^\prime)\le\Cal D(P)-1$. \par В заключение доказательства Теоремы 1 отметим, что в случае, когда $d(E_1)>d(O_1)$ следует применить элементарный лифтинг, являющийся верхней треугольной матрицей. \enddemo \par Как будет показано в \S 5, реализация алгоритмов опирающаяся на факторизацию, гарантированную Теоремой 1, имеет двукратный асимптотический выигрыш в вычислительных затратах при фиксированных степенях знаменателей $h(z)$ и $\tilde h(z)$ и степени хотя бы одного из числителей, стремящейся к бесконечности, при условии, что обе функции $h(z)$ и $\tilde h(z)$ имеют общий вид, т.е. среди коэффициентов их числителей между максимальной и минимальной степенью нет нулей или их относительно мало. \par Однако на практике чаще всего приходится иметь дело со всплесками, которые с точностью до сдвига аргумента являются четными или нечетными функциями. Именно такие примеры были рассмотрены в \S 2. \par К сожалению, для последовательностей $h_n$ и $\tilde h_n$, симметричных относительно полуцелых точек, нам не удалось найти лифтинг-реализацию, учитывающую симметрию. Важность этой задачи очевидна, поскольку такие последовательности определяют базисы нечетных всплесков (простейшим примером таких функций являются всплески Хаара). \par Рассмотрим случай четных всплесков. О возможности учета симметрии при реализации лифтинг-схемы, когда $h(z)$ и $\tilde h(z)$ --- лорановские полиномы есть упоминание (без доказательства) в [3]. Там же для всех примеров, соответствующих четному случаю, приведена лифтинг-реализация с учетом четности. \par Проблема здесь состоит в том, что когда $h(z)=S(z)/Q(z)$, где $S$, $Q$ --- лорановские полиномы, для которых, $S(1/z)=S(z)$, $Q(1/z)=Q(z)$, при реализации формул (2.8) или (2.9) можно сэкономить на учете симметрии числителя, воспользовавшись формулой $$ c^{-1}_k=h_0c^0_{2k} +\sum_{m=1}^M h_m(c^0_{2k+m}+c^0_{2k-m}), $$ где $2M=d(S)$. Асимптотически при больших $m$ при учете симметрии количество операций равно $3/4$ числа операций, необходимых в общем случае. Естественно, хотелось бы при лифтинг-реализации дополнительно к двукратному выигрышу получить еще такой же дополнительный выигрыш в арифметических затратах. \par Итак, будем считать, что обе рациональные функции $h(z)$ и $\tilde h(z)$ имеют последовательности лорановских коэффициентов, симметричные относительно коэффициента с нулевым индексом. Тогда без ограничения общности то же можно сказать и о полиномах $E_1$, $E_2$, $O_1$, $O_2$ в обозначениях (4.1). Тогда имеет место \proclaim{Теорема 2} Пусть полифазная матрица $P(z)$ имеет рациональные компоненты вида (4.1), порожденные последовательностями $h_n=h_{-n}$, $\tilde h_n=\tilde h_{-n}$. Тогда матрица $P(z)$ имеет четный дефект и может быть представлена в виде $$ P (z) =P_0 (z)\left (\prod_ {i=1} ^ {\Cal D (P) /2} T^ {\sigma (i)} (\sigma (i) k_i, a_i) T^ {\sigma (i)} ((-1) \cdot\sigma (i) (k_i + 1), a_i) \right) , $$ где $P_0(z)$ --- матрица с нулевым дефектом, $k_i\in\Bbb N\cup {0}$, $a_i\in\R$, $\sigma(i)$ --- подходящим образом выбранный знак. \endproclaim \demo{Доказательство теоремы 2} Покажем сначала, что дефект матрицы $P(z)$ является четным числом. В самом деле, из симметрии коэффициентов нетрудно получить, что $l(E_1)=-u(E_1)$, $l(O_1)=1-u(O_1)$, $l(O_2)=-u(O_2)$, $l(E_2)=-1-u(E_2)$. Следовательно, $l(E_1O_2)=-u(E_1O_2)$ и $l(E_2O_1)=-u(E_2O_1)$, кроме того $l(Q_1Q_2)=-u(Q_1Q_2)$. Поэтому $\Cal L(P)=\Cal U(P)$, что влечет $\Cal D(P)=2\Cal L(P)=2\Cal U(P)$. \par Таким образом, нам остается показать, что любую матрицу $P(z)$ с ненулевым дефектом, удовлетворяющую условиям теоремы 2, можно представить в виде $$ P(z)= P_1(z)T^{\sigma}(\sigma k,a)T^{\sigma}((-1)\cdot\sigma(k+1),a), %\tag4.3 $$ где $P_1$ --- матрица, также удовлетворяющая условиям теоремы 2. \par Поскольку $\Cal L(P)= \Cal U(P)>0$, то согласно Лемме 1 имеем $l(E_1)+l(O_2)=l(E_2)+l(O_1)$ и $u(E_1)+u(O_2)=u(E_2)+u(O_1)$, причем определители матриц $$ A=\left(\matrix L(E_1)&L(E_2)\\ L(O_1)&L(O_2) \endmatrix\right),\quad B=\left(\matrix U(E_1)&U(E_2)\\ U(O_1)&U(O_2) \endmatrix\right) $$ равны нулю. Ввиду симметрии последовательностей $h_n$ и $\tilde h_n$ имеем $A=B$. Ввиду того, что $d(E_1)$ и $d(O_2)$ --- четные числа, а $d(O_1)$ и $d(E_2)$ --- нечетные, имеет место либо выполнение неравенств: а) $d(E_1)>d(O_1)$, $d(E_2)>d(O_2)$, либо выполнение неравенств б) $d(E_1)