Глава 6. Ортонормированные базисы вейвлетов с компактным носителем

Как результат ортогонализации (5.3.3), все примеры ортонормированных базисов вейвлетов в предыдущей главе, за исключением базиса Хаара, состояли из функций с бесконечным носителем. Чтобы построить ортонормированные примеры, в которых имеет компактный носитель, стоит начать с функции (или, что то же, со схемы субполосной фильтрации — см. § 5.6), а не с функции или пространств . В § 6.1 мы показываем, как построить такую то, что выполняются (5.1.20) и (5.5.5) для некоторого (необходимое условие, чтобы иметь определенную регулярность ). Однако не каждая такая то связана с ортонормированным базисом вейвлетов, что обсуждается в §§ 6.2 и 6.3. Главные результаты этих двух частей суммированы в теореме 6.3.6 в конце § 6.3. Параграф 6.4 содержит примеры вейвлетов с компактными носителями, порождающих ортонормированные базисы. Полученные таким образом ортонормированные базисы вейвлетов, вообще говоря, нельзя записать в аналитической форме. Их график можно вычислить с произвольной точностью с помощью алгоритма, который я называю «каскадным алгоритмом» (cascade algorithm), который фактически является «уточняющей схемой» (refinement schemes), принятой в компьютерном дизайне. Все это обсуждается в § 6.5.

Большая часть материала восходит к работе Добеши ([53]) 1988 года. С тех пор для большинства результатов были найдены лучшие, более простые или более общие доказательства, и я отдаю предпочтение этому новому видению вещей. Эти различные подходы позаимствованы, в основном, у Малла ([132]), Коэна ([35]), Лоутона ([121], [122]), Мейера ([142]) и Коэна, Добеши, Фово ([41]). Связь с масштабирующим уравнением (refinement equation) обсуждается Кавареттой, Даменом и Мичелли в [29], Дин и Левиным [73], а также в более ранних работах этих авторов (см. § 6.5).

6.1. Построение m0

В этой главе нас в основном интересует построение вейвлетов с компактными носителями. Самым легким способом обеспечить компактный носитель для вейвлета является выбор масштабирующей функции с компактным носителем (в ортогонализованной версии). Тогда из определения

следует, что лишь конечное число не равняется нулю, так что сводится к конечной линейной комбинации функций с компактными носителями (см. (5.1.34)) и, таким образом, автоматически сама имеет компактный носитель. Выбирая с компактными носителями, получаем то преимущество, что в соответствующей схеме субполосной фильтрации (см. § 5.6) используются только КИХ-фильтры.

Для с компактным носителем -периодическая функция

превращается в тригонометрический полином. Как показано в главе 5 (см. (5.1.20)), ортонормированность влечет выполнение равенства

«почти всюду» здесь опущено, поскольку то обязательно является непрерывной, значит, (6.1.1) выполняется для всех , если это верно .

Нас также интересует, как сделать достаточно регулярными. В силу следствия 5.5.4 это означает, что то должна быть вида

где и — тригонометрический полином. Заметим, что даже без ограничений на регулярность нам нужно разложение (6.1.2), где по крайней мере равно I. Совмещая (6.1.1) и (6.1.2), получаем, что мы ищем полином по

удовлетворяющий уравнению

и

где также полином по Для наших целей удобно переписать в виде полинома по

В терминах Р уравнение (6.1.4) становится условием

которое должно выполняться для всех , а значит, для всех Для разрешения (6.1.7) относительно Р воспользуемся теоремой Безу.

Теорема 6.1.1. Если — два полинома степени соответственно, без общих нулей, то существуют единственные полиномы степени соответственно, такие, что

Доказательство.

1. Сначала докажем существование, а несколько позже и единственность. Мы можем предположить, что (перенумеровав при необходимости). Так как мы можем найти такие полиномы что и

2. Аналогично мы можем найти такие что и

Повторяем эту процедуру, при этом играет роль в последнем уравнении, а роль

Поскольку строго убывает, процесс должен остановиться на некотором шаге, что возможно, лишь если для некоторого где ,

3. Поскольку

является делителем и для тоже. По индукции является делителем и для всех предыдущих тогда — делитель для Поскольку не имеют общих нулей, то — константа, отличная от нуля.

4. Итак, мы получаем

По индукции

где Снова по индукции имеем, что Для находим

где (Мы использовали то, что если бы равнялась 0, то равнялось бы 0.) Следовательно, — решения (6.1.8), удовлетворяющие требуемым ограничениям на степени.

5. Осталось установить единственность. Допустим, что — две пары решений (6.1.8), для обеих выполнены ограничения на степень. Тогда

Поскольку не имеют общих нулей, каждый ноль является нулем кратности, по крайней мере, не меньшей. Неравенство означает, что а это невозможно, поскольку Отсюда Из этого немедленно следует, что

