Всплесковое разложение для функций на дифференцируемом многообразии

Ю. К. Демьянович

ВСПЛЕСКОВОЕ РАЗЛОЖЕНИЕ ДЛЯ ФУНКЦИЙ НА ДИФФЕРЕНЦИРУЕМОМ МНОГООБРАЗИИ*

Вэйвлетные (всплесковые) разложения, связанные с равномерной сеткой, широко известны (см., например, [1-4] и имеющуюся там библиографию). Для неравномерной сетки вэйвлеты рассматривались в работах [5-8]. Обработка числовых потоков, ассоциированных с гладким многообразием, возможна с использованием локальных функций (см. [9]), однако, создание эффективных алгоритмов требует привлечения аппарата вэйвлетных разложений.

Цель данной работы — представить схему построения вэйвлетов с использованием аппроксимационных соотношений: дать условия вложенности пространств локальных функций, построить вэйвлетное разложение и соответствующие формулы декомпозиции/реконструкции, оценить число операций в упомянутых формулах и порядок малости вэйвлетной составляющей через порядок аппроксимации.

Классические подходы к построению вэйвлетов связаны с использованием преобразования Фурье или с применением лифтинговой схемы (см. [1-4, 10-12]). В данной работе исходными являются аппроксимационные соотношения, что приводит к вэй-влетным разложениям с порядком аппроксимации асимптотически оптимальным по N -поперечнику стандартных компактов; при этом координатные вэйвлеты имеют компактный носитель минимальной (индексной) длины (при заданном порядке аппроксимации), и в ряде случаев представляют собой гладкие координатные сплайны, а получаемые вэйвлеты, в отличие от классических (см. [2], стр. 23), могут иметь ненулевое среднее значение. Отметим также, что порядок малости вэйвлетной составляющей равен упомянутому порядку аппроксимации, а при построении вэйвлетного разложения и формул декомпозиции/реконструкции не используются метрические свойства линейных пространств (свойства пространства Ь2(К1), кратно-масштабный анализ и т.п.); кроме того, коэффициент линейной зависимости сложности вычислений от количества исходных данных просто оценивается через порядок аппроксимации.

1. Покрытие для многообразия и его оснащение

