Орторекурсивные разложения по переполненным системам

Теория ортогональных рядов (рядов Фурье) является одним из классических направлений математических исследований, которое начало развиваться в первой половине XIX века. По всей видимости, первыми работами, в которых изучались ортогональные разложения, являются труды Д’Аламбера и Эйлера о колебании струны и работы Фурье о распространении тепла. В настоящее время имеется большое количество публикаций, посвященных как общей теории ортогональных рядов (см., например, [1], [7], [8]), так и разложениям в ряды Фурье по конкретным системам (см., например, [3], [4], [б]).

В последние десятилетия в результате широкого внедрения компьютерных технологий разложения в ряды Фурье по различным ортогональным системам стали широко использоваться на практике при решении задач хранения, обработки и передачи данных различной природы. При этом обрабатываемый объект (изображение, аудиофрагмент, результаты сделанных спутником измерений и др.) моделируется некоторым элементом / пространства со скалярным произведением Н, в Н выбирается подходящая, учитывающая специфику конкретной задачи полная ортогональная г 1К система {enjn=1, где К — или некоторое натуральное число (в случае конечномерных пространств Н), или бесконечность, и работа ведется не с.

I К самим элементом /, а с его разложением в ряд Фурье по системе {еп}п1, jf то есть с рядом ^ /пеп, где /п = е" п) • Этот ряд сходится к элементу /, и п=1 ' в случае бесконечномерных пространств его заменяют на частную сумму, приближающую элемент с некоторой допустимой погрешностью.

Причинами, приведшими к широкому внедрению рядов Фурье в решение прикладных задач, являются такие свойства ортогональных разложений, как простота вычисления коэффициентов, наличие тождества Бесселя, обеспечивающего возможность быстрой оценки погрешности, то есть разности между элементом и частной суммой разложения, а также так называемое свойство оперативности («on-line» свойство). Последнее свойство заключающееся в том, что если точность, с которой iV-ая частная сумма приближает разлагаемый элемент, не является приемлемой, то для получения следующего приближения — (N + 1)-й частной суммы — достаточно вычислить еще один коэффициент, не производя пересчет уже вычисленных коэффициентов. Свойство оперативности позволяет, в частности, параллельно осуществлять разложение и передавать уже вычисленные коэффициенты.

Вместе с тем, ортогональные разложения обладают свойствами, которые с точки зрения практических приложений являются отрицательными. Во-первых, условие ортогональности является очень жестким условием на систему, значительно сужающим класс систем, по которым осуществляется разложение. Во-вторых, ортогональные разложения принципиально не позволяют корректировать погрешности, возникающие в вычислении коэффициентов: для любой числовой последовательности {сп}^=1, отличной от последовательности fn коэффициентов Фурье элемента / по ор

IJ п=1 тогональной системе {e"}^L1, ряд ^ спеп либо расходится, либо сходится п= 1 к элементу, отличному от /.

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

Орторекурсивные разложения.

Орторекурсивные разложения были предложены Т. П. Лукашенко в работах [13], [14]. Эта процедура разложения дает в случае ортогональной системы в точности ряд Фурье разлагаемого элемента по этой системе. Напомним определение и некоторые свойства ортрекурсивных разложений по счетным системам.

Пусть^Н, (•,•)) — пространство со скалярным произведением над полем действительных или комплексных чисел, {еп}^=1 — система ненулевых элементов Н, f — некоторый элемент Н. Индуктивно определим последовательность остатков {rn (/)}^L0 и последовательность коэффициентов.

Положим.

Г0(Л = /, fl = /S.

2 = го (/), ех) ei, ei) М/), е2) ri (/)=r0(/)-/ieb r2(/)=n (/)-/2e2 е2, е2) и т. д. Если уже определен остаток гп (/), то положим r"(/), en+i) п+1 en+i, en+i) n+l (/) = rn (/) ~ /n+l^n+l.

