Сходимость жадных алгоритмов тема диссертации и автореферата по ВАК РФ 01.01.01, доктор физико-математических наук Лившиц, Евгений Давидович

• Лившиц, Евгений Давидович
• доктор физико-математических наук
• 2010

Оглавление диссертации доктор физико-математических наук Лившиц, Евгений Давидович

Введение

1 Скорость сходимости чисто жадного и ортогонального жадного алгоритмов

1.1 Сходимость жадных алгоритмов.

1.2 Реализуемость жадных алгоритмов для дискретных словарей

1.2.1 Вспомогательные леммы.

1.2.2 Доказательство теорем 1.1 и 1.2 .

1.3 Скорость сходимости жадных алгоритмов и наилучшие т-членныс приближения.

1.4 Оценка снизу на скорость сходимости чисто жадного алгоритма

1.4.1 Общие формулы.

1.4.2 Конструкция.

1.4.3 Подбор параметров.

1.4.4 Дальнейшие оценки.

1.4.5 Окончание доказательства теоремы 1.12.

1.5 Оценка снизу на скорость сходимости ортогонального жадного алгоритма.

1.6 Интерполяционные классы.

1.7 Оценки сверху на скорость сходимости чистого жадного алгоритма для интерполяционных классов.

1.7.1 Численные неравенства.

1.7.2 Основные определения и неравенства для ЧЖА

1.7.3 Множества Д(гао)

1.7.4 Оценка произведений атЬт.

1.7.5 Доказательство теоремы 1.16.

1.8 Нижние оценки для интерполяционных классов.

2 Скорость сходимости жадных алгоритмов для словарей с малой когерентностью

2.1 Неравенства типа Лебега.

2.1.1 Вспомогательные леммы.

2.1.2 Вспомогательные обозначения.

2.1.3 Основные леммы.

2.1.4 Доказательство теоремы 2.7.

2.2 Словари с ограниченной совокупной когерентностью

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

3.1 Возвратный жадный алгоритм.

3.2 Сходимость возвратного жадного алгоритма. Доказательство теоремы 3.2.

3.3 Скорость сходимости возвратного жадного алгоритма.

3.3.1 Оценка akjfDk.

3.3.2 Основная лемма.

3.3.3 Доказательство теорем 3.3 и 3.4.

3.4 Жадные разложения с неотрицательными коэффициентами

3.4.1 Основные определения.

3.4.2 Сходимость ПСЖА.

3.4.3 Связь между СЖА и ПСЖА. Необходимое условие сходимости ПСЖА.

4 Жадные алгоритмы в банаховых пространствах

4.1 Введение.

4.2 Пример расходимости Х-ЖА в гладком банаховом пространстве

4.3 Сходимость Д-ЖА.

4.4 Некоторые геометрические свойства пространства lp, р >

4.5 Система Хаара и система функций пропорциональных индикаторам двоичных промежутков.

4.6 Схема доказательства теоремы 4.6.

4.7 Вспомогательные леммы.

4.8 Доказательство теоремы 4.9.

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

4.8.2 Двоичные деревья.

4.8.3 Окончание доказательства теоремы 4.9.

4.9 Доказательство теоремы 4.10.

4.10 Сходимость и скорость сходимости Х-УКК по системе Хаара

4.11 Сходимость и скорость сходимости Х-УКК по системе Хр

Введение диссертации (часть автореферата) на тему «Сходимость жадных алгоритмов»

Теория приближения относится к тем областям математики, которые тесно связаны с прикладными задачами естествознания и техники. Увеличение мощности вычислительных систем, происходившее в последние десятилетия, позволило приступить к решению новых более вычислительноемких задач. Одной из них является построение "индивидуального приближения" для заданной функции / из некоторого класса К. Приближение предлагается строить как элемент линейного подпространства L из заранее определенного (по К) семейства линейных подпространств С. При этом выбор L G С зависит от /, что отличает эту задачу от классической задачи аппроксимации класса К, где приближающее подпространство L выбиралось единым для всех / G К. Другими словами, класс К приближается нелинейным объектом ULeC L- Такие приближения имеют также важное теоретическое значение. Как было показано P.C. Исмагиловым [9], К.И. Осколковым [17] pi В.Е. Майоровым [16] этот нелинейный (индивидуальный) подход может давать преимущества в некоторых классических задачах. Изучение оценок снизу для этого метода приближения было начато Б.С. Кашиным [10].

Начиная с 80-х годов 20-го века, в рамках математической статистики и теории приближения стали интенсивно изучаться жадные алгоритмы, что, с одной стороны, дало теоретическое обоснование ряда методов вычислительной математики, а, с другой стороны, позволило получить конструктивные способы нахождения наилучших т-членных приближений. Ключевую роль в формировании теории жадных алгоритмов сыграли работы Дж. Фридмана, В. Стузла, С. Маллата, Ж. Жанга, П. Хьюбера, JI. Джоунса, А. Бэр-рона, Р. ДеВора, В.Н. Темлякова, C.B. Конягина, Д.Донохо и др. ([46], [64], [53], [54], [25], [37], [58], [34], [41]). В паши дни жадные алгоритмы успешно применяются в задачах распознавания образов, медицины, финансовой математики, обработки сигналов и ряде других областей ([42], [85], [70], [66], [65]).

Необходимо отметить, что со временем большая часть результатов по жадным алгоритмам начала формулироваться и доказываться на языке теории функций. Более того, идеология теории функций в значительной степени определила направлёния дальнейших исследований жадных алгоритмов.

Пусть X = (X, || • ¡1) — действительное банахово пространство. Множество Т>, Т> С X, будем называть словарем, если оно состоит из векторов с единичной нормой, и замыкание линейной оболочки Т> совпадает со всем X: geV №11 = 1, spânP = X.

Для произвольного элемента / g X и m g N требуется найти конечную линейную комбинацию m элементов словаря, достаточно хорошо приближающую /: m ck(f)gk(f), ck(f) G M, gk(f) G V. (0.0.1) k=î

Особенностями данной постановки являются:

• от / зависят не только коэффициенты ck(f), но и элементы словаря 9k{f ); участвующие в приближении,

• словарь V может быть как базисом, так и переполненной системой. Важными примерами переполненных систем являются словарь плоских волн (ridgc-функций), RBF-словари, переполненные системы случайных векторов и. т.д.

При этом желательно, чтобы величина ошибки аппроксимации ||/ — ЕГ=1с*:(/Ы/)|| была близка к значению наилучшего m-членного приближения (это понятие было введенного С.Б. Стечкиным в [21]) m