Рассмотрим гладкое п-мерное многообразие М и его покрытие семейством подмножеств 6 =£ {&^, гомеоморфных открытому п-мерному шару, считая, что граница каждого из них кусочно-гладкая, У= М, а J — не более, чем счетное упорядоченное множество.

Для каждой точки £ € М рассмотрим содержащее ее множество = р| е. .

Совокупность различных множеств при £ € М не более, чем счетна; в дальнейшем упомянутые множества обозначаем Ск, к € К, где К —конечное или счетное множество индексов. Справедливы соотношения П Ск" = 0 при к' = к", к', к" € К,

* Работа выполнена при финансовой поддержке РФФИ (гранты №07-01-451 и 07-01-00269).

© Ю. К. Демьянович, 2008

С1 (&j) = С1 ^иСкСе^, , С1 ^ик£К = С1 (М), где С1 означает замыкание. Пред-

полагая, что множества Ск гомеоморфны открытому п-мерному шару, совокупность С =£ {Ск | к € К} называем дроблением семейства 6, а множества Ск —клетками дробления.

Используя обозначение |М| для числа элементов множества М, для любого £ € М положим к =£ |{з | £ € 6^-}|. Если существует такое натуральное число к, что почти для всех точек £ € М справедливо равенство к = к, то семейство 6 называется к-накрывающим семейством (для М).

Множество векторов-столбцов А = {aj | з € 3, aj € Кк} называется оснащением к-накрывающего семейства 6, если почти для всех точек £ € М система векторов А(г) =£ {aj | £ € 6j} является базисом пространства . Матрицу (aj)jeJ из вектор-столбцов aj, расположенных в соответствии с порядком во множестве J, будем обозначать тем же символом А.

2. Вложенность пространств локальных функций

на гладком многообразии

Пусть X — некоторое линейное пространство функций на М (для определенности под X можно подразумевать одно из пространств Ш^(Ш) или СЯ(М), в > 0, д > 1). Рассмотрим вектор-функцию ^ : М ^ с компонентами из пространства X (здесь

к > 1, з =0,1, 2,..., к - 1, Ь € М).

Теорема 1. Пусть 6 — к-накрывающее (для М) семейство с оснащением А =£ {aj }jeJ. Тогда существует единственная система функций (вектор-столбец) ш(£) С=Е (шj(г)Ь^, удовлетворяющая почти везде аппроксимационным соотношениям

и>Т

Дальше под J подразумевается упорядоченное не более, чем счетное множество, а символ ^у означает j-ю компоненту вектора a.

Теорема 2. Если выполнены условия теоремы 1, а матрица ф = (pij)iЄJjЄJ

такова, что при А=£фтА существует система функций

сІ7(і) =£-у, для которой почти везде

и.1Т

то справедливо калибровочное соотношение

ІО = фй.

Предположим, что кроме семейства 6 на многообразии М имеется еще одно х-накрывающее (для 9Л) семейство подмножеств б=£{б:;'}^,е^ с оснащением А, £=£{Сд,/ | к' Е К} — его дробление. Пусть система функций (вектор-столбец) и(г) = почти везде удовлетвряет аппроксимационным соотношениям

иЗТ{Ь)А = у>

Теорема 3. Если А и А — оснащения семейств & и &, ср(Ь) — вектор-функция, с линейно независимыми компонентами на соответствующих клетках к (Е К., и к' (Е К., то полученные из соотношений (2.1) и (2-4) системы функций и ьЗ соответственно являются линейно независимыми системами, а если еще матрица ф=£ (ди1Т)Т удовлетворяет второму из соотношений (2.2), то справедливо калибровочное соотношение (2.3); здесь д = (з^)^е7 — система линейных функционалов (вектор-столбец), биортогопальная системен:

дйТ = 7,

-^=£ (^з,з ')] з 'е7 — единичная матрица.

3. Вэйвлетное разложение

Дальше предполагается, что система ш состоит из линейно независимых функций. Обозначим через д =£(g^)^eJ систему линейных функционалов (вектор-столбец), биор-тогональную системе ш,

д шТ = I,

где I = (<5,')*,*'е/ — единичная матрица.

Рассмотрим пространства § =£/^({й;*}^/) и § =££({йл,'}^е^), где символ С означает линейную оболочку перечисленных векторов. Если выполнено соотношение (2.3), то

§ с §.

Обозначая символом (д, /} результат действия линейного функционала д на функцию / и предполагая, что § С §, введем следующее условие:

(B) существуют линейные продолжения фунционалов д^ на пространство § такие, что для любого ] (Е J количество ненулевых элементов во множестве {{Зг,^з)}ге3 конечно.

Теорема 4. Если выполнены соотношение (2.3) и условие В, то матрица £} = дй)Т с элементами (дг,иЗ^), * (Е €Е является левой обратной к матрице

Доказательство. Транспонируем соотношение (2.3) и умножим его на одностолбцовую матрицу д слева; ввиду формулы (3.1) и условия В находим I = дшТ последнее эквивалентно равенству = /. Теорема доказана.

Определим линейную операцию проектирования V пространства § на § равенством

Рй=£ и) ^ Уй

г£ J

и введем линейное пространство Ш=£(1 — Р) §, где X — тождественная операция в §. Прямая сумма

§ = § + Ш

дает вэйвлетное разложение пространства §; пространство § называется основным, а пространство Ш — вэйвлетным.

Если а £ § и й £ §, то с некоторыми коэффициентами (Е М1 имеем и =

Т.^ш3с3’ й = ^3^31 ЧТ0 С ПОМОЩЬЮ вектор-столбцов коэффициентов {с

— def /_ \ 'Т — —7^—

и с = (с можно записать в виде и = и: с, и = и: с.

Предположим, что

(C) система состоит из линейно независимых функций.

Теорема 5. Пусть выполнены предположения (В) и (С), а элемент й € § представлен в соответствии с разложением (3.3) в виде суммы й = и + т, где и ё §,

ги Є Ш. Тогда для вектор-столбцов с, с и Ъ, фигурирующих в равенствах и = и)Тс, и = и)Тс, и) = Л)ТЪ; справедливы формулы декомпозиции

с = Дс,

Ь = с - фтДс

и формулы реконструкции

с = фтс + Ь.

Доказательство. Из определения (3.2) для и = Тй, и = и>Тс и й = итс имеем и = Гй =

= <^тДс, откуда благодаря единственности разложения и по базису ш получаем соотношение (3.4). Переписывая представление й = и -\- IV

ГГ ГР ГГ'\—

в виде ш с = ю с + ш Ь и умножая последнее соотношение слева на д, а затем используя определение матрицы Д и равенство (2.5), находим (3.6). Применив в формуле (3.6) только что установленное соотношение (3.4), получаем соотношение (3.5). Теорема доказана.

Вектор с называется исходным потоком, вектор с — основным потоком, а вектор Ь называется вэйвлетным потоком.

Матрицы р и Д будем рассматривать как линейные операторы, действующие из арифметического пространства С=£{с | [с]д- £ Е1,; Є /} в арифметическое пространство С =£{с | [с]і Є М1,* Є J}. В дальнейшем упомянутые линейные операторы будут обозначаться теми же символами: ф, £3 (Е [С і—> С]. Пространство С называется пространством исходных потоков.

4. О всплесковом разложении пространства исходных потоков

Оператор рТ, порождаемый транспонированием матрицы р, будем рассматривать как оператор, действующий из пространства С в пространство С: Є [С і—> С].

Рассмотрим формулы декомпозиции (3.4)—(3.5) и формулы реконструкции (3.6) при с (Е С, а с, Ь (Е С.

Обозначим через 1с и тождественные операторы в пространствах С и С соответственно. Поскольку

ДРТ = ІС,

применение оператора £3 к обеим частям соотношения (2.2) дает ноль: ДЬ = Дс — ДфтДс = 0; таким образом, вектор Ь лежит в ядре оператора Д: Ь (Е кегД.

Рассмотрим подпространство 5 пространства С, определяемое равенством Б =£{с | с = рТа Уа Є С}, и положим В =£кегД.

Теорема 6. Оператор рТ, рассматриваемый в паре пространств С и Б, рТ : С і—> Б, является изоморфизмом этих пространств; обратным оператором служит сужение оператора Д на подпрстранство Б:

Доказательство. Прежде всего заметим, что ввиду соотошения (4.1) кегрТ = 0 (противное означало бы существование ненулевого вектора с Є С, для которого ДРТ с = 0, что противоречит сотношению (4.1)). Теперь из определения пространства

Б ясно, что рТ —изоморфизм, а из (4.1) следует, что Д|^ —правый обратный к рТ;

для изоморфизма правый обратный является двусторонним обратным, т. е. обратным оператором в обычном смысле. Итак, Q|s : S 1—> C и выполнено соотношение (4.2). Теорема доказана.

Теорема 7. Пространство С может быть представлено в виде прямой суммы

C = S + B.

Оператор 9t=f^pT:Q проектирует пространство С на подпространство S, а оператор Ig — 9t проектирует упомянутое пространство на подпространство В.

Доказательство. Сначала докажем, что правая часть соотношения (4.3) является прямой суммой; для этого достаточно установить, что S р| В = 0. Если с (Е S р| ker£3, то из импликации с G S следует, что существует а (ЕС, при котором с = фта; а поскольку с £ B, то Qc = 0, и значит QpTa = 0, так что благодаря формуле (4.1) получаем a = 0, откуда и с = 0. Итак, установлено, что правая часть в формуле (4.3) —прямая сумма.

Теперь покажем, что любой элемент с (ЕС может быть представлен в виде с = В + Ь, где 6 (Е S, a b (Е В. Для этого положим 6=£фт£}с, b=f (% — фт£3)с. Этим заканчивается доказательство соотношения (4.3).

Для доказательства второй части теоремы заметим, что для В ё S имеем В = a при некотором a £ C, так что RB = a = a = В. Кроме того, при b ё B имеем

(Iq — 9t)b = b — 9tb = b — = Ь. Учитывая очевидные соотношения 9tc (Е S и

(i"c — 91)с (Е В, видим, что вторая часть теоремы также доказана.

Теорема 8. Если пространства S и B — гильбертовы пространства со скалярными произведениями (fi, fii)s и (b, bi)g соответственно, то относительно скалярного

произведения, в С, вводимого для любых элементов с* (Е С, i = 1, 2, по формуле

линейный оператор (фт)+ (Е [С i—> С], задаваемый соотношением

(тТ\ + -def JQc при с £ S № } С= \0 при с (ЕВ ’

является псевдообратным оператором.

Доказательство. Согласно определению псевдообратного оператора (в гильберо-вом пространстве) для доказательства достаточно установить ортогональность подпространств S и B; последняя очевидным образом следует из определения (4.4) скалярного произведения в С.

Символом ||с|| обозначим норму, порождаемую скалярным произведением (4.4) в пространстве С, ||с|| =f \J (с, с), с (ЕС.

Следствие 1. Уравнение

Фтс = с0,

рассматриваемое при, фиксированном Со (ЕС относительно с (Е С, разрешимо при Со £ В, а при, Со ф. В это уравнение не имеет решения. Вектор с* =f (фт) + Со может рассматриваться как «наилучшее обобщенное решение» уравнения в том смысле, что

причем равенство достигается лишь при с = с*.

Доказательство. Представим правую часть уравнения (4.5) в виде со = Во + Ьо, Во ё S, bo £ B; тогда по определению оператора (PT) имеем с* = (PT) Во. Очевидно, что

Во = PT с*

является ортогональной проекцией вектора со на <S, и потому ||со — Во|| < ||со — ВЦ при любом В £ S. Для доказательства соотношения (4.6) осталось в последнем неравенстве использовать формулу (4.7), а также положить В = с, где с — произвольный элемент пространства S.

Если с** —элемент, на котором реализуется минимум правой части (4.5), то необходимо, чтобы вектор В**=£фтс** являлся ортогональной проекцией вектора со на подпространство S (а такая проекция единственна); ввиду того, что осуществляет изоморфизм пространств C и S, приходим к выводу, что существует единственное решение с £ C уравнения с = В**; итак, решением этого уравнения является с**. Следствие полностью доказано.

5. О количестве арифметических операций

Ограничимся оценкой числа арифметических операций в формулах декомпозиции и реконструкции без учета числа операций, необходимых при вычислениях элементов матриц P и Q; оценка этого количества может быть получена при конкретных вариантах задания вектор-функции y>(t).

Говорят, что носителем линейного функционала g служит точка x £ M, если для любой функции f из рассматриваемого пространства функций число (g, f} определяется значениями функции f в сколь угодно малой окрестности точки x; в этом случае пишут suppg = x и такой функционал называют точечным.

Для г £ J, j £ J введем обозначения

qW d=l{j I Ф 0, j £ 1}, рЫ d=f{* I (gp Ui) Ф о, * ё J}

и положим

q

Согласно только что введенным обозначениям q(i) — число ненулевых элементов в i-й строке матрицы Q, а p(j) —число ненулевых элементов в j-й строке матрицы .

Теорема 9. Если функционалы gi и <; • —точечные (ii £ J, Vj £ J), то

1) при декомпозиции для отыскания каждого элемента основного потока требуется не более к мультипликативных и не более к — 1 аддитивных операций, а для отыскания элемента вэйвлетного потока дополнительно требуется не более к мультипликативных и не более к аддитивных операций;

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

Доказательство. Поскольку функционалы gi и <;•—точечные, количество элементов в каждом из множеств {j | suppgij С suppoJj j £ J}, {i | suppT^- С supper, i £ J} не больше Я, ибо ПО условию suppc^j С &i, SUppcUj С &j, а семейства 6 = {<3j}, 6 = {©j} — х-накрывающие. Поэтому числа р^ и q(%\ определяемые соотношениями (5.1), не превосходят числа к. Теперь доказываемые утверждения легко следуют из формул (3.4)-(3.6).

Следствие 2. Если пространства С, С конечномерны и _/V=f|J|; _/V=f|J| — их размерности (соответственно), и если выполнены предположения теоремы 9, то

1) при декомпозиции для отыскания основного потока требуется не более N к мультипликативных и не более N (к — 1) аддитивных операций, а для отыскания элемента вэйвлетного потока дополнительно требуется не более N я мультипликативных и не более N я аддитивных операций;

2) для, определения реконструируемого исходного потока требуется, не более Nх мультипликативных и, не более N я аддитивных операций.

Доказательство получается использованием теоремы 9 и формул (3.4)-(3.6).

Простой способ построения биортогональной системы точечных функционалов для функций ш.1, полученных из аппроксимационных соотношений вида (2.1), предложен в работе [8].

6. Об устойчивости вычислений при декомозиции и реконструкции

Будем считать, что пространства С и С сужены так, что их элементы имеют конечные нормы ЦсЦоо^ зир4е/ |[с]*|, ЦсЦоо^ 8ир.е7|[с].,-| соответственно.

Лемма 1. Справедливы неравенства

где

ЦОсЦоо <

Q d= sup £ \qij \,

Pd= sup ]T \Pij\.

J iEPti)

Доказательство. Из (3.4) имеем [с]* = 4ij[c\j> так чт0

|[c]i| < У] \qij\\[c}j\ < У] | qij | max | [с]д-1 < Q max | [с]д-1 < ЦЦсЦоо,

j£Q(i) j£Q(i) j£Q(i) j£QW

откуда вытекает первая из оценок в (6.1). Аналогичным образом находим вторую из оценок в (6.2).

Замечание. В условиях теоремы 9 справедливы оценки Q < ^о, P < кРо, где Qo =f supiejmaXjEQ(i) \qi:j\, P0d= supie7maxiePo) \Pij\.

Теорема 10. При, декомпозиции для векторов с и, b справедливы оценки,

< (l + qpJUclloo,

а для формул реконструкции верно неравенство

здесь Р и Р определяются формулами (6.2).

Доказательство легко следует из формул (3.4)-(3.6) и соотношений (6.1)-(6.2).

ОО

с ОО < Q С

ОО

ОО

7. Кратность накрытия и аппроксимация

Число к скалярных аппроксимационных соотношений (2.1) тесно связано с порядком аппроксимации. Проиллюстрируем это, рассмотривая вектор-фунцию <^>(£) переменных £ = (£1, £2, • • •, £п), компонентами которой являются всевозможные степени вида ^ £-22 •••£«", где а > 0, 1 = 1, 2, ...,п, ^ П=1 а — т; в этом случае к = (т„+”). Для выяснения порядка аппроксимации рассмотрим покрытие = {6^}, зависящее

от малого параметра Н > 0, так что Н = Бир^/ diam©h. В дальнейшем все связанные с ©^ объекты снабдим верхним индексом Н; в частности, рассмотрим пространство

8^ = ^ ^ | = ^2 с^, ^ е М1

ieJh

и систему функционалов {$^}, биортогональную к {^^}. Пусть исходные потоки определяются функцией / е Ст+1 по формуле = (д^,/}; в этом случае справедливо неравенство

где К — не зависящая от Н и / константа, а пК =£ ^е^^^.

В соотношениях (3.2)-(3.6) возьмем §=£§я и §=£§?1, где Н < Ыг, а I/— фиксированное число, Ь > 1. Благодаря неравенству (7.1) имеем ||^тЬ||с — 2К(ЬН)т+1||/||ст+1, так что вэйвлетная составляющая имеет порядок малости Нт+1.

Для дальнейшей иллюстрации рассмотрим симплициальное подразделение Т с вершинами ж^ 1 е J, на гладком п-мерном многообразии М; система 6, образованная (открытыми) телами его барицентрических звезд ©^ является к-накрывающей с к = п+1. При т =1 в качестве функций о^(£) из (2.1) получим аналоги функций Куранта на многообразии; существует (единственное при фиксированных вершинах, достаточной мелкости и выбранной структуре подразделения, вообще говоря, криволинейное) сим-плициальное подразделение, при котором упомянутые функции непрерывны.

Рассмотрим на Ш еще симплициальное подразделение Т с вершинами х^, ] £ представляющее собой измельчение подразделения Т. Для него аналогично предыдущему построим п+ 1-накрывающее семейство © =£{©^-}-еу, рассматривая барицентрическую звезду вершины ж^ в качестве множества Положим (<?*,/} =£/(ж*),

/) =£/(^*)- Значения элементов матрицы ф легко вычисляются; например, если п =2 и многообразие М диффеоморфно области на плоскости или сфере, то используя упомянутый диффеоморфизм, все построения можно проводить на плоскости (соответственно, сфере). Измельчая исходную триангуляцию с использованием средних линий каждого из составляющих ее треугольников, заметим, что элементы р^- принимают лишь три значения 0, 1/2, 1.

В другом примере реализации биортогональной системы функционалов ограничимся случаем п = 1, т =2. На интервале (а, в) вещественной прямой М1 (не исключаются случаи а = — оо, /3 = +оо) рассмотрим сетку X .... < х-\ < жо < х\ < ..., Игп^-оо = а, Игп^+оо = /3, и ее укрупнение — сетку X С X, X : ... < ж_1 < хо < жх,... (со своей нумерацией узлов). В качестве щ и возьмем В-сплайны второй степени класса С1 на сетках X и X соответственно, считая эирр^ = [ж*,ж*-|_з], эиррси^ = [ж^ж^+з]. Биортогональные системы функционалов представим в виде

(№,/} =£/^+1) + (ж^2 — Жi+l)//(жi+l)/2,

(^•,/)=£Я^+1) + (ж,-+2 -Хэ+1)/'(хэ+1)/2 V/ € С\а,/3),

где С1 (а, в) —линейное пространство функций, непрерывно дифференцируемых на интервале (а, в). Вэйвлетное разложение (3.3) получается применением проектирования (3.2). Если сетка X получена из X выбрасыванием лишь одного узла ж&, то пространство вэйвлетов одномерно, его базисным вэйвлетом является В-сплайн

W = {cZJk | Vc G R1}; таким образом, среднее значение полученного вэйвлета отлично от нуля. Заметим также, что вэйвлетное представление на любом отрезке [a, b], содержащемся в интервале (а, в), можно получить сужением всех рассматриваемых функций на [a, b].

Литература

1. Добеши И. Десять лекций по вейвлетам. М.; И., 2004. 464 с.

2. Малла С. Вэйвлеты в обработке сигналов. М., 2005. 671 с.

3. Новиков И. Я., Протасов В. Ю., Скопина М. А. Теория всплесков. М., 2005. 616 с.

4. Малоземов В. П., Машарский С. М. Сравнительное изучение двух вейвлетных базисов // Проблемы передачи информации. 2000. Т. 36. Вып. 2. С. 27-37.

5. Демьянович Ю. К. Всплесковые разложения в пространствах сплайнов на неравномерной сетке // Докл. РАН. 2002. Т. 382. №3. С. 314-319.

6. Ford J. M., Oseledets I. V., Tyrtyshnikov E. E. Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids // Rus. J. Numer. Anal. an Math. Modelling. Vol. 19, N2. 2004. P. 185-204.

7. Оселедец И. Применение разделенных разностей и B-сплайнов для построения дискретных преобразований вейвлетовского типа на неравномерных сетках // Матем. заметки. 2005. Т. 77. Вып. 5. С. 743-752.

8. Демьянович Ю. К. Гладкость пространств сплайнов и всплесковые разложения // Доклады РАН (2005). Т. 401, №4. С. 1-4.

9. Демьянович Ю. К. Локальная аппроксимация на многообразии и минимальные сплайны. СПб., 1994. 356 с.

10. Тыртышников Е.Е. Методы численного анализа. М., 2007. 320 с.

11. Schroder P., Sweldens W. Spherical wavelets: Efficiently representing functions on the sphere // Computer Graphics Proceedings (SIGGRAPH 95). 1995. P. 161-172.

12. Sweldens W. The lifting scheme: A custom-design construction of biorthogonal wavelets // Journal of Appl. and Comput. Harmonic Analysis. Vol. 3. Issue 2. 1996. P. 186-200.

Статья поступила в редакцию 18 мая 2008 г.