Определение 1. Формальный ряд ^ fn^n называется орторекурсивп=1 ным разложением элемента f по системе {еп}^=1.

Сформулируем основные свойства орторекурсивных разложений. Теорема, А [14]. Пусть {вп}^ — система ненулевых элементов Н,.

ОО ^ — некоторый элемент Н, ^ fnen — орторекурсивное разложение f по п=1 системе {en}^Lr Справедливы следующие утверждения: (а) для любого натурального числа N выполняется равенство N.

-£/&bdquo-е„

71=1 N.

П=1 аналог тождества Бесселя) — (Ь) имеет место неравенство.

ОО /".

71—1 аналог неравенства Бесселя);

ОО с) равенство ^.

П=1 fn еп||2 = ||/1|2 имеет место тогда и только тооо гда, когда справедливо равенство f = fnen (эквивалентность ра.

П=1 венства Парсеваля и сходимости орторекурсивного разложения к разлагаемому элементу).

Как отмечается, например, в работах [15], [30], схема орторекурсив-ного разложения допускает принципиально различные подходы: можно изначально фиксировать систему {еп}^=1, а можно на каждом шаге для данного элемента / (или для данного остатка гп (/)) выбирать из некоторого фиксированного множества очередной разлагающий элемент en+i (/). Второй подход реализуется, в частности, в жадных разложениях. Существенным отличием орторекурсивных разложений по фиксированным системам и жадных разложений является отсутствие у последних линейности. Приведенные выше свойства определяются лишь схемой орторекур-сивного разложения и не зависят от способа выбора разлагающих элементов, таким образом, они справедливы как для орторекурсивных разложений по фиксированной системе функций, так и для жадных разложений.

Далее, если не оговорено противное, под орторекурсивным разложением будет пониматься орторекурсивное разложение по фиксированной системе элементов.

При решении прикладных задач в качестве пространства со скалярным произведением обычно выступает L2 (X, Л, fi), где (X, А, //) — некоторое измеримое пространство (часто это отрезок числовой прямой или прямоугольник на плоскости с классической мерой Лебега). При вычислении скалярных произведений в этом пространстве (то есть при вычислении соответствующих интегралов), а значит, и при вычислении коэффициентов орторекурсивного разложения неизбежны вычислительные ошибки (погрешности). В ряде случаев за счет выбора параметров вычислительной схемы можно добиться того, чтобы величины ошибок не превосходили некоторых наперед заданных значений, контролируя тем самым возникающие погрешности. Однако полностью устранить вычислительные неточности нельзя. В связи с этим возникает необходимость формализации понятия ошибок в вычислении коэффициентов орторекурсивного разложения и изучения возможности коррекции возникающих погрешностей за счет выбора разлагающей системы.

Приведем определение орторекурсивных разложений с ошибками в вычислении коэффициентов.

Пусть (Н, (•, •)) — пространство со скалярным произведением над полем действительных или комплексных чисел, {еп}^ — система ненулевых элементов Н, f — некоторый элемент Н. Индуктивно определим последовательность остатков разложения {г®- (/)}^L0 и последовательность коэффициентов разложения верхний индекс указывает на то, что в вычислении коэффициентов разложения возможны ошибки). Положим reo (f) = /.

Если уже определен остаток г®- (/), то коэффициент /®+1 запишем в виде.

Те (r^(/), en+1) где en+i и? n+i — некоторые числа. Положим.

