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

Теория приближения относится к тем областям математики, которые тесно связаны с прикладными задачами естествознания и техники. Увеличение мощности вычислительных систем, происходившее в последние десятилетия, позволило приступить к решению новых более вычислительноемких задач. Одной из них является построение «индивидуального приближения» для заданной функции / из некоторого класса К. Приближение предлагается строить как элемент линейного подпространства 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, spanP = X.

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

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

• от / зависят не только коэффициенты 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 — (Я, <�•,¦)) с нормой ||.|| := Ь->½.

Чисто жадный алгоритм (ЧЖА) Пусть задан словарь 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 — cgl 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. Показано, что чисто жадный алгоритм обладает оптимальной по порядку скоростью сходимости в интерполяционных пространствах [Я, л (?>)].

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°GA (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: |l = sup (fm, g)} Ф 0).

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

Теорема 1.2. Пусть задан дискретный словарь Т>. Тогда множество функций из Н, для которых на каждом шаге ОЖА супремум достигается: б Я | Vm {gm+1 е V: (fm, gm+i) = sup ||> ф 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™A (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-½, и показатель —½ не может быть уменьшен даже для ортонормированного словаря.

Приводятся оценки сверху на скорость сходимости ЧЖА — G&trade-Ä-(f, V) У < C7fMV) 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 = ½. Автору удалось проверить (0.0.5) для 7 = ½ — 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-«-™SfMvy.

В параграфе 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&trade-А№)\ < С|/1[Н, Аг (Т>)]в, оот~в²+е'.

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

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

В главе 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], константа ½ в неравенстве (0.0.8) не может быть увеличена.

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

А. Гильберт, М. Мутукришнан и Дж. Штраусе [49] установили неравенство (0.0.9) для А (т) = га, В (т) = 8га½, С (ц) = 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.8 (1гаррп^-свойство, [51], [43], [49], [85]) Пусть заданы словарь Т> с <½, его конечное подмножество и / € эрап^о) — ф 0. Тогда о 5&euro-Х>£> О.

Теорема 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 достаточно хорошо приближают / (при этом различность 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, то порядок скорости сходимости СЖАЬ окажется близким к —¼, т. е. существенно лучшим по сравнению со скоростью сходимости ЧЖА.

Перейдем к определению возвратного жадного алгоритма, который, с одной стороны, как чисто жадный алгоритм дает разложение целевой функции в ряд по элементам словаря, а с другой, как ортогональный жадный алгоритмы, дает правильную в полиномиальной шкале скорость сходимости в классах А{Т>) и [Я, Л{Т>)]в^, 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)\ < KfMv) n~V4nn.

II/ «G^GA (f, V, t)|| < Kf[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 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 KmCg), 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?iA+(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]- удовлетворяющая неравенству.

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) gl Отметим, что согласно теореме Хана-Банаха функционалы, удовлетворяющие (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) >tsupFfm (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.

Оказалось, что для сходимости жадных алгоритмов в равномерно выпуклых и равномерно гладких пространствах (где, в частности, 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), для которой существует такое O > 0, что supат{/, Пр) Мт + 2))^i+2+5 < оо. т> О.

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

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