Замечание.

1. Для дальнейшего удобства (глава 8) мы сформулировали теорему Безу в более общем виде, чем это необходимо в данной главе. На самом деле ее утверждение выполняется даже при более общих условиях: для имеющих общие нули, (6.1.8) по-прежнему разрешимо, если его правая часть делится на наибольший общий делитель Доказательство остается таким же, теперь лишь является а не константой. Доказательство представляет нечто иное, как построение по алгоритму Евклида. Он работает и во многих других областях, помимо полиномов.

2. Из конструкции ясно, что если имеют лишь рациональные коэффициенты, такими же будут и коэффициенты Это используется в главе

Теперь применим этот результат к имеющейся проблеме, т. е. к уравнению (6.1.7). В силу теоремы 6.1.1 существуют единственные полиномы степени такие, что

Подставляя 1 — у вместо у в (6.1.9), приходим к соотношению

при этом единственность дает Следовательно, — решение (6.1.7). В этом случае мы можем найти в явном виде, даже не используя алгоритм Евклида:

где мы выписали в явном виде первые членов разложения Тейлора для Так как совпадает со своим разложением Тейлора, оборванным после члена, или

Этим дается явное решение (6.1.7). (К счастью, при оно положительное, а значит, является хорошим кандидатом на роль Это единственное решение, имеющее самую низкую степень, мы обозначим через Однако существует много решений более высоких степеней. Для каждого такого решения мы имеем

Отсюда получаем, что делится на

Более того,

т. е. Р — антисимметричен по отношению к Все наши открытия соберем в

Предложение 6.1.2. Тригонометрический полином вида

удовлетворяет (6.1.1) тогда и только тогда, когда может быть записан в форме

где

а

— нечетный полином, выбранный так, чтобы для .

Это предложение полностью характеризует Для наших целей нам необходима все-таки то, а не Как же мы «извлечем квадратный корень» из L? Здесь нам на помощь приходит лемма Рисса (см. Пойа, Сеге [155]).

Лемма 6.1.3. Пусть А будет положительным тригонометрическим полиномом, инвариантным под действием подстановки , т. е. А обязательно имеет вид

Тогда существует тригонометрический полином В степени М. т. е.

такой, что

Доказательство.

1. Мы можем записать , где — полином степени М с вещественными коэффициентами. Этот полином можно разложить на множители

где нули появляются либо комплексными парами либо поодиночке в вещественном виде. Мы также можем написать

где — полином степени . Для мы имеем

таким образом, полиномы в левой и правой части совпадают на всей плоскости С.

2. Если — вещественный, то корнями — являются При это два вещественных нуля (вырождающихся, если вида При два корня являются комплексно сопряженными, равными 1 по абсолютной величине,

т. е. вида Поскольку такие нули соответствуют «физическим» нулям А (т. е. значениям для которых ). Чтобы не прийти к противоречию с эти нули должны иметь четную кратность.

3. Если — не вещественный корень, то мы рассматриваем его вместе с Полином — имеет четыре нуля Легко проверяется, что все четыре нуля различны и образуют четверку

4. Таким образом, мы имеем

где перегруппированы три различных вида нулей.

5. Для на единичном круге мы имеем

Следовательно,

где

очевидно является тригонометрическим полиномом степени М с вещественными коэффициентами.

Замечание.

1. Это доказательство является конструктивным. В нем используется разложение полинома степени М на множители, что, однако, должно делаться численным образом и может привести к проблемам, если М велико и некоторые из нулей близки друг другу. Заметим, что в отличие от других процедур, в которых на множители раскладывается непосредственно полином степени в этом доказательстве нам нужно раскладывать на множители полином всего лишь степени М.

2. В технической литературе эта процедура «извлечения квадратного корня» также называется спектральной факторизацией.

3. Полином В — не единственный! Например, для нечетного М полином может иметь четверок комплексных нулей и одну пару вещественных нулей. В каждой четверке мы можем выбирать, оставить ли в В пару или же . В каждой паре мы можем выбрать либо либо Так получаем уже различных вариантов для В. Кроме того, мы всегда можем умножить В на егпп — произвольное из

Предложение 6.1.2 и лемма 6.1.3 говорят о том, как построить все возможные полиномы то, удовлетворяющие (6.1.1) и (6.1.2). До сих пор, однако, не ясно, приводит ли какой-нибудь из таких полиномов то к ортонормированному базису вейвлетов. На самом деле некоторые из них не обладают этим свойством. Это будет обсуждаться в двух следующих параграфах. Те читатели, которые хотели бы пропустить технические детали, могут найти главные результаты, сведенные в теорему 6.3.6 в конце § 6.3.