Сы (Я = <(/) «Й+хвп+ь оо ^.

Определение 2. Формальный ряд ^ /®-еп будем называть ортореп=1 курсивным разложением элемента f по системе {е^^^ с ошибками я = {(*", WKL г.

Отметим, что орторекурсивное разложение по системе {еп}^=1 с нулевыми ошибками £0,о (^о, о = {(^m ?n))w> где еп = £п = 0 при п = 1, 2, 3, .) совпадает с обычным орторекурсивным разложением по этой системе.

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

Впервые определение, аналогичное определению 2, было предложено Р. Грибонвалем и М. Нилсеном в работе [22], посвященной изучению устойчивости жадных разложений к вычислительным ошибкам. Ошибки в этой работе задавались посредством их относительных величин.

При практической реализации орторекурсивных разложений последовательность ошибок Е неизвестна, но в ряде случаев эта последовательность может быть оценена. Например, можно специально реализовывать вычислительную схему так, что ошибка при вычислении коэффициента fn не превосходит некоторую изначально выбранную величину.

Различным парам (еп, £п) может соответствовать одна и та же ошибка в вычислении коэффициента при этом любая ошибка в вычислении коэффициента может быть задана посредством лишь £п, с еп = 0. Однако используемая форма записи ошибок удобна как при теоретической работе с орторекурсивными разложениями (формулировка и доказательство теорем при используемой форме записи ошибок становятся более понятными), так и при прикладной работе (в некоторых случаях проще могут быть установлены оценки на относительные ошибки, в некоторых — на абсолютные).

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

Определение 3. Пусть? — некоторое непустое множество последовательностей числовых пар. Будем говорить, что орторекурсивное разложение по системе ненулевых элементов {enj-^lj абсолютно устойчиво к ошибкам из множества ?, если для любого элемента f Н и любой последовательности Е = {(?n>? ? орторекурсивное разложение элемента / по системе {еп}^=1 с ошибками Е сходится к /.

Основными классами ошибок, изучаемыми в данной работе, являются классы ?0 и? i-tp. ?q — это множество последовательностей числовых пар {(?", ?n)}^Li) удовлетворяющих следующему условию: существует такое целое неотрицательное число N, что для всех номеров n, п ^ N + 1, справедливы равенства еп = £п = 0. — это множество последовательностей числовых пар {(еП5 таких, что lim sup |er"| < 1 и ПОСЛега—>ОО довательность принадлежит пространству I2.

Жадные разложения.

Впервые, вероятно, жадные разложения встречаются (в неявном виде) в работе Б.С. и С. Б. Стечкиных [18]. В статистике и теории передачи сигналов жадные разложения по конкретным системам изучались с 1980;х годов (см. [21], [23], [25]). При этом в теорию передачи сигнала жадные разложения вошли под названием Matching Pursuit, а в статистику — под названием Projection Pursuit. Активное изучение общей теории жадных разложений было начато в 1990;е годы математиками университета Южной Каролины, США (см. [27]). Именно ими был введен термин «жадный» (greedy) для описания таких разложений. Как уже отмечалось выше, жадные разложения — нелинейная процедура разложения. В случае ортогональной системы классическое жадное разложение дает ряд Фурье разлагаемого элемента по этой системе, переставленный в порядке убывания модулей коэффициентов.

Общая теория жадных разложений начала развиваться с изучения чисто жадных (Pure Greedy) разложений. Напомним соответствующее определение. Пусть (#, (•, •)) — гильбертово пространство над полем R или С, / — элемент Н, D — подмножество ненулевых элементов Н с всюду плотной в Н линейной оболочкой (так называемый «словарь» — dictionary). Индуктивно определим последовательность остатков {^n (/)}^Lo чи~ еловую последовательность коэффициентов |/п| и последовательность разлагающих элементов {en (/)}^Li С D. Положим ro (f) = f.

Возьмем в качестве (/) произвольный элемент D, удовлетворяющий условию l (ro (/)iei (/))l l (ro (/), e)| llei (/)ll S INI ' положим = ^'ff". п (Л = г0(Л-ШЛ.

Возьмем в качестве ег (/) произвольный элемент D, удовлетворяющий условию п (/), е2(/))| |(ri (/), е)[.

1ЫЯ11 Л ||е|| '.

ПОЛОЖИМ h — (е2,е2) ' Г2(/) = ri (/) ~ и т. д. Если уже определен остаток rn (f), то возьмем в качестве еп+1(/) произвольный элемент D, удовлетворяющий условию.

1Ы/), вп+1(/))1 = Ifrn (/), <01 l|en+i (/)|| eeD \е\ положим fn+1 = T" n+i (/) = rn{f) — fn+1en+i (f). еп+1, en+ij.

Определение 4. Описанный выше процесс называется чисто жадным алгоритмом (Pure Greedy Algorithm — PGA). Если разложение осуществить удалось, то построенный в результате его применения формаль.

ОО л ный ряд fnen будем называть PGA-разложением элемента / G Н по п=1 системе D.

Отметим, что описанный процесс не всегда осуществим: супремум, возникающий при выборе очередного разлагающего элемента, может и не ре-ализовываться. Кроме того, термин «алгоритм», традиционно употребляющийся в названии процесса, не совсем корректен, так как даже в случае, когда супремум реализуется, выбор очередного разлагающего элемента не является конструктивным. Эти соображения, а также стремление исследовать устойчивость разложения к погрешностям в вычислении коэффициентов и в выборе разлагающих элементов, привели к необходимости обобщения модели чисто жадного разложения. Наиболее общей моделью такого рода в настоящее время является обобщенный приближенный слабый жадный алгоритм. Приведем соответствующее определение, полагая, для сокращения записи, что система D нормирована.

Пусть^Н, (•, • — гильбертово пространство над полем действительных или комплексных чисел, множество D элементов Н — нормированный словарь (то есть для любого элемента d Е D справедливо равенство ||с?|| = 1 и замыкание линейной оболочки D совпадает с Н). Пусть также / — некоторый элемент Н, {?n}^Li — последовательность чисел из отрезка [0,1], {qn}n=i ~ последовательность действительных неотрицательных чисел, {(?n> ?п)КГ=1 — послеДовательность числовых пар. Определим индуктивно последовательность остатков {гп (/)}^=0, последовательность коэффициентов {/"} и последовательность разлагающих элементов {е&bdquo-(/)}^=1. Положим.

П>(/) = /.

Далее, если уже определен остаток гп (/), найдем элемент en+i (/) G D, удовлетворяющий условию.

IM/), en+i (/))| ^ tn+1 sup |(rn (/), e)| - qn+l. e€D.

Если элементов, удовлетворяющих этому условию, несколько, в качестве en+i (/) выберем любой из них. Если элементов, удовлетворяющих этому условию, не существует, будем говорить, что осуществить разложение не удалось. Отметим, что последний случай возможен только если tn+i = 1 и qn+1 = 0.) Положим fn+1 = (Г rn+i (f) = rn (f) — fn+1en+1{f).

Определение 5. Описанный выше процесс будем называть обобщенным приближенным слабым жадным алгоритмом (gAWGA — generilized Approximate Weak Greedy Algorithm). Если разложение удалось осущеоо Л ствить, формальный ряд fn^nif) будем называть обобщенным приблип=1 женным слабым жадным разложением (или gAWGA-разложением) элемента / по словарю D с ослабляющими последовательностями {дп}^=1 и последовательностью ошибок {(en?

Последовательность ошибок {(еп, допускает ту же интерпретацию, что и в случае орторекурсивных разложений с ошибками в вычислении коэффициентов. Смысл введения ослабляющих последовательностей {*"}≅1 и {<3Vi}^Li заключается в стремлении максимально ослабить требования, налагаемые при выборе очередного разлагающего элемента. Отметим, что несмотря на такое ослабление выбор разлагающих элементов в gAWGA неконструктивен, так что термин «алгоритм» в названии процесса, как и в случае PGA, не совсем корректен.

Если qn = = 0 для всех натуральных п, то gAWGA совпадает с введенным Р. Грибонвалем и М. Нилсеном приближенным слабым жадным алгоритмом (AWGA — Approximate Weak Greedy Algorithm, см. [22]). Если для всех натуральных п выполняются равенства qn — = 0, еп = 0, то gAWGA совпадает с предложенным В. Н. Темляковым слабым жадным алгоритмом (WGA —Weak Greedy Algorithm, см. [27]). Если qn = ?n = еп = О и tn = 1 для всех натуральных п, то gAWGA совпадает с рассмотренным выше чисто жадным алгоритмом.

Цель работы.

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

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

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

— исследовать устойчивость полученных условий к малым изменениям системы;

— привести пример функциональной системы, удовлетворяющей полученным условиям, исследовать сходимость разложений по этой системе (сходимость почти всюду, равномерную сходимость, сходимость в метриках Lp);

— получить условия на параметры обобщенного приближенного слабого жадного разложения, гарантирующие сходимость разложения к разлагаемому элементу;

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

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

Структура и основные результаты работы.

Работа состоит из введения, четырех глав и списка литературы, включающего 40 наименований. Теоремы, леммы, утверждения имеют номера из двух чисел, первое из которых — номер главы, а второе — номер теоремы (леммы, утверждения) в этой главе. Определения нумеруются сквозным образом. Результаты других авторов нумеруются сквозным образом латинскими буквами.

Во введении дан краткий обзор исследуемой проблемы, приведены определения изучаемых объектов — орторекурсивных разложений и жадных разложений, сформулированы основные результаты работы.

1. Алексии Г. Проблемы сходимости ортогональных рядов — М.: ИЛ, 1963.

2. Бари Н. К. Об устойчивости свойства полноты системы функций // Докл. АН СССР. 1942. 37. С. 99−103.

3. Голубов Б. И., Ефимов А. В., Скворцов В. А. Ряды и преобразования Уолша. Теория и применения— М.: Наука, 1987.

4. Добеши И. Десять лекций по вейвлетам — Ижевск: РХД, 2001.

5. Дьяченко М. И., Ульянов П. Л. Мера и интеграл — М.: Факториал, 1998.

6. Зигмунд А. Тригонометрические ряды. тт. 1, 2. — М.: Мир, 1965.

7. Качмаж С., Штейнгауз Г. Теория ортогональных рядов — М.: ГИФМЛ, 1958.

8. Кашин Б. С., Саакян А. А. Ортогональные ряды (2-е изд.) — М.: АФЦ, 1999.

9. Кудрявцев А. Ю. Орторекурсивные разложения по системам сжатий и сдвигов / / Современные проблемы теории функций и их приложения. Тезисы докладов 11-й Саратовской зимней школы. — Саратов: Изд-во ГосУНЦ «Колледж», 2002. С. 106−108.

10. Кудрявцев А. Ю. Орторекурсивные разложения по системам неортогональных всплесков II Современные методы теории функций и смежные проблемы. Материалы конференции. — Воронеж: Воронежский государственный университет, 2003. С. 137−138.

11. Кусис П.

Введение

в теорию пространств Нр — М.: Мир, 1984.

12. Лившиц Е. Д., Темляков В. Н. О сходимости слабого гриди-алгоритма // Труды математического института им. В. А. Стеклова. 2001. 232. С. 236−247.

13. Лукашенко Т. П. Об орторекурсивних разложениях по системе Фабера-Шаудера // Современные проблемы теории функций и их приложения. Тезисы докладов 10-й Саратовской зимней школы. — Саратов: Изд-во Саратовского университета, 2000. С. 83.

14. Лукашенко Т. П. О свойствах орторекурсивних разложений по неортогональным системам // Вестник Моск. ун-та. Сер. I. Матем. Ме-хан. 2001. № 1. С. 6−10.

15. Лукашенко Т. П. О новых системах разложения и их свойствах // Чебышевский сборник. 2004. 5, вып. 2. С. 66−82.

16. Натансон И. П. Теория функций вещественной переменной — СПб.: Лань, 1999.

17. Сакс С. Теория интеграла — М.: ИЛ, 1949.

18. Стечкин B.C., Стечкин С. Б. Среднее квадратическое и среднее арифметическое // Докл. АН СССР. 1961. 137, № 2. С. 287−290.

19. Стечкин С. Б. Избранные труды. Математика — М.: Наука, Физмат-лит, 1998.

20. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. Т. 1. Изд. 7-е. — М.: Наука, 1969.

21. Friedman J.H., Stueuzle W. Projection pursuit regression //J. Amer. Statist. Assoc. 1981. 76. P. 817−823.

22. Gribonval R., Nielsen M. Approximate Weak Greedy Algorithms // Adv. Comput. Math. 2001. 14, № 4. P. 361−378.

23. Jones L.K. On a conjecture of Huber concerning the convergence of PP-regression // Ann. Statist. 1987. 15. P. 880−882.

24. Jones L. A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and network training // Ann. Statist. 1992. 20. P. 608−613.

25. Mallat S., Zhang Z. Matching pursuit with time-frequency dictionaries // IEEE Trans. Signal Process. 1993. 41, № 12. P. 3397−3415.

26. Rejto L., Walter G. G. Remarks on ptojection pursuit regression and density estimation // Stochastic Analyses and Application. 1992. 10. P. 213−222.

27. Temlyakov V.N. Weak greedy algorithms // Adv. Comput. Math. 2000. 12, № 2,3. P. 213−227.

28. Temlyakov V. N. A criterion for convergence of Weak Greedy Algorithms // Internet: http://www.math.sc.edu/ imip/OO.html 00:21.Научные работы автора по теме диссертации.

29. Галатенко В. В. Об орторекурсивном разложении по системе сигнумов II Современные исследования в математике и механике. Труды XXIII Конференции молодых ученых механико-математического факультета МГУ. — М.: Изд-во ЦПИ при мех-мат ф-те МГУ, 2001. С. 9294.

30. Галатенко В. В. Об орторекурсивном разложении по некоторой системе функций II Известия РАН. Сер. матем. 2002. 66, № 1. С. 59−70.

31. Галатенко В. В. О скорости сходимости орторекурсивных разложений по некоторой системе функций // Труды XXIV Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова. — М.: Изд-во ЦПИ при мех-мат ф-те МГУ, 2002. С. 47−49.

32. Галатенко В. В. О LP-разложениях по системе сигнумов / / Труды участников Международной школы-семинара по геометрии и анализу памяти Н. В. Ефимова. — Ростов-на-Дону, 2002. С. 111−113.

33. Галатенко В. В. О разложении по некоторой системе функций с фиксированными коэффициентами // Вестник Моск. ун-та. Сер. I. Матем. Механ. 2003. № 1. С. 13−16.

34. Галатенко В. В. О скорости сходимости Lp-разложений по системе сигнумов // Современные методы теории функций и смежные проблемы: материалы конференции. — Воронеж: Воронежский государственный университет, 2003. С. 67−68.

35. Галатенко В. В. Об устойчивости орторекурсивных разложений к ошибкам в вычислении коэффициентов // Современные проблемы теории функций и их приложения. Тезисы докладов 12-й Саратовской зимней школы. — Саратов: Изд-во ГосУНЦ «Колледж», 2004. С. 51−52.

36. Галатенко В. В. Об орторекурсивном разложении по некоторой системе функций с ошибками при вычислении коэффициентов // Мат. сборник. 2004. 195, № 7. С. 22−36.

37. Галатенко В. В. Об орторекурсивном разложении с ошибками в вычислении коэффициентов // Известия РАН. Сер. матем. 2005. 69, JVe 1. С. 3−16.

38. Галатенко В. В. Об одной модификации жадных разложений // Современные методы теории функций и смежные проблемы: материалы Воронежской зимней математической школы. — Воронеж: ВГУ, 2005. С. 65−66.

39. Galatenko V. V., Livshitz Е. D. On the convergence of Approximate Weak Greedy Algorithms // East J. Approx. 2003. 9, № 1. P. 43−49. Теорема 3 установлена Галатенко В. В., теорема 4 установлена Лившицем Е. Д.