Vm(f, ) ■•= Vm(f, v) am(f, V, X) = inf ||/ - £ ck9k||. k—l

В большинстве случаев, особенно для переполненных словарей, построение m-членных приближений (0.0.1), пусть даже не наилучших, является весьма важной и интересной задачей.

Наметим подход к построению га-членных приближений с помощью жадных алгоритмов.

Пусть X является сепарабельным гильбертовым пространством H — (Я, <•,■)) с нормой ||.|| := Ь->1/2.

Чисто жадный алгоритм (ЧЖА) Пусть задан словарь V с Я и целевая функция /qGA := /о := / € Я. Положим GqGA{J,T>) 0. Последовательно для каждого m > 0 выбираем вектор gm+i G D такой, что

I (/m, 9т+1) ! = sup | (fm: g) | (0.0.2) geV и определяем

Cf(/^) := G™A(f,V) + {fm,gm+i)gm+u fm+1 '•— fm+1 '■— f — 1 (/j D) — fm — (fm: 9m+l)ffm+l

Таким образом, для / и m > 1 построены ш-членные приближения GpmGAU,V).

Корректность определения gm+i по формуле (0.0.2) будет обсуждаться ниже, пока лишь заметим, что в случае конечномерного H и конечного словаря Т> (случай приложений), супремум всегда достигается на каком-либо элементе словаря, и его вычисление, требует конечного числа действий.

Отметим, что ЧЖА строит разложение элемента / в ряд по словарю V, максимально уменьшая па каждом шаге алгоритма норму остатка: ll/m+i|| = inf II frn - cg\l m > 0. ceR, g&V

Если Т> является ортонормированным базисом в H, то ЧЖА будет выбирать элементы словаря в порядке убывания коэффициентов Фурье функции / относительно этого базиса. Подобные приближения рассматривались в теории функций начиная с работы С.Б.Стечкина [21].

Для переполненных систем специального вида ЧЖА впервые появился в статистике в работе Дж. Фридмана и В. Стузла [46] под именем Projection pursuit regression, а также в теории передачи сигнала в работе С. Маллата и Ж. Жанга [64] под именем Matching pursuit.

Необходимо также отметить, что ряд более ранних работ по теории функций, например, Е. Шмидта [71], а также B.C. Стечкина и C.B. Стечкина [20], может быть проинтерпретирован как результат о сходимости ЧЖА для словарей специального вида.

Жадные алгоритмы тесно связаны с орторекурсивными разложениями, которые в последние годы интенсивно исследовались Т.П. Лукашенко, В.В. Галатенко и др. ([14], [3], [4], [5] [15], [13], [18]).

С современным состоянием теории жадных алгоритмов можно ознакомиться, например, в обзоре В.Н. Темлякова [75].

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

1. Показано, что чисто жадный алгоритм не является оптимальным по порядку в пространстве Ai(T>). Получены оценки снизу на скорость сходимости чисто жадного алгоритма в пространствах Aq(T>) и Лг(Т>) достаточно близкие наилучшим известным оценкам сверху (A.B. Силь-ниченко). Тем самым получен ответ на вопрос Девора - Темлякова об оптимальности ЧЖА и с точностью до 0.01 определена константа Ко-нягина - Темлякова. (Теорема 1.12.)

2. Показано, что чисто жадный алгоритм обладает оптимальной по порядку скоростью сходимости в интерполяционных пространствах [Я, л(£>)]<?,оо при 0 < в < 1/3. (Теорема 1.15.)

3. Получено точное по порядку неравенство типа Лебега для ортогонального жадного алгоритма по словарям с малой когерентностью. Ранее эта задача исследовалась в работах Д. Донохо, М. Элада, В.Н. Тем-лякова, А. Гильберт, М. Мутукришнана, Дж. Штраусса, Дж. Троппа, П. Желтова. (Теорема 2.7.)

4. Предложен возвратный жадный алгоритм, который позволяет получать жадные разложения, обладающие оптимальной по порядку скоростью в интерполяционных пространствах [H,Ai(T>)]ej00 при 0 < в < 1, и, в частности, в А\(Т>). (Теоремы 3.3, 3.4.)

5. Предложены положительный чисто жадный и положительный слабый жадный алгоритмы. Доказано, что если функция приближается элементами словаря с положительными коэффициентами, то жадные разложения, построенные с помощью этих алгоритмов, после приведения подобных будут иметь неотрицательные коэффициенты. Тем самым, получен ответ на вопрос B.C. Кашина о конструктивном получении "положительных" 7п-членных приближений. (Теоремы 3.5, 3.6.)

6. Построен пример гладкого банахова пространства, словаря в нем и целевой функции, для которых Х-жадный алгоритм расходится. (Теорема 4.1.)

7. Найдено новое геометрическое свойство банаховых пространств, являющееся достаточным для сходимости некоторых видов жадных алгоритмов в банаховых пространствах. Доказана сходимость і?,-жадного алгоритма в пространствах lp, р > 2. (Теоремы 4.2, 4.3.)

8. Исследована сходимость Х-жадного алгоритма в пространстве Lp(0,1) для конкретных систем: системы Хаара, и системы функций, пропорциональных индикаторам двоичных интервалов. Получены неравенства типа Лебега, а также доказана сходимость Х-жадного алгоритма по "системе индикаторов" на всем пространстве Lp(0.1), 1 < р < оо. (Теоремы 4.4, 4.5, 4.6, 4.7.)

В главе 1 изучается скорость сходимости чисто жадного и ортогонального жадного алгоритмов в гильбертовом пространстве. В параграфе 1.1 приводится определение чисто жадного и ортогонального жадного алгоритмов.

Ортогональный жадный алгоритм (ОЖА) Пусть задан словарь V и целевая функция JqGA := /о := / Є Н. Положим GQGA(f,T>) := 0. Последовательно для каждого т > 0 выбираем вектор gm+i Є Т> такой, что fm,9m+l)\=swp\(fm,g)\ (0.0.3) и определяем 1 V) := Projspajl(fllv.i5m+l)/, fOGAг г s-iOGA/ f T)\

Jm+1 ■— Jm+1 -—JO — Ьm+l

Также в параграфе 1.1 приводятся результаты JI. Джонса [54] и В. Дубинина [45] о сходимости ЧЖА и ОЖА: для любого гильбертова пространства Я, словаря Т> и целевой функции / е Я выполняются равенства lim ||/ - GpmGA{f,V)II = 0, lim ||/ - G°GÄ(f,V)|| = 0. то—> oo m—>схз

