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

Оглавление
Введение 4
1 Скорость сходимости чисто жадного и ортогонального жадного алгоритмов 28
1.1 Сходимость жадных алгоритмов................................ 28
1.2 Реализуемость жадных алгоритмов для дискретных словарей 31
1.2.1 Вспомогательные леммы................................ 31
1.2.2 Доказательство теорем 1.1 и 1.2 - 37
1.3 Скорость сходимости жадных алгоритмов и наилучшис т-членные приближения.............................................. 42
1.4 Оценка снизу на скорость сходимости чисто жадного алгоритма 51
1.4.1 Общие формулы........................................ 51
1.4.2 Конструкция.......................................... 53
1.4.3 11одбор параметров................................... 54
1.4.4 Дальнейшие оценки.................................... 56
1.4.5 Окончание доказательства теоремы 1.12................ 63
1.5 Оценка снизу на скорость сходимости ортогонального жадного алгоритма........................................................ 64
1.6 Интерполяционные классы..................................... 66
1.7 Оценки сверху на скорость сходимости чистого жадного алгоритма для интерполяционных классов............................... 68
1.7.1 Численные неравенства................................ 68
1.7.2 Основные определения и неравенства для ЧЖА .... 73
1.7.3 Множества Д(то) ..................................... 74
1.7.4 Оценка произведений атЬт............................. 77
1.7.5 Доказательство теоремы 1.16.......................... 81
1.8 Нижние оценки для интерполяционных классов......... 82
2 Скорость сходимости жадных алгоритмов для словарей с малой когерентностью 84
2.1 Неравенства типа Лебега..................................... 84
2.1.1 Вспомогательные леммы................................ 87
2.1.2 Вспомогательные обозначения.......................... 90
2
2.1.3 Основные леммы.......................................... 91
2.1.4 Доказательство теоремы 2.7.............................. 98
2.2 Словари с ограниченной совокупной когерентностью...............100
3 Жадные разложения 108
3.1 Возвратный жадный алгоритм.................................... 108
3.2 Сходимость возвратного жадного алгоритма. Доказательство теоремы 3.2...................................................... 111
3.3 Скорость сходимости возвратного жадного алгоритма..............114
3.3.1 Оценка а к# Б к........................................ 114
3.3.2 Основная лемма......................................... 119
3.3.3 Доказательство теорем 3.3 и 3.4.........................124
3.4 Жадные разложения с неотрицательными коэффициентами . 127
3.4.1 Основные определения................................... 127
3.4.2 Сходимость ПСЖЛ........................................ 131
3.4.3 Связь между СЖА и ПСЖА. Необходимое условие сходимости ПСЖА................................................ 134
4 Жадные алгоритмы в банаховых пространствах 136
4.1 Введение...................................................... 136
4.2 Пример расходимости Х-УКА в гладком банаховом пространстве 139
4.3 Сходимость Я-ЖА............................................... 153
4.4 Некоторые геометрические свойства пространства 1ру р > 2 . . 157
4.5 Система Хаара и система функций пропорциональных индикаторам двоичных промежутков..................................... 163
4.6 Схема доказательства теоремы 4.6.............................. 166
4.7 Вспомогательные леммы......................................... 167
4.8 Доказательство теоремы 4.9.................................... 169
4.8.1 11риближение характеристическими функциями двоичных промежутков............................................. 169
4.8.2 Двоичные деревья....................................... 172
4.8.3 Окончание доказательства теоремы 4.9................... 182
4.9 Доказательство теоремы 4.10................................... 192
4.10 Сходимость и скорость сходимости X ЖА по системе Хаара . 199
4.11 Сходимость и скорость сходимости X Ж А по системе Хр . . . 203
Литература 208
3
Введение
Теория приближения относится к тем областям математики, которые тесно связаны с прикладными задачами естествознания и техники. Увеличение мощности вычислительных систем, происходившее в последние десятилетия, позволило приступить к решению новых более вычислительноемких задач. Одной из них является построение “индивидуального приближения” для заданной функции / из некоторого класса К. Приближение предлагается строить как элемент линейного подпространства L из заранее определенного (по К) семейства линейных подпространств С. При этом выбор L Є С зависит от /, что отличает эту задачу от классической задачи аппроксимации класса К, где приближающее подпространство L выбиралось единым для всех / Є К. Другими словами, класс К приближается нелинейным объектом Uієс^- Такие приближения имеют также важное теоретическое значение. Как было показано P.C. Исмагиловым (9|, К.И. Осколковым [17] и В.Е. Майоровым [16] этот нелинейный (индивидуальный) подход может давать преимущества в некоторых классических задачах. Изучение оценок снизу для этого метода приближения было начато Б.С. Кашиным [10].
Начиная с 80-х годов 20-го века, в рамках математической статистики и теории приближения стали интенсивно изучаться жадные алгоритмы, что, с одной стороны, дачо теоретическое обоснование ряда методов вычислительной математики, а, с другой стороны, позволило получить конструктивные способы нахождения наилучших m-членных приближений. Ключевую роль в формировании теории жадных алгоритмов сыграли работы Дж. Фридмана, В. Стузла, С. Маллата, Ж. Жанга, П. Хыобера, J1. Джоунса, А. Бэррона, Р. ДсВора, В.Н. Темлякова, С.В. Конягина, Д.Донохо и др. ([46], [64], [53], [54], [25], [37], [58], [34], [41]). В наши дни жадные алгоритмы успешно применяются в задачах распознавания образов, медицины, финансовой математики, обработки сигналов и ряде других областей ([42], [85], [70], [66], [65]).
Необходимо отметить, что со временем большая часть результатов по жадным алгоритмам начала формулироваться и доказываться на языке теории функций. Болес того, идеология теории функций в значительной степени определила направления дальнейших исследований жадных алгоритмов.
Пусть X = (X, II • (І) — действительное банахово пространство. Множе-
4
ство V. V С X, будем называть словарем, если оно состоит из векторов с единичной нормой, и замыкание линейной оболочки V совпадает со всем X:
д еТ> => Ц^Н = 1. Щ5ап£> = X.
Для произвольного элемента / € X и тп 6 N требуется найти конечную линейную комбинацию тп элементов словаря, достаточно хорошо приближающую /:
т
/ -+ 2>(/ЫЛ, «*(/) е к, <?,(/) е о. (0.0.1)
к=\
Особенностями данной постановки являются:
• от / зависят не только коэффициенты сД/), но и элементы словаря #*(/)> участвующие в приближении,
• словарь V может быть как базисом, так и переполненной системой. Важными примерами переполненных систем являются словарь плоских волн (пс^с-функций), ЯВК-словари, переполненные системы случайных векторов и. т.д.
При этом желательно, чтобы величина ошибки аппроксимации ||/ — ХХ=1 ск(/)9к(/)\\ была близка к значению наилучшего т-членного приближения (это понятие было введенного С.Б. Стечкиным в [21])
т
°т(/,) := а1п({, V) := стт(/, V, X) = Ы II/ —
сь-.^СтеК, ди...,дт€Т> '
к~А
В большинстве случаев, особенно для переполненных словарей, построение 772-членных приближений (0.0.1), пусть даже не наилучших, является весьма важной и интересной задачей.
Наметим подход к построению 7П-членных приближений с помощью жадных алгоритмов.
Пусть X является сепарабельным гильбертовым пространством Н —
(II, {., •)) с нормой II • II := {•, ->1/2.
ЧИСТО ЖАДНЫЙ АЛГОРИТМ (ЧЖА) Пусть задан словарь V с Н и ■целевая функция /0РСЛ := /о ;= / 6 Я. Положим Срсл(/. V) := 0. Последовательно для каждого т > 0 выбираем вектор дт+1 £ ^ такой, что
|(/т,<?т+1)| = эир|{/т!р)| (0.0.2)
и определяем
(/,*>) := <ЭТ/,Р) + (1т,дт+1)9т+и
fm+1 •— fm+l f — fm (frm 9m+l)0m+l'
Таким образом, для / и т > 1 построены m-членные приближения GPmGA{f:V).
Корректность определения gm+i по формуле (0.0.2) будет обсуждаться ниже, пока лишь заметим, что в случае конечномерного Н и конечного словаря V (случай приложений), супремум всегда достигается на каком-либо элементе словаря, и его вычисление, требует конечного числа действий.
Отметим, что ЧЖА строит разложение элемента / в ряд по словарю £>, максимально уменьшая на каждом шаге алгоритма норму остатка:
Il/m+i|| = inf II/,„ - с.д\\, т > 0.
СбЬц
Если V является ортоиормированным базисом в Я, то ЧЖА будет выбирать элементы словаря в порядке убывания коэффициентов Фурье функции / относительно этого базиса. Подобные приближения рассматривались в теории функций начиная с работы С.Б.Стечкина [21].
Для переполненных систем специального вида ЧЖА впервые появился в статистике в работе Дж. Фридмана и В. Стузла [46] под именем Projection pursuit regression, а также в теории передачи сигнала в работе С. Маллата и Ж. Жанга [64] иод именем Matching pursuit.
Необходимо также отметить, что ряд более ранних работ по теории функций, например. Е. Шмидта [71], а также B.C. Стечкнна и С.Б. Стечкина [20], может быть проинтерпретирован как результат о сходимости ЧЖА для словарей специального вида.
Жадные алгоритмы тесно связаны с орторекурсивными разложениями, которые в последние годы интенсивно исследовались Т.П. Лукашенко, В.В. Галатенко и др. ([14], [3], [4], [5] [15], [13], (18]).
С современным состоянием теории жадных алгоритмов можно ознакомиться, например, в обзоре В.Н. Тсмлякова [75].
Перечислим основные результаты работы, а затем приведем более подробное описание диссертации по главам:
1. Показано, что чисто жадный алгоритм не является оптимальным по порядку в пространстве А\(Т>). Получены оценки снизу на скорость сходимости чисто жадного алгоритма в пространствах Ло(Т^) и А\{Т>) достаточно близкие наилучшим известным оценкам сверху (A.B. Силь-ииченко). Тем самым получен ответ на вопрос Девора - Темлякова об оптимальности ЧЖА и с точностью до 0.01 определена константа Ко-нягина - Темлякова. (Теорема 1.12.)
2. Показано, что чисто жадный алгоритм обладает оптимальной по порядку скоростью сходимости в интерполяционных пространствах [Н, Ai(V)\q^ при 0 < в < 1/3. (Теорема 1.15.)
6
3. Получено точное по порядку неравенство типа Лебега для ортогонального жадного алгоритма по словарям с малой когерентностью. Ранее эта задача исследовалась в работах Д. Донохо, М. Эл ада, В.Н. Тем-лякова, А. Гильберт, М. Мутукришнана, Дж. Штраусса, Дж. Троппа, П. Желтова. (Теорема 2.7.)
4. Предложен возвратный жадный алгоритм, который позволяет получать жадные разложения, обладающие оптимальной но порядку скоростью в интерполяционных пространствах (//, Ai(T>)]gt(X) при 0 < 0 < 1, и, в частности, в Л\{Т>). (Теоремы 3.3, 3.4.)
5. Предложены положительный чисто жадный и положительный слабый жадный алгоритмы. Доказано, что если функция приближается элементами словаря с положительными коэффициентами, то жадные разложения, построенные с помощью этих алгоритмов, после приведения подобных будут иметь неотрицательные коэффициенты. Тем самым, получен ответ на вопрос Б.С. Кашина о конструктивном получении “положительных” m-членных приближений. (Теоремы 3.5, 3.6.)
6. Построен пример гладкого банахова пространства, словаря в нем и целевой функции, для которых Х-жадный алгоритм расходится. (Теорема 4.1.)
7. Найдено новое геометрическое свойство банаховых пространств, являющееся достаточным для сходимости некоторых видов жадных алгоритмов в банаховых пространствах. Доказана сходимость Я-жадного алгоритма в пространствах /р, р > 2. (Теоремы 4.2, 4.3.)
8. Исследована сходимость X-жадно го алгоритма в пространстве Ьр( 0,1) для конкретных систем: системы Хаара, и системы функций, пропорциональных индикаторам двоичных интервалов. Получены неравенства типа Лебега, а также доказана сходимость X-жадного алгоритма по “системе индикаторов” на всем пространстве Ьр(0,1), 1 < р < оо. (Теоремы 4.4. 4.5, 4.6, 4.7.)
В главе 1 изучается скорость сходимости чисто жадного и ортогонального жадного алгоритмов в гильбертовом пространстве. В параграфе 1.1 приводится определение чисто жадного и ортогонального жадного алгоритмов.
Ортогональный жадный алгоритм (ОЖА) Пусть задан слооарь V и целевая функция ftfGA := /о := / G Н. Положим GGGA{f,V) := 0. Последовательно для каждого т > 0 выбираем вектор gm+i € V такой, что
|(/m,№n+l)| = SUp|(/m,(?)| (0.0.3)
g£V
7
■и определяем
V) := Рго]8рап(9ь.
•чРт+і)^5
Также в параграфе 1.1 приводятся результаты Л. Джонса [54] и В. Дубинина [45] о сходимости ЧЖА и ОЖА: для любого гильбертова пространства Я, словаря V и целевой функции / 6 Я выполняются равенства
Легко видеть, что в сепарабельном пространстве дискретные словари ею более чем счстны.
Формально супремум в формулах (0.0.2) и (0.0.3) может не достигаться. Однако оказалось, что если словарь V дискретен, то для і:большинства” функций супремум в формулах (0.0.2) и (0.0.3) достигается на каком-либо элементе словаря на всех шагах алгоритма.
Теорема 1.1. Пусть задан дискретный словарь V. Тогда множество функций из Н, для которых па каждом шаге ЧЖА супремум достигается:
является мпоэюеством второй категории1 ( использовалось обозначение
Теорема 1.2. Пусть задан дискретный словарь V. Тогда мпоэюество функций из Я, для которых па каждом шаге ОЖА супремум достигается:
является множеством второй категории (использовалось обозначение
В параграфе 1.3 приводятся результаты о скорости сходимости жадных алгоритмов. Для получения оценок сверху на скорость сходимости жадного алгоритма, необходимо потребовать, чтобы целевая функция / принадлежала некоторому, зависящему от словаря, классу Л(Т>). Показано, что классы,
1под множествами второй категории в этой работе понимаются такие множества, дополнения которых являются множествами первой категории.
9и92СТ>, 9:^92
} Є Я І Уш {рт+1 Є V : К/ш><?т-н)| = эирК/т.д)!} ф 0
/п, = / — Ш
/ Є Я І Мт {дп,+\ Є V : |(/т,р„1+і)| = вир |</т, </)|} ф 0
Лп = /-С£сл(/,©))-
определяемые скоростью убывания наилучшего m-членного приближения, оказываются слишком широкими.
Теорема 1.5. Пусть заданы строго убывающие полооюительпые функции г, R G C(R+), для которых
lim r(t) = lim RU) = 0.
£->cx> £->оо
Тогда найдется словарь V. целевая функция f е Н и С > 0, для которых имеют место неравенства
Ош(Л £0 < R{rn), т > 1,
\\f-G™A(f,V)\\>Cr(m), т> 1,
II/ -0°таЛ{!,Щ\ >Ст(т), т> 1.
Таким образом, для получения нетривиальных оценок сверху на скорость сходимости жадных алгоритмов необходимо накладывать более жесткие ограничения на класс Л{Т>). Наиболее популярным в теории жадных алгоритмов является класс A\(V), определенный ниже.
Для словаря V и М > 0 рассмотрим класс
Al(V, М) :={/€#:/ = ]Гсл<?л, За G V, #Л < оо и £ |сл| < М)
А€Л АеЛ
и класс М), являющийся замыканием (в Н) класса A"(V, М). Далее
определим
Л (!>):= U
Л/>0
Для / G Ai(V), введем норму
l/Ui(x>) = inf{M > 0 | / € А\(Т>, М)}.
Отметим, что шар А\(Т>, 1) является замыканием выпуклой оболочки Т> и (-©).
Из результатов С.Б. Стечкина [21] и А. Бэррона [25] следует, что последовательность величин наилучшего га-членного приближения am(f/D) для / G A\(V) убывает не медленнее, чем Сга“1/2, и показатель -1/2 не может быть уменьшен даже для ортонормированного словаря.
Приводятся оценки сверху на скорость сходимости ЧЖА
||/ - Gpma\i,V)|| < С,|/U(p)m-ï. (0.0.4)
9
Р. ДсВор и В.Н. Темляков [37] доказали справедливость (0.0.4) для 7 = 1/6, С.В. Конягин и В.Н. Темляков [58] — для у = 11/62, Л.В. Сильни-чепко [19] — для 7 = 0.182.
Для построения нижних оценок необходимо построить словарь V, функцию / е A\(V), / Ф 0 и для нее оценить снизу скорость убывания нормы \\f - G™A(f,V)\\:
II/ - 0)11 > C^\f\MV)m-\ С7 > 0. (0.0.5)
Отметим, что во всех нижних оценках, приведенных в работе, функция / будет являться конечной линейной комбинацией элементов словаря, т.е. принадлежать пространству разреженных (sparse) векторов Ao(V):
%т(Р) =
^2 САРА, СА Є R, дх Є V, #Л < т
Аел
(0.0.6)
Л (о) := U £т(Р),
ш>0
l/lo = l/Uo(0) := Hiin{m > 0 : / 6 £т(0)}, / 6 Л(О).
Класс Aq(T>) с A\(V) является очень узким и из приведенных ниже оценок будет следовать, что за счет “разумного” сужения A\{V) существенно увеличить скорость сходимости ЧЖА и ОЖА нельзя.
Р. ДеВор и В.Н. Темляков [37] установили (0.0.5) для 7 = 1/2. Автору удалось проверить (0.0.5) для 7 = 1/2 — 5, 6 > 0, В.Н. Темляков уменьшил 7 до 1/3, в совместной работе автора и В.Н. Темлякова [93] 7 было уменьшено до 0.27.
В параграфе 1.4 получена новая оценка снизу па скорость сходимости ЧЖА, которая оказывается весьма близкой к верхней оценке A.B. Сильни-ченко.
Теорема 1.12. Существует, такой словарь V, элемент / € Aq(T)) и С > 0, что для произвольного т > 1 выполняется неравенство
||/ - G™AU,V)|| = Ц/504 > Cm-01838|/k(*».
В параграфе 1.5 получена оценка снизу на скорость сходимости ортогонального жадного алгоритма.
Теорема 1.13. Существует такой словарь V, элемент / € Ао (V) и С > 0, что для произвольного т > 1 выполняется неравенство
||/ - С£СА(/,©)|| > Ст-'/2.
10
Этот результат показывает неулучшаемость оценки сверху Р. ДеВора и В.Н. Темлякова |37) на скорость сходимости ОЖА.
Как отмечалось выше, в случае произвольного словаря V сужение класса А\(Т>) не ведет к увеличению скорости сходимости жадных алгоритмов, в тоже время как на более широких классах, скорость сходимости жадных алгоритмов может быть близка к оптимальной. Соответствующие результаты формулируются в параграфе 1.6 и доказываются в параграфе 1.7.
В качестве расширений Ai(V) будут рассматриваться интерполяционные пространства [Я. А\(Т>)]о,оо-
Пусть X и У действительные нормированные пространства. Напомним (см. [28]) определение интерполяционных пространств [X, У]о10С, 0 < 0 < 1. По определению / Е X принадлежит пространству |Х, У]<?)00 тогда и только тогда, если существует такое С > 0, что для всех t > 0 выполняется
K{f,t) < Ct\ (0.0.7)
где
К{}Л) = K(f,t,X.Y) := inf{||/ - h\\x+t\\h\\Y}.
ПЕУ
В качестве нормы \f\[x,Y]eoo, берется инфимум по числам С, для которых выполняется неравенство (0.0.7).
А. Бэррон, А. Коэн, В. Дамен, и Р. ДоВор |27] доказали оптимальность ОЖА в интерполяционных пространствах [Я, Ai(V)\eyoo, для всех 0, 0 < в < 1. В случае малых 0 чисто жадный алгоритм также является почти оптимальным:
Теорема 1.15. Для произвольных 6, 0 < 0 < 1/3 и е, 0 < е < в/2. Существует такое С > 0 что для всех / G [Я, Ai(T>)]oy00 и т > 1 справедлива оценка
||/ - G™A{f,V)\\ < C\S\[HMe.„m-o^.
В параграфе 1.8 доказываются оценки снизу на скорость убывания наилучшего m-членного приближения для интерполяционных классов.
Из теорем 1.12 и 1.13 вытекает, что если не накладывать на словарь V никаких дополнительных ограничений, то жадные алгоритмы не могут гарантировать скорость сходимости, лучшую чем СтГ1/2 даже для разреженных целевых функций (функций из Ао(Т>)). Тем не менее оказалось, что при наложении на словарь некоторых ограничений, связанных с когерентностью, скорость сходимости жадных алгоритмов может быть значительно выше.
В главе 2 исследуются скорость сходимости жадных алгоритмов по словарям с малой когерентностью. В начале параграфа 2.1 приводится определение когерентности, указывается пример переполненного словаря с малой когерентностью, построенный на основе Бсрнуллиевской матрицы, да-
11
ется краткая историческая справка и приводятся формулировки основных результатов.
Определение 2.1. Когерентностью словаря V будем называть величину
д:= sup \(ф,ф)\.
4>,\peV, ффф
Словари с когерентностью р будем называть ^-когерентными.
Сходимость ортогонального жадного алгоритма по словарям с малой когерентностью изучалась в работах Р. Грибонваля, М. Нильсена, Д. Донохо, М. Элада, В.И. Тсмлякова, А. Гильберт, М. Мутукришнана, Дж. Штраусса. Дж. Троппа и др. ([51], [43], [49], [85]). Интерес к этому направлению в значительной степени обусловлен тем, что получаемые здесь результаты оказались востребованы в задаче "сжатых измерений” (compressed sensing).
Следующая теорема является базовым результатом о сходимости ортогонального жадного алгоритма для разреженных целевых функций но словарю с малой когерентностью.
Теорема 2.1 ([51], [49], [85]) Пусть задан словарь Т> с когерентностью р и функция } £ Ао(Т>). Если
|/|„ < 1(М-’ + 1), (0.0.8) тпо для любого rn > j/|o имеет место равенство
f = GiOA(f:V).
Как было показано В.Н. Темляковым и П. Желтовым |84], константа 1/2 в неравенстве (0.0.8) не может быть увеличена.
Устойчивость точной аппроксимации разреженных целевых функций интенсивно изучалась. Следуя В.Н. Тсмлякову, будем называть неравенствами типа Лебега оценки, связывающие ошибку аппроксимации жадного алгоритма и наилучшее m-членное приближение
II/ - GSw(/, Х>)11 < В(т),тт(/,2>), т < С(ц). (0.0.9)
А. Гильберт, М. Мутукришнан и Дж. Штраусс [49] установили неравенство (0.0.9) для А(га) = 7/г, B(rri) = 8т1/Г2, С(р) = 2"3-5/!-1 — 1. Константы в А(т) и 13{т) были несколько улучшены Дж. Троппом [85] (см. также статью Д. Л. Донохо, М. Элада и В.Н. Тсмлякова [43].) Позднее Д. Л. Донохо, М. Элад и В.Н. Темляков [44] значительного улучшили В(т) и доказали неравенство (0.0.9) с Л(тп) = [тlogт\, В(т) = 24, С(р) = ^р~2^- В своей недавней работе [84] В.Н. Темляков и П. Жслтов приблизили значение С(р) к
12
оптимальному, доказав оденку (0.0.9) с А(т) = т\2^1°5ТП\, В(гп) = 3 и С(/х), которое должно обеспечить неравенство т2'/21°8т < для ш < С(/х).
В параграфе 2.1 получено точное по порядку неравенство типа Лебега (для ортогонального жадного алгоритма).
Теорема 2.7 Для произвольного р-когерентного словаря Т> и функции / є Н справедлива оценка
Ц/-С^(/,Р)||<3<7т(/)
для всех
1
1 < тп <
20/х
Этот результат доказывается в пунктах 2.1.1 - 2.1.4.
В параграфе 2.2 исследуются словари с ограниченной совокупной когерентностью. Следуя Дж. Троппу |85], введем определение.
Определение 2.2. Совокупной когерентностью счетного словаря V будем называть величину
II 1(23) := вир ^ | (5,9)1 •
9625 дфд
Будем говорить, что словарь V имеет ограниченную совокупную когерентность, если для него Ц\(Т>) < ОС.
Хорошо известно, что если для словаря V имеет место оценка р\(П) < 1/2, то для него выполняется так называемое Паррп^-свойство. Следующий результат в том или ином виде присутствует во всех работах по скорости сходимости жадных алгоритмов, в которых накладываются ограничения на когерентность словаря.
Теорема 2.8 (1;гарр1г^-свойство, [51], [43], [49], [85]) Пусть заданы словарь V с (£>) < 1/2, его конечное подмножество Х>0 и } € 5рап(Х>0), 7^0. Тогда
тах|</,0>|> зир |{/,<?)|.
9^0 деЪ\О0
Теорема 2.8 гарантирует, что если / € эрап^о), где V0 конечное подмножество V. то на каждом шаге жадного алгоритма очередной элемент словаря будет выбираться из Vо- Тем самым, в случае ортогонального жадного алгоритма за конечное число шагов (ЦТ>о) будет получено точное решение, а в случае чисто жадного алгоритма будет иметь место экспоненциальная скорость сходимости (как в конечномерных пространствах).
При малых значениях /хДХО чисто жадный алгоритм обладает оптимальной скорость и в пространстве
13
Теорема 2.9. Пусть заданы словарь V с ni{V) <1/3 ti / € Ai(V). Тогда
Теорема 2.9 была обобщена на более широкие классы.
Определим классы АР(Т>), 1 < р < оо. Положим .для М > О
А»(V, М) := <-ь9х ■ 53 Мр ^ iV/P> с* 6 R> 9х 6 2>, «А < оо},
А<=Л АеЛ
где замыкание берется в норме пространства Н. Пусть
Ap(V) := (J ЛР(Р,М),
Л/>0
1/1, := |/U(B) := inf{M > 0 : / £ -Лр(1>, М)}, / € Др(©).
Теорема 2.10. Пусть заданы словарь V с р\{Т>) < 1/3, р, 1 < р < 2 и / 6 Тогда найдутся Ci = Cl (р) > 0 г/ С2 = C,2(//i(X>)) > 0 такие,
что для любого гп > 1
||/ - GpmGA{f,V)|| = ||/т|| < CiCal/lpm-1^1/2.
В главе 3 исследуется вопрос о получении для целевой функции / разложений по элементам словаря V вида
ос
/ ~ 2>(Лл(Л, с*(/) 6 R’ е
Ь=1
частичные суммы которых
m
53 °k(f)9k(f) k-l
достаточно хорошо приближают / (при этом различность <?*(/) 11е требуется). Легко видеть, что чисто жадному алгоритму соответствует так называемое ЧЖА-разложение
00
С ST',г PGA РСЛ \ ,PGA
J ~ *9ы )9k »
k=l
в то время как ортогональному жадному алгоритму, в силу того, что на каждом шаге идет полный пересчет коэффициентов, никакое разложение не соответствует.
14
В главе 3 будут построены разложения, частичные суммы которых на классах A\(V) и [Н, Ai(T>)]ot00 обеспечивают скорость приближения близкую к оптимальной.
Первые разложения, превосходящие по скорости ЧЖА-разложения были предложены В.Н. Темляковым в работе [80] (см. также [75]). Им был рассмотрен слабый жадный алгоритм с параметром Ь и получены оценки на его скорость сходимости
Слабый жадный алгоритм с параметром Ь (СЖАв) Пусть заданы последовательность С [0,1], параметр Ь, 0 < 6 < 1, словарь
V и целевая функция fQVCAb /о := / € Я. Положим Go'GAb(f,T>) := 0. Последовательно для каоюдого т > 0 выбираем вектор g^GAb := gm+1 € V такой, чт.о
|{/m><?m+l)| ^ tm+1 SUp|(/m,(?)|
ge V
и определяем
GZ+x\f: Т>) ~ G%aM(J,T>) + b{fm,gm+i)gm+i, ff := /rn+1 := / - G"a“(/, V) = U- b(fm, gm+i)gm+v
В.Н. Темляков [80] доказал, что для произвольного элемента / G и 7?г > 1 справедлива оценка
т
ll/-G^6(/,©)|| < |/U.(7,)(1 + Ь(2 -b)J2 . (0.0.10)
Легко видеть, что если для достаточно малого е > 0 положить
b = f., tm =1 — б, т > 1,
то порядок скорости сходимости СЖАЬ окажется близким к -1/4, т.е. существенно лучшим по сравнению со скоростью сходимости ЧЖА.
Перейдем к определению возвратного жадного алгоритма, который, с одной стороны, как чисто жадный алгоритм дает разложение целевой функции в ряд по элементам словаря, а с другой, как ортогональный жадный алгоритмы, дает правильную в полиномиальной шкале скорость сходимости в классах A\{V) и [Н, Ai(V)\o)00, 0 < 0 < 1.
Возвратный жадный алгоритм (ВЖА) Пусть заданы вектор f G Н, словарь V и число 0 < t < 1. Полоэюгии Jq есСА := /о = f, GSecGA(f1Vtt) := Go(f, V, t) := 0. Предположим, что для п > 0 yoice определены /i,.... fn G Н, gi,..., gn G V u q,..., cn G K. Причем
k
fk = / - Y, ftft, Vfc, 1 < fc < n. (0.0.11)
1=1
15
Обозначим через
Дг := А,(/о, 2>, о := {»К-і! (0.0.12)
^п(д) '■= уп{д,/о-.Ъ-Л) ■= ^2 с*; (0.0.13)
к<п,дк=д
Ьп := Ьп(/оЛ Ь) := ^ М</)1;
рєАі атг = (/п> /п)-
£Ьш 7г > 1 и существует хотя бы один вектор д € Оп такой, что выполняются неравенства
тт(|г>п(<?)|, |(/п>р)|) >
и
ві^иДр)) = -вщп((/п,д)),
то полооюим
9м?л :=<?»+1 ~д, Сп+1 = ві^п(</П}д')) тіп(|гіп(д)|, |</п,.9>|).
Будем называть такие шаги возвратными. В противном случае, выберем произвольный дЦ+\*А = дп+і € V, удовлетворяющий неравенству
|(/».Ап+і)| > ^ир|(/П!р)| дЄЯ
и положим
С«+1 = {/пі9п+1)
Будем называть такие шаги жадными. Определим аппроксимант и остаток:
П4-1
£ЛеоС?Л(у := у ск9к = <7П(/,Х>) + Сп+1^п+1-
к=1
/5$*А := Ли-1 := /п - сп+і^п+і = / - <?п+1(/, 2>, О,
что гарантирует выполнение (0.0.11) па следующем шаге алгоритма.
Ряд
00
Х>^£СД
П=1
будем называть возвратным жадным разложением элемента / по словарю V.
16
В параграфе 3.2 доказывается следующая теорема о сходимости возвратных разложений.
Теорема 3.2 Для произвольного словаря V, целевой функции / € Н и і, 0 < і < 1, возвратный жадный алгоритм сходится:
lim \\f-G?cCAV,V,t)\\=0-
71—Ї ОО
В параграфе 3.3 установлены следующие две теоремы о скорость сходимости ВЖА.
Теорема 3.3. Для произвольного t, 0 < t < 1, существует такая константа К = K(t) > 0, что для произвольного словаря V, целевой функции / Є A\(V) и всех п > 1 имеет место неравенство
\\f-G«“GA(f,V,t)\\ < K\f\MV)n~^\un.
Теорема 3.4. Для произвольных числа і € (0,1] и в Є (0,1], существует такая константа К = К (1,9), что для любого словаря V, целевой функции / € [Н, Аі(Т))]еі00 и всех п > 1 имеет место неравенство
у_аНесвАи^т < КЦ\[Н'Мщ^П-в*\ъп.
Замечание 3.2. В отличие от оценки" (0.0.10) показатель степени в оценках скорости сходимости в теоремах 3.3 и 3.4 не зависит от пара-метра I.
Во многих приложениях, в частности задачах, относящихся к финансовой математике, требуется, чтобы коэффициенты с* в п-членном приближении
п
/ ~ у /Ш. 9к е В>, (0.0.14)
к— 1
были неотрицательными. В параграфе 3.4 обсуждается получение п-членных приближений с неотрицательными коэффициентами с помощью жадных алгоритмов.
Ясно, что при наложении дополнительного условия (неотрицательность коэффициентов) на тг-членное приближение, мы должны также наложить дополнительное условие на словарь V, чтобы построение соотвегствующего приближения было возможным. Множество V с Я будем называть положительным словарем, если
у е V => ||(7|| = 1, (^2 с\9\ I сА >0, дх в V, 8А < ос} = Н. (0.0.15)
АеЛ
17
А. Бэрроном [26] был предложен способ построения неотрицательных п-членных приближений с помощью релаксационного жадного алгоритма. Из результатов работы [27] вытекает, что релаксационный жадный алгоритм сходится для произвольного положительного словаря V и целевой функции /о, этот алгоритм также обладает хорошей скоростью сходимости, оптимальной для интерполяционных классов. С другой стороны, релаксационный жадный алгоритм дает только 7/-членныо приближения (0.0.14), но не даст разложения
оо
/ ~ ^2 Ск$к' дк е (0.0.16) к=1
кроме того, последовательность норм остатков не обязана монотонно убывать. 13 параграфе 3.4 мы рассматриваем “положительные аналоги” чистого жадного и слабо жадного алгоритмов, которые обеспечивают построение разложений (0.0.16). т.е. обладают свойством оперативности (on-line свойством), и частичные суммы которых (0.0.14) монотонно (в смысле нормы остатка) стремятся к целевой функции. (При этом с точки зрения скорости сходимости они могут уступать релаксационному жадному алгоритму).
При определении “положительных” версий ЧЖА и СЖА (ПЧЖА и ПСЖА) используются обозначения (0.0.12) и (0.0.13). Отметим, что ПЧЖА и ПСЖА не гарантируют неотрицательность всех коэффициентов с* в разложении (0.0.16), но любая частичная сумма ряда может быть рассмотрена как n-членное приближение с неотрицательными коэффициентами.
п
. У^Ск9к = ^2 - °> 9 е D»•
*=1 geDn
Положительный чисто жадный алгоритм (ПЧЖА) Пусть заданы целевая функция /0 := / € Я и полоэ/сителъный словарь V. Полооюим @о CA+{f'.'D) •= 0. Последовательно для као/сдого т. > 0 выбираешь вектор 9m+i е V и с,а+1 > -tJm(pm+i) т,ак, чт.обы
||/т ~ Cm-rl<?m+l|| = inf ||/m — Cg\\:
g<EV, r>-vm(g)
и. определяем
Glnn+(f,V) := G™+(/,®) + W3™Ti
/m+1 = / - V) = fm - cm+lgm+l.
Отмстим, что для фиксированных g G V и / G Я величина infc>-u ||/ — eg|| достигается при
с = тах( у, (/,у)).
18
Для д Є V определим
Кт(д) := вир ||/т||2 - ||/т - е<?||2 = вир (/т,/т>-
с>-от(д)
с>-ьт(д)
(/т - сд, /т - С£?> = вир 2с(/ю,д) - с2 =
с>-ьт(д)
{ </т,9)2, І «т(?)(-
2{/т)5) )> {/т>і?) <
Таким образом, легко видеть, что определение элемента <7ш+і и числа г^+1 по формуле (3.4.4) можно переписать
Слабый жадный алгоритм отличается от чисто жадного тем, что на очередном шаге алгоритма при выборе вектора максимизирующего скалярное произведение нам разрешается “ошибаться” при вычислении скалярного произведения в і“1-раз. Таким образом, мы приходим к определению.
Положительный слабо жадный алгоритм (ПОКА) Пусть фиксирована последовательность коэффициентов слабости т = {£т}т=і С [0,1]. Для целевой функции /о := / Є Н и положите.яъпого словаря V положим т) := 0. Тогда последовательно для каоюдого тп > 0
выбираем вектор дт+\ Є V такой, что
Отметим, что, согласно определению Кт(д), имеет место равенство
Определение ПОКА корректно. Как и в случае ОКА, для любого ^т4.1 € (0,1) мы всегда можем осуществить т-ый шаг алгоритма, т.е. найти дт+1 £ Р, удовлетворяющий (0.0.18). Это вытекает из следующей леммы.
9т+1 • Кт(.9т+1) — БЦр (_(/),
<?ЄР
Єт+1 Шах( Ут{с)1п+ 1) 5 {/т» 9т+1) )
Кт(дт+1) = ||/т||2 - ||/т+і|і2.
(0.0.17)
А»п(рпї+і) ^ эир
д^т) ^(/тп,^) 'Ут(д))і ^ш+і{/тпід) < Vт{д)
^т+іі/ті 9) — ^т(у)
(0.0.18)
и
А'т(УтЧ-і) = ІІ/т||2 - ||/т-4-і||2 > 0.
19