Определение 1.1. Будем называть словарь Т> дискретным, если

SUP |(01,02)| < 1

Легко видеть, что в сепарабельном пространстве дискретные словари не более чем счетны.

Формально супремум в формулах (0.0.2) и (0.0.3) может не достигаться. Однако оказалось, что если словарь V дискретен, то для "большинства" функций супремум в формулах (0.0.2) и (0.0.3) достигается на каком-либо элементе словаря на всех шагах алгоритма.

Теорема 1.1. Пусть задан дискретный словарь Т>. Тогда множество функций из Н, для которых на каждом шаге ЧЖА супремум достигается: G Я | Vm {gm+1 е V : |</m,Wi>l = sup\(fm,g)\} Ф 0)

I gev ) является множеством второй категории1 ( использовалось обозначение fm = f-G™A(f,V)).

Теорема 1.2. Пусть задан дискретный словарь Т>. Тогда множество функций из Н, для которых на каждом шаге ОЖА супремум достигается: б Я | Vm {gm+1 е V : \(fm,gm+i)\ = sup |</m,p>|> ф 0) I gev J является множеством второй категории (использовалось обозначение fm = f~G°GA(f,V)).

В параграфе 1.3 приводятся результаты о скорости сходимости жадных алгоритмов. Для получения оценок сверху на скорость сходимости жадного алгоритма, необходимо потребовать, чтобы целевая функция / принадлежала некоторому, зависящему от словаря, классу Л(Т>). Показано, что классы, под множествами второй категории в этой работе понимаются такие множества, дополнения которых являются множествами первой категории. определяемые скоростью убывания наилучшего га-членного приближения, оказываются слишком широкими.

Теорема 1.5. Пусть заданы строго убывающие положительные функции г, R g c(r+), для которых lim r(t) = lim R{t) = 0. t—>00 t—>00

Тогда найдется словарь T>, целевая функция f <Е Н и С > 0, для которых имеют место неравенства

GmUiV) < R(m), т> 1, f-G™Ä(f,V)\\>Cr(m), га>1, \\f-G°GA(f,V)\\>Cr(m), т> 1.

Таким образом, для получения нетривиальных оценок сверху на скорость сходимости жадных алгоритмов необходимо накладывать более жесткие ограничения на класс А(Т>). Наиболее популярным в теории жадных алгоритмов является класс А\(Т>), определенный ниже. Для словаря V и М > 0 рассмотрим класс

A^VtM):={feH:f = ^x9xi gxeV,#A< 00 и J>A| < М}

Дел Аел и класс Л\{Т>, М), являющийся замыканием (в Н) класса A°(D,M). Далее определим

Ai{V) := (J Ai(V,M). м>о

Для / £ А\(1У), введем норму

I fWv) = inf{M > о I fe Ai (V, M)}.

Отметим, что шар А\(Т>, 1) является замыканием выпуклой оболочки Т> U (-V).

Из результатов С.Б. Стечкина [21] и А. Бэррона [25] следует, что последовательность величин наилучшего га-членного приближения 0m(f,T>) для / g А\{Т>) убывает не медленнее, чем Cm-1/2, и показатель —1/2 не может быть уменьшен даже для ортонормированного словаря.

Приводятся оценки сверху на скорость сходимости ЧЖА - G™Ä(f,V)У < C7\f\MV)rrn. (0.0.4)

Р. ДеВор и В.Н. Темляков [37] доказали справедливость (0.0.4) для 7 = 1/6, С.В. Конягин и В.Н. Темляков [58] — для 7 = 11/62, A.B. Сильни-ченко [19] — для 7 = 0.182.

Для построения нижних оценок необходимо построить словарь Т>, функцию / 6 Al(T>), / 0 и для нее оценить снизу скорость убывания нормы

II/ - G™A(f,V)\\ > С7|/и1(0)т^, С7 > 0. (0.0.5)

Отметим, что во всех нижних оценках, приведенных в работе, функция / будет являться конечной линейной комбинацией элементов словаря, т.е. принадлежать пространству разреженных (sparse) векторов Ло(V):

Ят(Р) = \ с*3\, д\ G V, #А < m > . (0.0.6)

I АеЛ J

MV) ■■= U Егп(Т>), т>0 l/lo = l/UoP) := min 0: fe Ето(£>)}, / € AQ{V).

Класс Ло(Т>) С Л\(V) является очень узким и из приведенных ниже оценок будет следовать, что за счет "разумного" сужения Л\{Т>) существенно увеличить скорость сходимости ЧЖА и ОЖА нельзя.

Р. ДеВор и В.Н. Темляков [37] установили (0.0.5) для 7 = 1/2. Автору удалось проверить (0.0.5) для 7 = 1/2 — 5 > 0, В.Н. Темляков уменьшил 7 до 1/3, в совместной работе автора и В.Н. Темлякова [93] 7 было уменьшено до 0.27.

В параграфе 1.4 получена новая оценка снизу на скорость сходимости ЧЖА, которая оказывается весьма близкой к верхней оценке A.B. Сильни-ченко.

Теорема 1.12. Существует такой словарь V, элемент f е Ло(Т>) и С > 0, что для произвольного т> 1 выполняется неравенство

II/ - G™A(f,V)\\ = ||/«"|| > Cm-«-™S\f\Mvy

В параграфе 1.5 получена оценка снизу на скорость сходимости ортогонального жадного алгоритма.

Теорема 1.13. Существует такой словарь Т>, элемент / € Ло(Т>) и С > 0, что для произвольного т> 1 выполняется неравенство

II f-G°mGAUm\>Cm-l'\

Этот результат показывает неулучшаемость оценки сверху Р. ДеВора и В.Н. Темлякова [37] на скорость сходимости ОЖА.

Как отмечалось выше, в случае произвольного словаря Т> сужение класса Л\{Т>) не ведет к увеличению скорости сходимости жадных алгоритмов, в тоже время как на более широких классах, скорость сходимости жадных алгоритмов может быть близка к оптимальной. Соответствующие результаты формулируются в параграфе 1.6 и доказываются в параграфе 1.7.

В качестве расширений Л\ (V) будут рассматриваться интерполяционные пространства [Н,Л

Пусть X и У действительные нормированные пространства. Напомним (см. [28]) определение интерполяционных пространств [X, У]0]ОО, 0 < в < 1. По определению / € X принадлежит пространству [X, У]0,оо тогда и только тогда, если существует такое С > О, что для всех t > 0 выполняется ки,г)<а9, (0.0.7) где ки,1) = ки,г,х,¥) := шШ/ - Щх + т\у}. пеУ

В качестве нормы |/|[х,у]0оо> берется инфимум по числам С, для которых выполняется неравенство (0.0.7).

А. Вэррон, А. Коэн, В. Дамен, и Р. ДеВор [27] доказали оптимальность ОЖА в интерполяционных пространствах [Н,А\(^У)]в,оо-> Для всех в, 0 < в < 1. В случае малых в чисто жадный алгоритм также является почти оптимальным:

Теорема 1.15. Для произвольных в, 0 < в < 1/3 и е, 0 < е < в/2. Существует такое С > 0 что для всех / € [Н, Л\{Т>)\е^оо итп> 1 справедлива оценка - 0™А№)\\ < С|/1[Н,Аг(Т>)]в,оот~в^2+е'

В параграфе 1.8 доказываются оценки снизу на скорость убывания наилучшего т-членного приближения для интерполяционных классов.

Из теорем 1.12 и 1.13 вытекает, что если не накладывать на словарь Т) никаких дополнительных ограничений, то жадные алгоритмы не могут гарантировать скорость сходимости, лучшую чем Ст-1/2 даже для разреженных целевых функций (функций из Ло(Т>)). Тем не менее оказалось, что при наложении на словарь некоторых ограничений, связанных с когерентностью, скорость сходимости жадных алгоритмов может быть значительно выше.

В главе 2 исследуются скорость сходимости жадных алгоритмов по словарям с малой когерентностью. В начале параграфа 2.1 приводится определение когерентности, указывается пример переполненного словаря с малой когерентностью, построенный на основе Бернуллиевской матрицы, дается краткая историческая справка и приводятся формулировки основных результатов.

Определение 2.1. Когерентностью словаря Т> будем называть величину fi:= sup \(ф,ф)\. ф,фє&, ффip

Словари с когерентностью ¡і будем называть ^¿-когерентными.

Сходимость ортогонального жадного алгоритма по словарям с малой когерентностью изучалась в работах Р. Грибонваля, М. Нильсена, Д. Донохо, М. Элада, В.Н. Темлякова, А. Гильберт, М. Мутукришнана, Дж. Штраус-са, Дж. Троппа и др. ([51], [43], [49], [85]). Интерес к этому направлению в значительной степени обусловлен тем, что получаемые здесь результаты оказались востребованы в задаче "сжатых измерений" (compressed sensing).

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

Теорема 2.1 ([51], [49], [85]) Пусть задан словарь!) с когерентностью fi и функция f € Ао(Т>). Если l/loC^ + l), (0.0.8) mo для любого rri > |/|о имеет место равенство f = GgaA(f,V).

Как было показано В.Н. Темляковым и П. Желтовым [84], константа 1/2 в неравенстве (0.0.8) не может быть увеличена.

Устойчивость точной аппроксимации разреженных целевых функций интенсивно изучалась. Следуя В.Н. Темлякову, будем называть неравенствами типа Лебега оценки, связывающие ошибку аппроксимации жадного алгоритма и наилучшее га-членное приближение B(m)*m(f,V), m<C(ji). (0.0.9)

А. Гильберт, М. Мутукришнан и Дж. Штраусе [49] установили неравенство (0.0.9) для А(т) = га, В(т) = 8га1/2, С(ц) = 2~35fi~1 — 1. Константы в А(т) и В(т) были несколько улучшены Дж. Троппом [85] (см. также статью Д. Л. Донохо, М. Элада и В.Н. Темлякова [43].) Позднее Д. Л. Донохо, М. Элад и В.Н. Темляков [44] значительного улучшили В(т) и доказали неравенство (0.0.9) с А(т) = [mlogmj, В(т) = 24, С {¡л) = В своей недавней работе [84] В.Н. Темляков и П. Желтов приблизили значение С {¡л) к оптимальному, доказав оценку (0.0.9) с А(т) — m[2^logrn\, В(т) = 3 и С(у^), которое должно обеспечить неравенство m2V21ogTO ^¡i 1 для m < C(fi). В параграфе 2.1 получено точное по порядку неравенство типа Лебега (для ортогонального жадного алгоритма).

Теорема 2.7 Для произвольного ц-когерентного словаря Т) и функции f G Н справедлива оценка f-G^A(LV)\\<3am(f) для всех 1

1 < га <

20 ц

Этот результат доказывается в пунктах 2.1.1 — 2.1.4. В параграфе 2.2 исследуются словари с ограниченной совокупной когерентностью. Следуя Дж. Троппу [85], введем определение.

Определение 2.2. Совокупной когерентностью счетного словаря Т> будем называть величину xi(X>):=sup \(9>9)\

3&>

Будем говорить, что словарь Т> имеет ограниченную совокупную когерентность, если для него Ц\{Т>) < оо.

Хорошо известно, что если для словаря Т> имеет место оценка /¿1(1}) < 1/2, то для него выполняется так называемое 1тарр^-свойство. Следующий результат в том или ином виде присутствует во всех работах по скорости сходимости жадных алгоритмов, в которых накладываются ограничения на когерентность словаря.

Теорема 2.8 (1гаррп^-свойство, [51], [43], [49], [85]) Пусть заданы словарь Т> с <1/2, его конечное подмножество и / € эрап^о); ф 0. Тогда о 5€Х>\£> О

Теорема 2.8 гарантирует, что если / е зрап(Х>о), где V0 конечное подмножество £>, то на каждом шаге жадного алгоритма очередной элемент словаря будет выбираться из Х>о- Тем самым, в случае ортогонального жадного алгоритма за конечное число шагов (¡^о) будет получено точное решение, а в случае чисто жадного алгоритма будет иметь место экспоненциальная скорость сходимости (как в конечномерных пространствах).

При малых значениях Ц\(1У) чисто жадный алгоритм обладает оптимальной скорость и в пространстве А\(Т))

Теорема 2.9. Пусть заданы словарь Т> с Ц1(Т>) < 1/3 и / € Л\{ТУ). Тогда

Н/-ССЛ(/^)11<1/|1 т> 1.

Теорема 2.9 была обобщена на более широкие классы. Определим классы АР(Т>). 1 < р < оо. Положим для М > О

Ар(Ъ, М) := : |са|р < ЛГр, сЛ € Ж, д* € 2>, ДЛ < оо}, лел аел где замыкание берется в норме пространства Н. Пусть

АР(Э) := У ЛР(£>,М), м> о

1/1 р := |/иР(р) М{м > 0 : / € М)}, / £ Ар(7>).

Теорема 2.10. Пусть заданы словарь V с ^л\{Т)) <1/3, р, 1 < р < 2 и / е АР(Т>). Тогда найдутся С\ = С\{р) > 0 и С2 = С2(^1(Т>)) > 0 такие, что для любого т > 1 ц/2>)|| = ц/т|| < ^Са!/^-1/^.

В главе 3 исследуется вопрос о получении для целевой функции / разложений по элементам словаря V вида оо ~ $>*(/ы/), <*(/) € к, £*(/) е V, к—1 частичные суммы которых т

Х>(/ыл к=1 достаточно хорошо приближают / (при этом различность <?&(/) не требуется). Легко видеть, что чисто жадному алгоритму соответствует так называемое ЧЖА-разложение оо ~ Аи "к-1 > 9к )9к » с=1 в то время как ортогональному жадному алгоритму, в силу того, что на каждом шаге идет полный пересчет коэффициентов, никакое разложение не соответствует.

В главе 3 будут построены разложения, частичные суммы которых на классах Л\(ТУ) и [Я, А\(Т))\е,оо обеспечивают скорость приближения близкую к оптимальной.

Первые разложения, превосходящие по скорости ЧЖА-разложения были предложены В.Н. Темляковым в работе [80] (см. также [75]). Им был рассмотрен слабый жадный алгоритм с параметром Ъ и получены оценки на его скорость сходимости

Слабый жадный алгоритм с параметром Ъ (СЖАв) Пусть заданы последовательность ^ [0> параметр Ь, 0 < Ъ < 1, словарь Т> и целевая функция /¿^САЬ := /о := / € Н. Положим С1^сль(/:Т>) := 0. Последовательно для каждого т > 0 выбираем вектор АЬ := дт+\ € Т> такой, что

I (/т; 9т+1) | > *т+18ир|(/то,р)| деъ и определяем

С^Л/, V) := V) + Ъ(и дт+1)9т+1, ш+1ЛЬ '■— /т+1 I ~ З^Ч/; — /та ~ Ь(/т» Йт+Х^те+Ь

В.Н. Темляков [80] доказал, что для произвольного элемента / £ Л.х(Х') и т > 1 справедлива оценка т и - о%вАЬи,ъ)\\ < + (0.0.10) к= 1

Легко видеть, что если для достаточно малого е > 0 положить

Ь — е, = 1 — б, т > 1, то порядок скорости сходимости СЖАЬ окажется близким к —1/4, т.е. существенно лучшим по сравнению со скоростью сходимости ЧЖА.

Перейдем к определению возвратного жадного алгоритма, который, с одной стороны, как чисто жадный алгоритм дает разложение целевой функции в ряд по элементам словаря, а с другой, как ортогональный жадный алгоритмы, дает правильную в полиномиальной шкале скорость сходимости в классах А\{Т>) и [Я, Л\{Т>)]в^, 0 < в < 1.

Возвратный жадный алгоритм (ВЖА) Пусть заданы вектор / е Н, словарь V и число 0 < £ < 1. Положим ¡$ес<ЭА := /о = /, (/,£>, £) := <30(/,1>,*) := 0. Предположим, что для п > 0 уже определены /ь ., /„ е Н, <71,., дп е V и С],., сп £ М. Причем к

Л = / - V*, 1 < Л < п. (0.0.11) 1

Обозначим через

Аг := АЛ/о,®,«) := {9к}Ъ=1, (°-0-12)

Уп(д) := уп{9, /о, V, *) := ^ с*; (0.0.13) к<п,дк=д

Ьп ■= Ъп(/о,7),Ь) := ^

0"п = (/п) /тг) •

Если п > 1 и существует хотя бы один вектор д е Оп такой, что выполняются неравенства тт(\уп(д)\,\ап,д)\) >

Дп*2

9ЬП ' и sign {уп(д)) = з1§п((/п, $)), то положим

9п+\Л := 0п+1 := сп+1 = sign«/„,£» тт(|г;п(5)|, |</„,^)|).

Будем называть такие шаги возвратными. В противном случае, выберем произвольный д^с\СА = дп+1 £ Т>, удовлетворяющий неравенству п, 9п+1)\ > * вир | (/п,£)| 362? и положим сп+1 ~ (1п,9п+1)

Будем называть такие шаги жадными. Определим аппроксимант и остаток: п+1 А=1 уДесСЛ Сп+1^п+1 = у (2п+1(/,Х>, ¿),

•что гарантирует выполнение (0.0.11) на следующем шаге алгоритма. Ряд оо п=1 будем называть возвратным жадным разложением элемента / по словарю V.

В параграфе 3.2 доказывается следующая теорема о сходимости возвратных разложений.

Теорема 3.2 Для произвольного словаря Т>, целевой функции / Е Н и 0 < £ < 1, возвратный жадный алгоритм сходится:

В параграфе 3.3 установлены следующие две теоремы о скорость сходимости ВЖА.

Теорема 3.3. Для произвольного t, 0 < t < 1, существует такая константа К = K(t) > 0; что для произвольного словаря V, целевой функции f Е А1 (V) и всех п > 1 имеет место неравенство

Теорема 3.4. Для произвольных числа і є (0,1] и в є (0,1], существует такая константа К = в), что для любого словаря Т>, целевой функции f є [Н,Лі(Т>)]ду00 и всех п> 1 имеет место неравенство

Замечание 3.2. В отличие от оценки? (0.0.10) показатель степени в оценках скорости сходимости в теоремах 3.3 и 3.4 не зависит от параметра

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

Ясно, что при наложении дополнительного условия (неотрицательность коэффициентов) на п-членное приближение, мы должны также наложить дополнительное условие на словарь Т>, чтобы построение соответствующего приближения было возможным. Множество Т> С Н будем называть положительным словарем, если g Є V =>- \\g\\ = 1, {J>a<7a I ел > 0, дхЄ V, ЦА < оо} = Н. (0.0.15) lim ||/ — G„ecGA(f, V, £)|| = 0.

II/ - G^cGA(f,V,t)\\ < K\f\Mv)n~V4nn.

II/ " G^GA(f,V,t)|| < K\f\[HtAimetOBn-^]nn. n

0.0.14) аєл

А. Бэрроном [26] был предложен способ построения неотрицательных п-членных приближений с помощью релаксационного жадного алгоритма. Из результатов работы [27] вытекает, что релаксационный жадный алгоритм сходится для произвольного положительного словаря Т> и целевой функции /о, этот алгоритм также обладает хорошей скоростью сходимости, оптимальной для интерполяционных классов. С другой стороны, релаксационный жадный алгоритм дает только n-членные приближения (0.0.14), но не дает разложения оо к=1 кроме того, последовательность норм остатков не обязана монотонно убывать. В параграфе 3.4 мы рассматриваем "положительные аналоги" чистого жадного и слабо жадного алгоритмов, которые обеспечивают построение разложений (0.0.16), т.е. обладают свойством оперативности (on-line свойством), и частичные суммы которых (0.0.14) монотонно (в смысле нормы остатка) стремятся к целевой функции. (При этом с точки зрения скорости сходимости они могут уступать релаксационному жадному алгоритму).

При определении "положительных" версий ЧЖА и СЖА (ПЧЖА и ПСЖА) используются обозначения (0.0.12) и (0.0.13). Отметим, что ПЧЖА и ПСЖА не гарантируют неотрицательность всех коэффициентов Ск в разложении (0.0.16), но любая частичная сумма ряда может быть рассмотрена как n-членное приближение с неотрицательными коэффициентами. п к=1 geDn

Положительный чисто жадный алгоритм (ПЧЖА) Пусть заданы целевая функция /о := / 6 Н и положительный словарь Т>. Положим GQGA+(f,T>) := 0. Последовательно для каждого т. > 0 выбираем вектор 9т+1 еТ> и cm+1 > -vm(gm+1) так, чтобы fm - Crn+l9m+l\\ = inf || fm - eg||, geV, c>-vm(g) и определяем G™A+(f,V) + cm^g^! и fm+1 — f — ~ fm~ Cm+l£m+l

Отметим, что для фиксированных g £ Т> и / £ Н величина infc>„ ||/ — eg || достигается при с = тах(—-и, (/, д)).

Для g G Х> определим Кгп{д) ■= sup ||/m||2 — ||/m — Сд\\2 = sup (fm,fm c>-vm(g) c>—vm(g) frn ~ fm - eg) - sup 2c(fm,g) - c2 = c>-vm(p) f </m,5>2, (/m,3> > -Vm(<7)

I vm(g)(-2(fm, g) -vm(g)), (fm,g) <

Таким образом, легко видеть, что определение элемента дт+\ и числа cm+i по формуле (3.4.4) можно переписать дт+1 : ifm(5m+i) = sup KmÇg), gev

Cm+i - max(-um(5m+i), (/m,£m+i)), (0.0.17) i) = ||/m||2-||/m+i||2.

Слабый жадный алгоритм отличается от чисто жадного тем, что на очередном шаге алгоритма при выборе вектора максимизирующего скалярное произведение нам разрешается "ошибаться" при вычислении скалярного произведения в ¿"^раз. Таким образом, мы приходим к определению.

Положительный слабо жадный алгоритм (ПСЖА) Пусть фиксирована последовательность коэффициентов слабости г = {¿m}m=i ^ [0,1]. Для целевой функции /о := / G H и положительного словаря Т> положим G^GA+(f,T>,T) := 0. Тогда последовательно для каждого m > 0 выбираем вектор gm+i G Т> такой, что

Кт(ат-4-1 ) > sup / > tm+l (fmi g) > ~Vm С9) m\ m+ ^ I Wl%(fl)(-2(/m.ff) -vm(g)), Wl(/m,fl) < -Vm(g) '

0.0.18) определяем cm+1 no формуле (0.0.17) и полагаем

GZ?iÂ+(f, V., г) := G%GA+(f, V, г) + и fm+l = f — Gm+^ifi T) = fm~ Cm+l9m+l

Отметим, что, согласно определению Km(g), имеет место равенство m+l)=ll/m||2-||/m+l||2>0.

Определение ПСЖА корректно. Как и в случае СЖА, для любого tm+i G (0,1) мы всегда можем осуществить m-ый шаг алгоритма, т.е. найти gm+i G V, удовлетворяющий (0.0.18). Это вытекает из следующей леммы.

Лемма 3.3. Для любых д ЕТ> и т > 0 имеет место неравенство

К (п\ / (1т,д)2, > -Ут(д) > т[9) \ут(д){-щт,9)-ут(д)), (/т, д) <-ут{д) ~ / *т+1(1т,д)2, ¿т+1 (/т,д) > \ - ¿ш+1 (1т, д) < ~Ут(д)

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

Теорема 3.5. Для произвольного положительного словаря V и целевой функции / Е Н выполняется

Ит ||/-С£сл+(/,Е>)||=0.

771—> ОО

Теорема 3.6. Для произвольного положительного словаря Т>, целевой функции / € Н и последовательности коэффициентов слабости {¿т}т=1 ^ [0,1], удовлетворяющей равенству

00 * I" гп

771=1 * имеет место соотношение

СА+,

Нт ||/-СГл+(/,0,г)|| = 0. т—»оо

Необходимое условие сходимости СЖА для монотонных последовательностей коэффициентов слабости, полученное В.Н. Темляковом и автором ([89], теорема 1), может быть перенесено-на,случай ПСЖА.

Теорема 3.7. Пусть задана последовательность коэффициентов слабости т — {¿ш}т=1 с [0? 1]; удовлетворяющая неравенству

00

V — < оо. (0.0.20) т

771=1

Тогда найдутся положительный слоёарь Т> с Н и целевая функция / е Н такие, что найдется реализация ПСЖА Т>: т)}^=0; для которой

Ит \\/-а%сл+илт)\\>0. гп—»оо

Глава 4 посвящена изучению сходимости и скорости сходимости жадных алгоритмов в банаховых пространствах. Это направление развивалось с конца 1990-х - начала 2000-х годов в работах В.Н. Темлякова, С. Дилвор-фа, Д. Куцаровой, C.B. Конягина, П. Войташчека, Н. Калтона, C.JI. Гогяна и др. ([39], [59], [78], [79], [86], [47], [6]) для многих результатов о сходимости жадных алгоритмов в гильбертовом пространстве нашелся "банаховый" аналог.

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

Пусть X = (X, || ■ ||) - действительное банахово пространство, a D С X словарь в нем. Для / € X обозначим через Ff опорный функционал к /:

FfeX\ ||*>|| = 1, *>(/) = ||/||. (0.0.21)

Для f,g еХ, ||р|| = 1 определим

M 9)еЖ: ||/ - Я/, д)д\\ = inf ||/ - у.д\|, (0.0.22) rq(f,g) := \\f\\q-\\f-Kf>g)g\\q, q> 0, r(f,g) := n(f,g) = II/II - \\f - fi(f,g)g\l Отметим, что согласно теореме Хана-Банаха функционалы, удовлетворяющие (0.0.21), существуют и в качестве Ff можно выбрать любой их них. В случае, если пространство X является гладким (по Гато), то для любого / G X выбор Fj становится однозначным. Аналогично, в качестве /л(/, д) берется любое число, удовлетворяющее (0.0.22), которое в строго выпуклых пространствах определяется однозначно.

Х-ЖАДНЫЙ АЛГОРИТМ (Х-ЖА). Пусть задан словарь V и целевая функция /о := / G H. Положим GjfGj4 (/,£>) := 0. Последовательно для каждого m > 0 выбираем вектор gm+i G Т> такой, что r(fm, 9т+1) = sup r(/m, g) gev и определяем

G™tif,V) ■= GlGA{f,V)+nUm,9m+l)gm+l, fm+1 •= f — V) = fm — ß{fm. gm+l)9m+l

В. Дубинин [45] отметил, что гладкость пространства является необходимым условием для сходимости Х-жадного алгоритма. В параграфе 4.2 доказывается, что гладкость пространства не является достаточным условием сходимости.

Теорема 4.1. Существует гладкое (по Гато) банахово пространство X, словарь V С X и f G X, для которых lim ||/m|| = lim \\f-G^GA(f)\\^0.

771—>оо m—J-oo s

Рассмотрим другие обобщения ЧЖА.

Двойственный жадный алгоритм с параметром t (D-ЖА). Пусть задан словарь Т>, целевая функция /о := / € X и фиксированное число t, 0 < t < 1. Положим Т>, t) := 0. Последовательно для каждого т > 0 выбираем вектор gm+i € Т> такой, что

Ffm(9m+i)\ >tsup\Ffm(g)\, geV и определяем

GSS.f(f,V,t) := G°GA(f,V,t) +{i(fm, gm+i)9m+u fm+1 f ~ G^f(fiV) — fm ~ V(fm, 9m+l)9m+l

В.-ЖАДНЫЙ АЛГОРИТМ С ПАРАМЕТРАМИ t и g (Д-ЖА). Пусть задан словарь Т>, целевая функция f € X и фиксированные числа t, 0 < t < 1 и q, q > 0. Положим GQGA(f,V,t,q) := 0. Для каждого m > 0 последовательно выбираем вектор gm+i £ Т> такой, что rq{fm: 9т+1) , г<7 lM(/m,5m+l)l ~ <7€оИ/тп,р)| гг определяем m+f (/> t, ч) := 2?, i, g) + м(/т, £m+i) W, fm+1 f — G^+f (/, X>, t, q) = fm — fl(fm, £7m+l)i7m+l

Отметим, что, если X является гильбертовым пространством, то Х-ЖА, D-ЖА с t = 1 и Я-ЖА с /; = 1, g = 2 в точности совпадают с ЧЖА.

Выбор параметра q в формулировке Л-жадного алгоритма может оказывать влияние на скорость сходимости, но сам факт сходимости от него не зависит:

Лемма 4.1. Пусть заданы банахово пространство X и словарь D с X. Если существует до > 0, что для всех 0 < t < 1, всех f £ X и произвольной реализации R-жадного алгоритма выполняется lim ||/ — G^fA(f,V, t, до) || = 0, m—>оо то для всех q> 0, 0<t<l, feX и произвольной реализации R-жадного алгоритма имеет место равенство lim \\f-G^Ä(f,V,t,q)\\=0. m—* оо

Оказалось, что для сходимости жадных алгоритмов в равномерно выпуклых и равномерно гладких пространствах (где, в частности, fi(f, д) и Ff(g) определены однозначно) важную роль играет следующее дополнительное геометрическое свойство:

30 > 1 : V/, д € X \\д\\ = 1, Qr(f,g) > \ß(f,g)Ff(g)\. (0.0.23)

В параграфе 4.3 доказывается общая теорема о сходимости Л-жадного алгоритма.

Теорема 4.2. Пусть X равномерно выпуклое, равномерно гладкое банахово пространство, для которого выполняется условие (0.0.23), uD словарь в нем. Тогда для всех 0 < t < 1, q > 0, для любой / 6 X и произвольной реализации R-жадного алгоритма выполняется lim ||/ — G^A(f,V,t,q)\\ = 0. т—>оо

В параграфе 4.4. показывается, что под условия теоремы 4.2 попадет достаточно широкий класс банаховых пространств.

Теорема 4.3. Пространства lp, р > 2, обладают свойством (0.0.23).

Эти теоремы тесно связаны с результатами М. Ганичева и Н. Калтона [47], которые доказали справедливость утверждения теоремы 4.3 для всех р, р > 1, и доказали сходимость D-ЖА. Подробности приведены в конце параграфа 4.1.

Хорошо известно, что Х-жадный алгоритм сходится в любом конечномерном гладком банаховом пространстве (т.е. для всех / 6 X и словарей Del выполняется lim ||/ - G*GA(f)\\ = 0.) тп—too

В своей недавней работе [38] С. Диворф, Д. Куцарова, К. Шуман, В.Н. Темляков, П. Войташчек установили слабую сходимость Х-жадного алгоритма для банаховых пространств, обладающих И^Х-свойством. С. Диворф, Е. Оделл, Т. Шлумпрехт, А. Зак [40] получили интересные результаты о сходимости Х-жадного алгоритма в пространствах Lp(0,1) для разреженных целевых функций. В тоже время никаких общих "положительных" результатов о сходимости Х-жадного алгоритма, в бесконечномерном банаховом пространстве, не являющимся гильбертовым, на сколько известно автору, получено не было. Более того, остается открытым вопрос о сходимости Х-жадного алгоритма (для всех целевых функций) в пространстве Ьр{0,1), р ф 2, по системе Хаара.

В параграфе 4.5 изучается скорость сходимости Х-жадного алгоритма в Lp(0,1), 1 < р < 2, для системы Хаара и системы функций, пропорциональных индикаторам двоичных интервалов.

Напомним определение системы Хаара Tip = {IIn}m=i в пространстве Lp{0,1), р > 1. Положим Hi(t) = 1. Пусть т = 2к + г, /с > 0, 1 < г < 2*. Следуя [11], рассмотрим двоичные промежутки

Am '■= А* '■= [' 2* > gjfe)» г-1 2г — 1ч

Дт (ДА:) : = [ 2fc+l ' 2*) =

Определим

2^, Ь е Д+ Ят(£) = < —2к/р, I е Ао, г £ Ат

Известно, что эрапНр = 1/р(0,1), поэтому, в силу равенств \\Нт\\ = 1, гп > 1, система Хаара Ир является словарем.

Для произвольного измеримого Д С [0,1) обозначим через |Д| его меру Лебега. Определим иг) - I 1Д1"1/Р' 1 е л ~ { о, £ е [о, 1] \ д.

Легко видеть, что ||/д|| = 1. В работе также изучается система функций Хр, пропорциональных индикаторам двоичных интервалов. Положим тп дт, m > 2,

Ер '■ {-^т}т=2

Приближение системой Хр было рассмотрено Т.П. Лукашенко в статье [14]. Легко видеть, что для любого гп > 1

Ет(Яр) С Е2ш{Тр) (0.0.24) см. определение (0.0.6)), но в противоположную сторону аналогичные включения не верны т(2р) £ ЕМ(ПР\ УМ > т. Для положительной функции ф 6 С(М+) рассмотрим класс

Афф,Х) = Лф(Р) = {/ € X : ат(/,£>,Х) < ф(т), т > 0}.

Теорема 4.4. Для любого р, 1 < р < оо; существует такое ао = &о{р) > 0; что для произвольной положительной убывающей функции ф £ Сх(М+), удовлетворяющей неравенству ИтЫ£(1п> -а0, (0.0.25)

-»оо ф(^) £—>оо для любой / £ Лф{Хр) и для произвольного т > 1 будет справедлива оценка где константа С > 0 зависит от р и ф(-), но не зависит от / и т.

Отметим, что для произвольных 0 < а < «о, ^>0, а + ^>0,иС>0 для функции ф £ Сх(М+) вида ф{1) = С (г + 1)-а(1п(г + 2))~Р выполняется неравенство (0.0.25).

Из теоремы 4.4 выводится сходимость Х-УКА по системе Хр для всех / £ Ьр(0,1).

Теорема 4.5. Для любого р, 1 < р < оо и целевой функции / £ Ьр(0,1) имеет место равенство

Ит ||/-С^(/Д,)||=0.

ТП—»оо

Имеет место следующий результат о скорости сходимости Х-жадного алгоритма для системы Хаара в пространствах Ьр(0,1), 1 < р < 2.

Теорема 4.6. Для любого р, 1 < р < 2, существует такое «о = &о(р) > 0; что для произвольной положительной убывающей функции ф £ Сі(Ж+); удовлетворяющей неравенству

Шппгї = ИшіпН (1п(0(г)))' > —ого, оо ф(£) ¿—їоо для любой f £ Лф{Хр, Ьр{0,1)) и для произвольного т > 1 будет справедлива оценка

1-0^Л(1,Пр)\\ = Ц/Л < с1(?3(т)(1п(т + 1))^т+2; где константа сі > 0 зависит от р и ф(-), но не зависит от / и т. Из справедливости включения (0.0.24) вытекает

Теорема 4.7. Для любого р, 1 < р < 2; существует такое ао = ао{р) > 0, что для произвольной полоэюительной убывающей функции ф £ Сі(]]&+), удовлетворяющей неравенству тіїгї = 1ітіпН(1п(фН))' > -а0, оо фу,) ¿->ос для любой / є Аф(Нр, Lp(0,1)) м для произвольного m > 1 будет справедлива оценка

1/ - G*GA(f,Hp)\\ = ||/m|| < c20(m)(ln(m+ 1))А+2, где константа ф > О зависит от р и </>(•), ко не зависит от f и т.

Из теоремы 4.7 вытекает сходимость Х-жадного алгоритма на достаточно широком подклассе Ьр{0,1), 1 < р < 2.

Теорема 4.8. Пусть задано р, 1 < р < 2, и функция / є Lp(0,1), для которой существует такое Ô > 0, что supат{/,Пр)Мт + 2))^î+2+5 < оо. т> О

Тогда lim ||/ — G^lGA(f,'Hp)\\ = 0.

Замечание 4.1. При р = 2 система Хаара Т-І2 является ортонорми-рованным базисом в пространстве (0,1), м хорошо известно, что для любой / є 1/2(0,1)

II/ - С™Л(/,Н2) II = II/ - = ат(/,я2), то есть теоремы 4-7 и 4-8 в случае р — 2 не являются оптимальными.

Замечание 4.2. Если в банаховом пространстве X задан базис Шаудера В = {фк}&=1, то т-членные приближения к / є X по системе В, можно получать с помощью метода, основанного на разложении / в ряд по базису В оо = ^2ск(ЛФк, к=1 и существенно отличного от изложенного выше X-жадного алгоритма. Этот метод основан на переупорядочении коэффициентов разложения в порядке убывания модуля

М)\ > Ы/)\ > ■ ■.

В качестве т-членного приближения О^ії, В) берется

ТП ¿=і

В.Н. Темляков [72] доказал, что для произвольного р > 1 найдется такое число С(р) > 0, что для всех / є Ьр(0,1) и т > 1 выполняется неравенство

-ад.^н^сср)^/,?^).

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

Теорема 4.9. Для любого р, 1 < р < 2, существуют такие числа с"з,с4 > 0, что для любого п Є N и Н Є Т,п(Хр), ||/г|| = 1 найдется конечное множество индексов Ао С М, для которого выполняются следующие неравенства сз г (/г, Н\) > —, для любого А Є Ао, п г(/г, Нх) > с4 (1п(п + І))"^"1, аєл0

Этот результат доказывается в параграфах 4.7, 4.8. С его помощью в параграфе 4.9 доказывается теорема

Теорема 4.10. Для любого р, 1 < р < 2, существуют такие сё, сё > О, что для любого п Є N, її є ЕП(ХР); ||/і|| = 1 и функции / Є Ьр(0,1) такой, что f-hW < с5 (1п(п + 1))-^ї-2 , найдется Ао Є для которого о> г(/, ЯАо) > п

В параграфе 4.10 теорема 4.10 применяется для доказательства теоремы 4.6, с помощью которой там же устанавливается справедливость теоремы 4.8. В параграфе 4.11 приводится доказательство теорем 4.4 и 4.5.