Сходимость жадных алгоритмов тема автореферата и диссертации по математике, 01.01.01 ВАК РФ

4845141

Лившиц Евгений Давидович

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

01.01.01 — вещественный, комплексный и функциональный

анализ

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва — 2011

,1 2 МАЙ 2011

4845141

Работа выполнена на кафедре нелинейного анализа и оптимизации факультета физико-математических и естественных наук Российского университета дружбы народов.

Официальные оппоненты:

доктор физико-математических наук, профессор Конягин C.B. доктор физико-математических наук, профессор Лукашенко Т.П. доктор физико-математических наук, доцент Терехин П.А.

Ведущая организация:

Институт Математики и Механики Уральского отделения РАН.

Защита диссертации состоится 17 мая 2011 г. в 16 ч. 00 мин. на заседании диссертационного совета Д.212.203.27 в Российском университете дружбы народов по адресу: 115419, Москва, ул. Орджоникидзе, д. 3, ауд. 495а.

С диссертацией можно ознакомиться в Учебно-научном информационном библиотечном центре (Научной библиотеке Российского университета дружбы народов) по адресу 117198, Москва, ул. Миклухо-Маклая

Д. 6.

Автореферат разослан "

2011 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук доцент

Общая характеристика работы.

Актуальность темы. Теория приближения относится к тем областям математики, которые тесно связаны с прикладными задачами естествознания и техники. Увеличение мощности вычислительных систем, происходившее в последние десятилетия, позволило приступить к решению новых более вычислителыюемких задач. Одной из них является построение "индивидуального приближения" для заданной функции / из некоторого класса К. Приближеиие предлагается строить как элемент линейного подпространства L из заранее определенного (по К) семейства линейных подпространств С. При этом выбор L 6 £ зависит от /, что отличает эту задачу от классической задачи аппроксимации класса К, где приближающее подпространство L выбиралось единым для всех / е К. Другими словами, класс К приближается нелинейным объектом (Jig£ L • Такие приближения имеют также важное теоретическое значение. Как было показано P.C. Исмагиловым [2|, К.И. Осколковым [6] и В.Е. Майоровым [5] этот нелинейный (индивидуальный) подход может давать преимущества в некоторых классических задачах. Изучение оценок снизу для этого метода приближения было начато B.C. Кашиным [3].

Начиная с 80-х годов 20-го века, в рамках математической статистики и теории приближения стали интенсивно изучаться жадные алгоритмы, что, с одной стороны, дало теоретическое обоснование ряда методов вычислительной математики, а, с другой стороны, позволило получить конструктивные способы нахождения наилучших m-членных приближений. Ключевую роль в формировании теории жадных алгоритмов сыграли работы Дж. Фридмана, В. Стузла, С. Маллата, Ж. Жан-га, П. Хыобера, JI. Джоунса, А. Бэррона, Р. ДеВора, В.Н. Темлякова, C.B. Конягина, Д.Донохо и др. В наши дни жадные алгоритмы успешно применяются в задачах распознавания образов, медицины, финансовой математики, обработки сигналов и ряде других областей.

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

Пусть X = (X, II ■ II) — действительное банахово пространство. Множество Т>, V С X, будем называть словарем, если оно состоит из векто-

ров с единичной нормой, и замыкание линейной оболочки Т> совпадает со всем X:

д S V =» |Ы| = 1, späHD = X.

Для произвольного элемента / € X и m £ N требуется найти конечную линейную комбинацию m элементов словаря, достаточно хорошо приближающую /:

m

/ -»■ Е^/Ы/), ck(f) е К, gk(f) е V. (1)

к= 1

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

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

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

При этом желательно, чтобы величина ошибки аппроксимации ||/ — Ck(/M/)II была близка к значению наилучшего m-члешюго приближения (это понятие было введенного С.Б. Стечкиным в [9])

m

am(f):=am(f,V)-.= am(f,V,X)= inf II/~

ci,...,c,„eR, S).....gm6C *

k=1

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

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

Пусть X является сепарабельным гильбертовым пространством Я = (Я, {.,•)) с нормой ||.|| :=

чисто ЖАДНЫЙ АЛГОРИТМ (ЧЖА) Пусть задан словарь V С Н и целевая функция /0РСЛ := /о := / € Н. Положим G^aA(f,V) := О. Последовательно для каокдого т > О выбираем вектор gm+1 £ V такой, что

l(/m,5m+l)| = sup|(/m,fir)|, (2)

я sX>

и определяем

G™ÎUV) := GpmGAU,V) + (fm,9,n+i}gm+ь

/m+í1 := /»1+1 f — GfJlf(fyV) = /m - {fm,g,n+\)gm+l-

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

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

Отмстим, что ЧЖА строит разложение элемента / в ряд по словарю V, максимально уменьшая на каждом шаге алгоритма норму остатка:

||/m+i|| = inf Wfm-cg\\, rn>Q. csR, seP

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

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

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

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

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

Цель работы. Получить оценки на скорость сходимости чисто жадного и ортогонального жадного алгоритмов для различных классов целевых функций. Изучить сходимость жадных алгоритмов для словарей с малой когерентностью. Разработать новые виды жадных алгоритмов,

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

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

Научная новизна и основные результаты. Основные результаты диссертации являются иовыми и состоят в следующем:

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

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

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

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

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

конструктивном получении "положительных" m-членных приближений. (Теоремы 3.5, 3.6.)

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

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

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

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты и разработанные методы могут быть использованы в теории жадных алгоритмов, в теории приближения, вычислительной математике, теории передачи сигнала (в задаче сжатых измерений). Некоторые из разработанных в диссертации жадных алгоритмов могут оказаться полезными и в практических вычислительных задачах.

Публикации. Основные результаты диссертации опубликованы в работах [40]-[49] в изданиях, рекомендованных ВАК. В работах [33]-[38] опубликованы результаты автора о сходимости жадных алгоритмов, которые не были включены в диссертацию.

Апробация работы. Результаты диссертации докладывались в 1999-2010 годах на семинарах в МГУ: семинаре п/р П.Л. Ульянова и B.C. Кашина, семинаре п/р Б.И. Голубова, М.С. Дьяченко, B.C. Кашина и C.B. Конягина, семинаре п/р B.C. Кашина и C.B. Конягина, семинаре п/р И.Г. Царькова, семинаре п/р Т.П. Лукашенко, семинаре п/р В.М. Тихомирова; в МИАНе на семинаре п/р B.C. Кашина, на семинарах В РУДН: семинаре п/р A.B. Арутюнова, семинаре п/р А.Л. Скубачев-ского; на школах С.Б. Стечкина по теории приближения (Миасс 2000,

2001, 2004, 2010гг., Алексин, 2007г.); на пленарных заседаниях конференции "Современные проблемы теории функций и приложения (Саратов, 2009г.), конференции "Конструктивная теория функция-2010" (Созо-поль, Болгария, 2010г.); на секционных заседаниях международных конференций "Теория приближения функций и операторов", посвященной 80-летию C.B. Стечкииа (Екатеринбург, 2000г.), "Приближение и вероятность" (Бендлево, Польша, 2004г.), "Неортогональные разложения и жадные алгоритмы" (Вена, Австрия, 2005г.), "Кривые н поверхности" (Авиньон, Франция, 2006г.), "Симпозиум фон Неймана но разреженным представлениям и многомерной геометрии" (Сноуберд, США, 2007г.), "Современные проблемы математики, механики и их приложений", посвященной 70-летию академика В.А. Садовничего (Москва, 2009г.), "Современные проблемы анализа и преподавания математики", посвященной 105-летию академика С.М. Никольского (Москва, 2010г.), "Теория приближения", посвященной 90-летию С.Б. Стечкина (Москва, 2010г.), а также XXIV конференции молодых ученых механико-математического факультета МГУ им М.В. Ломоносова (Москва, 2002г.).

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы. Главы разбиты на параграфы. Некоторые параграфы разбиты на пункты. Нумерация утверждений (теоремы и леммы) двойная: номер главы и собственный номер. Нумерация формул тройная: номер главы, номер параграфа и собственный номер. Номера теорем во введении и автореферате совпадают с их номерами в основном тексте. Общий объем работы — 215 страниц. Список литературы содержит 106 наименований.

Основное содержание работы.

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

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

Ортогональный жадный алгоритм (ОЖА) Пусть задан словарь Т> и целевая функция ¡°СА := /о := / 6 H. Положим G2GAU,T>) := 0. Последовательно для каждого m > 0 выбираем век-

тор дт+1 G Т> такой, что

I </m, ffm+l) ! = SUp I </m, gr) I (3)

sex>

и определяем

^m+li/.23) := ProjSpan(9l,...,9,„+1)/.

fm+1 := /«i+l := Л _ GW?(/,!>).

Также в параграфе 1.1 приводятся результаты JI. Джонса [24) и В. Дубшшна [19| о сходимости ЧЖА и ОЖА: для любого гильбертова пространства Я, словаря Х> и целевой функции / G Я выполняются равенства

lim II/ - С£СЛ(/,Р)|| = 0, lim II/ - С°сд(/,2?)|| = 0.

Ш—ЮО Til—юо

Определение 1.1. Будем называть словарь V дискретным, если sup Кй.й)! < 1.

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

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

Теорема 1.1. Пусть задан дискретный словарь V. Тогда множество функций из H, для которых на каждом шаге ЧЖА супремум достигается:

(/ 6 Я | Vm {gm+1 € V : |(/m,Wi>l = 8up|(/m,g)|} ф 0}

I se» J

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

1под множествами второй категории в этой работе понимаются такие множества, дополнения которых являются множествами первой категории.

Теорема 1.2. Пусть задан дискретный словарь V. Тогда множество функций из Н, для которых на каждом шаге ОЖА супремум достигается:

J € Я I Vm {gm+1 е Т>: \(fm,gm+i)\ = sup|(/m,g>|} ф 01

JSP J

является множеством второй категории (использовалось обозначение

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

Теорема 1.5. Пусть заданы строго убывающие положительные функции r,R& C(R+), для которых

lim r{t) = lim R[t) = 0.

£->oo t-yoo

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

<rm{f,V)<R{m), m > 1,

\\f-G™Ä(f,V)\\>Cr(m), m>l, \\f-G?nGA(f,V)\\>Cr(m), m> 1.

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

6 V, #Л < оо и £|сл|<М} лел ЛеЛ

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

Ат := У

а/>0

Для / € Ai (V), введем норму

l/Ui(») = inf{M > О I / 6 Ai{V, M)}.

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

Из результатов С.Б. Стечкина [9] и А. Бэрропа [10] следует, что последовательность величин наилучшего m-членного приближения <тт(/,23) для / 6 А\{Т>) убывает не медленнее, чем Стп~1/2, и показатель —1/2 не может быть уменьшен даже для ортонормированного словаря.

Приводятся оценки сверху на скорость сходимости ЧЖА

II/23)11 <а,|/и1(7,)т-т. (4)

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

Для построения нижних оценок необходимо построить словарь 23, функцию / 6 »4i(2?), / ф 0 и для нее оценить снизу скорость убывания нормы ||/-С^(/,2Э)||:

II/ - 23)11 > Cy\f\MV)m-\ C1 > 0. (5)

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

А0(13):

£m(23) = ] X) САЗА, CA € К, 5А е 23, #Л < m i . (6)

Iasa J

A(2>) := (J Sm(23),

то>0

l/lo = If\Mv) ~ min{m > 0 : / e Em(23)}, / e Д0(23).

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

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

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

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

||/ - = \\f™\\ > Cm-°nf\Mvy

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

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

\\f-G°?AU,V)\\>Cm-V\

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

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

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

Пусть X и Y действительные нормированные пространства. Напомним (см. [13]) определение интерполяционных пространств [X, Y]g,0о , 0 < в < 1. По определению / 6 X принадлежит пространству [X, Y]o<00 тогда и только тогда, если существует такое С > 0, что для всех t > 0 выполняется

K(f,t)<Ct9, (7)

где

K(f, t) = K(f, t X, Y) := inf{||/ - Hx + t\\h\\Y).

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

А. Бэррон, А. Коэн, В. Дамсн, и Р. ДеВор [12] доказали оптимальность ОЖА в интерполяционных пространствах [Я, Ai(V)]etao > Для всех в, 0<в<1.В случае малых в чисто жадный алгоритм также является почти оптимальным:

Теорема 1.15. Для произвольных в, 0 < 0 < 1/3 и е, 0 < е < в/2 существует такое С > 0 что для всех / 6 [Н,Ai(V)]ei0o и т > I справедлива оценка

||/ - G™A(f,V)|| < C\f\[HAi{v)]^m-°^.

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

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

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

Определение 2.1. Когерентностью словаря V будем называть величину

sup \(ф,тр)\.

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

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

значительной степени обусловлен тем, что получаемые здесь результаты оказались востребованы в задаче "сжатых измерений" (compressed sensing).

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

Теорема 2.1 ([23], [22], [32]) Пусть задан словарь V с когерентностью ß и функция / 6 Ао(Т>). Если

1/1о<^_1 + 1), (8)

то для любого т > |/|0 имеет место равенство

f = G°mGA{f,V).

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

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

II/ - G°fä(f,V)\\ < B(m)crm(f,ТУ), т < C(ß). (9)

А. Гильберт, М. Мутукришнан и Дж. Штраусе [22] установили неравенство (9) для Л (га) = т, В(т) = 8т1/2, С{ц) = 2~3V-1 - 1- Константы в А(гп) и В(т) были несколько улучшены Дж. Троппом [32] (см. также статью Д. Л. Донохо, М. Элада и В.Н. Темлякова [17].) Позднее Д. Л. Донохо, М. Элад и В.Н. Темляков [18] значительного улучшили В(т) и доказали неравенство (9) с А(т) = [m log raj, В(т) = 24, С(ц) = ¿/и-2/3 • В своей недавней работе [31] В.Н. Темляков и П. Жел-тов приблизили значение C(ß) к оптимальному, доказав оценку (9) с Aim) — т[2^Ьет\, В(т) = 3 и C(/i), которое должно обеспечить неравенство т2^21°5т < ^ß'1 для т < C(ß).

В параграфе 2.1 получено точное по порядку неравенство типа Лебега (для ортогонального жадного алгоритма).

Теорема 2.7 Для произвольного ß -когерентного словаря V и функции / £ Я справедлива оценка

U-G™A(f,V)U<3*m(f)

для всех

Этот результат доказывается в пунктах 2.1.1 - 2.1.4.

В параграфе 2.2 исследуются словари с ограниченной совокупной когерентностью. Следуя Дж. Троппу [32], введем определение.

Определение 2.2. Совокупной когерентностью счетного словаря V будем называть величину

/xi(P):=sup J2 \(9>9) I-

Будем говорить, что словарь V имеет ограниченную совокупную когерентность, если для него /xj (V) < оо.

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

Теорема 2.8 (trapping-свойство, [23], [17], [22], [32]) Пусть заданы словарь V с /х\{Т>) < 1/2, его конечное подмножество Vо и / G span(£>0), / Ф 0. Тогда

тах|(/,з)|> sup \(f,g)\.

sevо geVXVu

Теорема 2.8 гарантирует, что если / € span(Z?0), где Vq конечное подмножество V, то на каждом шаге жадного алгоритма очередной элемент словаря будет выбираться из V0. Тем самым, в случае ортогонального жадного алгоритма за конечное число шагов ((¡£>0) буДет получено точное решение, а в случае чисто жадного алгоритма будет иметь место экспоненциальная скорость сходимости (как в конечномерных пространствах).

При малых значениях ц\{Т>) чисто жадный алгоритм обладает оптимальной скоростью и в пространстве A\(D)

Теорема 2.9. Пусть заданы словарь V с [ii(D) < 1/3 и / 6 Ai(V). Тогда

||f-G^ifWWSVUm-1'2, rn> 1.

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

АГ<Р, М) := {£>л<?а : |сл|р < Л/р, сл е К, дх £ V, #Л < оо},

АеЛ АеЛ

где замыкание берется в норме пространства Я. Пусть

ДР(£>) := у ЛР(£>,М), м> о

1/1р := 1/и(®) := > 0 : / е -4Р(Р, М)}, / € Лр(2>).

Теорема 2.10. Пусть заданы словарь V с /^(Х*) < 1/3, р, 1 < р < 2 и / е Лр(2?). Тогда найдутся С] = С^р) > 0 и С2 = С2(^(Г>)) > О такие, что для любого т > 1

ц/.-с^^Иад!/!^-1^1/2.

В главе 3 исследуется вопрос о получении для целевой функции / разложений по элементам словаря V вида

оо

/~1>(/Ы/), <*(/)€К, а*(/)е2э,

частичные суммы которых

т

£с*цыя

/ы

достаточно хорошо приближают / (при этом различность <%(/) не требуется). Легко видеть, что чисто жадному алгоритму соответствует так называемое ЧЖА-разложение

оо *=1

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

В главе 3 будут построены разложения, частичные суммы которых на классах Ai(T>) и [Н, Ai (О)]о,оо обеспечивают скорость приближения близкую к оптимальной.

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

Слабый жадный алгоритм с параметром Ь (СЖАв) Пусть

заданы последовательность {im}„=1 С [0,1], параметр Ь, 0 < b < 1, словарь V и целевая функция /дУаль := /о := /б Я. Положим GlQrGAb(f,V) := 0. Последовательно для каждого т > 0 выбираем вектор дт+1А1> '■— 9т+1 £ f такой, что

\{fm,9m+1)| > fm+isup|(/m,fi[)|

flSP

и определяем

Gl^AbU,V) := GZaM{f,V) + b(fm,gm+1)gm+1,

fm+\M := /'»+i := / — = /,„ — b(fm,gm+i)gm+1-

В.Н. Темляков [30] доказал, что для произвольного элемента / 6 Ai{V) и т > 1 справедлива оценка

т

\\f-G%CAUm<\f\Mv)(l + b(2-b)Y^tl)*3^- (10)

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

Ь=е, tm = 1-6, m > 1,

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

Перейдем к определению возвратного жадного алгоритма, который, с одной стороны, как чисто жадный алгоритм дает разложение целевой функции в ряд по элементам словаря, а с другой, как ортогональный жадный алгоритмы, дает правильную в полиномиальной шкале скорость сходимости в классах A\(V) и [H,Ai{V)]$i00, 0 < 9 < 1.

возвратный жадный алгоритм (вжа) Пусть заданы вектор f Е Н, словарь Т> и число 0 < t < 1. Положим f^ecGA := /о = /,

GoecGA(f,V,t) := Go(f,V,t) := 0. Предположим, что для п > 0 уже определены fi, ...,/„ 6 Я, ...,gn е V и С\,..., с„ 6 R. Причем

к

Л=/-1>Зь Vft, l<fc<n. (11)

¿=i

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

Dn- Dn(f0,V,t) {gk}U; (12)

vn(g)~vn(g,f0,V,t):= ]T c*; (13)

k<n.gi=g

bn:=b„(fo,V,t) ~

«еД.

(¿T! = (/„, fn)~

Если n > 1 и существует хотя бы один вектор g € Dn такой, что выполняются неравенства

min(|un(sí)|,|(/n,í?)|) >

и

sign(vn(g)) = -sign((/„,ff)),

то положим

9ntfÄ ■= 9п+1 := <7, <Wi = sign((/n,5í))min(|i;n(<7)|, [(/„, ff)|).

Будем называть такие шаги возвратными. В противном случае, выберем произвольный = gn+i 6 V, удовлетворяющий неравенству

l(/n,3»+i)| > t sup | </„, s> |

gev

и положим

Cn+l = (/niflVi+l)

Будем называть такие шаги жадными. Определим аппроксимант и остаток:

п+1

G«lfA(f,V,t) := Gn+1(f,V,t) :=J2ck9k = Gn(f,V) + сн+1<м+1.

k=l

/п+{С ■•= /п+1 •'= /п - Сп+10П+1 — / _ С„+1(/,Х>, £),

чшо гарантирует выполнение (11) на следующем шаге алгоритма.

Ряд

00

П=1

будем называть возвратным жадным разложением элемента / но словарю Т>.

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

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

Ит ||/0,4)||=0.

тг-юо

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

Теорема 3.3. Для произвольного £, 0 < £ < 1, существует такая константа К = К{£) > 0, что для произвольного словаря Т>, целевой функции / € А\(Т>) и всех п > 1 имеет место неравенство

II/- (?Г'СЛ(/,2),£)|| < К\}\Атп-^Ъп. (14)

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

II/ - V, ОII < КУ\[н,лЛП^-0/21п п.

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

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

п

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

Ясно, что при наложении дополнительного условия (неотрицательность коэффициентов) на п-членное приближение, мы должны также наложить дополнительное условие на словарь V, чтобы построение соответствующего приближения было возможным. Множество V С Н будем называть положительным словарем, если

д € V => ||fl|| = 1, {J2 схдх | сл > 0, дх е V, ЦЛ < 00} = Н. (16)

А. Бэрроном [11] был предложен способ построения неотрицательных п-членных приближений с помощью релаксационного жадного алгоритма. Из результатов работы [12] вытекает, что релаксационный жадный алгоритм сходится для произвольного положительного словаря Т> и целевой функции /о, этот алгоритм также обладает хорошей скоростью сходимости, оптимальной для интерполяционных классов. С другой стороны, релаксационный жадный алгоритм дает только п-членные приближения (15), но не дает разложения

кроме того, последовательность норм остатков не обязана монотонно убывать. В параграфе 3.4 мы рассматриваем "положительные аналоги" чисто жадного и слабого жадного алгоритмов, которые обеспечивают построение разложений (17), т.е. обладают свойством оперативности (online свойством), и частичные суммы которых (15) монотонно (в смысле нормы остатка) стремятся к целевой функции. (При этом с точки зрения скорости сходимости они могут уступать релаксационному жадному алгоритму).

При определении "положительных" версий ЧЖА и СЖА (ПЧЖА и ПСЖА) используются обозначения (12) и (13). Отметим, что ПЧЖА и ПСЖА не гарантируют неотрицательность всех коэффициентов c/t в разложении (17), но любая частичная сумма ряда может быть рассмотрена как n-членное приближение с неотрицательными коэффициента-

Аел

оз

(17)

ми.

п

J2Ck3k = vn(9)3', Vn(g) > 0, g е V,,.

к= 1 аеД,

Положительный чисто жадный алгоритм (ПЧЖА) Пусть заданы целевая функция /о := / е H и положительный словарь Т>. Положим G^G/1+(/, ТУ) := 0. Последовательно для каждого т. > 0 выбираем вектор gm+i £ 2? ы cm+i > —vm(gm+i) так, чтобы

Il/m - c„1+1g,„.+i|| = inf ||/т - cg\\,

äSV, c>-vm(g)

и определяем

G™+(/.2>) := G™A+(f:V) + c,n+1gm+1

и

fm+i = f — G^f+(f,V) = fm - c„[+ljg„l+i.

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

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

lim ||/ — G^aA+(f,V)\\ = 0.

m—>оо

Также в параграфе 3.4 получено достаточное условие на коэффициенты слабости для сходимости положительного слабого жадного алгоритма.

Глава 4 посвящена изучению сходимости и скорости сходимости жадных алгоритмов в банаховых пространствах. Это направление развивалось с конца 1990-х - начала 2000-х годов в работах В.Н. Темлякова, С. Дилворфа, Д. Куцаровой, C.B. Конягипа, П. Войташчека, Н. Калто-на, С.Л. Гогяна и др. для многих результатов о сходимости жадных алгоритмов в гильбертовом пространстве нашелся "банаховый" аналог.

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

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

Ff е X', IIF/H = 1, Fj(f) = ||/||. (18)

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

М/,Э)€ R: ||/-K/,9)9||=inf||/-HI, (19)

fl

r,(/,s):= Ц/Г - ||/q> 0, '-(/,ff):=n(/,5) = ll/H-||/-M/.^ll-

Отметим, что согласно теореме Хана-Банаха функционалы, удовлетворяющие (18), существуют и в качестве Ff можно выбрать любой их них. В случае, если пространство X является гладким (по Гато), то для любого / £ X выбор Ff становится однозначным. Аналогично, в качестве ц(/,у) берется любое число, удовлетворяющее (19), которое в строго выпуклых пространствах определяется однозначно.

X -жадный алгоритм (Х-ЖА). Пусть задай словарь V и целевая функция /о := / £ Н. Положим GQCA{f,T>) := 0. Последовательна для каждого тп > 0 выбираем вектор дт+\ 6 Т> такой, что

r{fm,gm+l) = sup r(fm,g) gen

и определяем

Gwi(/,!>) := GiGA(f,V) + ß(fm, gm+1)gm+ i,

fm+l ■= f — G*GA(f,V) = fm — ß{fm,gm+l)gm+l-

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

Теорема 4.1. Существует гладкое (по Гато) банахово пространство X, словарь Т> с X и / £ X, для которых

lim ||/т||= lim ||/ - G*CA(f)\\ ф 0.

m-> оо m-> оо

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

Двойственный жадный алгоритм с параметром £ (£>-ЖА). Пусть задан словарь V, целевая функция /о := / 6 X и фиксированное число £, 0 < £ < 1. Положим ОЦаЛ{$,Т>)£) := 0. Последовательно для каждого т > 0 выбираем вектор дт+1 6 Т> такой, что

\Р/т(9т+1)\ >tsup\FfM

и определяем

:= С£см(/,2>,£) + ц(/т, дт+1)9т+и

/ш+1 := / - = /т - /'■(/ш,5т+1)?т+1-

л-жадный алгоритм с параметрами £ и <2 (я-жа). Пусть задан словарь Т>, целевая функция /о := / € А" и фиксированные числа £, 0 < £ < 1 и 9, д > 0. Положим Со?с;/1(/, 2?, £, д) := 0. Для каждого тп > 0 последовательно выбираем вектор дт+1 £ Р такой, что

^(/т.дт+О > ^ гч(/т,д) \К1т,д,п+1)|_ яео|М/п»з)|

и определяем

23, ¿, 9) := V, £, 9) + ц{/т,дт+1)9т+1,

/т+1 := / - = /т - /х(/,ц,5т+1)5т+1-

Отмстим, что, если X является гильбертовым пространством, то X-жа, -о-жа с £ = 1 н д-жа с£ = 1,д = 2в точности совпадают с чжа.

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

Лемма 4.1. Пусть заданы банахово пространство X и словарь И с X. Если существует > 0, что для всех 0 < £ < 1, всех / € X и произвольной реализации Я -жадного алгоритма выполняется

Нт ||/-С£сл(/,0,£,9о)||=0,

то для всех q>0,0<t<l, f € X и произвольной реализации R -жадного алгоритма имеет место равенство

lim ||/-G™A(f, V, t, 9)|| = 0.

m-*oo

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

Эе>1: Vf,geX ||g|| = 1, Оr(f,g) > \ß(f,g)Ff(g)|. (20)

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

Теорема 4.2. Пусть X равномерно выпуклое, равномерно гладкое банахово пространство, для которого выполняется условие (20), и V словарь в нем. Тогда для всех 0 < t < 1, q > 0, для любой / € X и произвольной реализации R, -жадного алгоритма выполняется

Ит ||/ -G™A(f,V,t, 9)||=0.

m—юо

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

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

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

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

m-ioo

В своей недавней работе [15] С. Диворф, Д. Куцарова, К. Шуман, В.Н. Темляков, П. Войташчек установили слабую сходимость X-жадного алгоритма для банаховых пространств, обладающих WN-свойством. С. Диворф, Е. Оделл, Т. Шлумпрехт, А. Зак [16] получили интересные результаты о сходимости X -жадного алгоритма в пространствах Lp(0,1) для разреженных целевых функций. В тоже время

никаких общих "положительных" результатов о сходимости X-жадного алгоритма, в бесконечномерном банаховом пространстве, не являющимся гильбертовым, на сколько известно автору, получено не было. Более того, остается открытым вопрос о сходимости X -жадного алгоритма (для всех целевых функций) в пространстве Lv(0,1), р ф 2, по системе Хаара.

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

Напомним определение системы Хаара Ир — {Яп}^=1 в пространстве Lv(0,1), р > 1. Положим Hi(t) = 1. Пусть m = 2* + г, к> 0, 1 < i < 2к. Рассмотрим двоичные промежутки

Известно, что spanНр = ¿,,(0,1), поэтому, в силу равенств ||Ят|| = 1, т > 1, система Хаара Tip является словарем.

Для произвольного измеримого Д С [0,1) обозначим через |Д| его меру Лебега. Определим

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

Д+ := (Д1)+ := [

Д- := (ДУ" :=

Определим

Приближение системой Тр было рассмотрено Т.П. Лукашенко в статье

[41-

Легко видеть, что для любого тп > 1

ът{нр) с т,2ш{1р) (21)

(см. определение (6)), но в противоположную сторону аналогичные включения не верны

Ът{1р) £ ЕЛ/СИр), УМ > гп.

Для положительной функции ф € С(П£+) рассмотрим класс

Аф{Ъ, X) = АФ{Ъ) = {/ 6 X : от(/,Т>, X) < ф{т)., т > 0}.

Теорема 4.4. Для любого р, 1 < р < оо, существует такое ад = ао(р) > 0, что для произвольной положительной убывающей функции ф 6 С1(К+), удовлетворяющей неравенству

Иш = 1шпп^ (1п (фа)))' > -а0, (22)

*->оо 0(£) <->оо

для любой / е ДДХр) м для произвольного тп > 1 будет справедлива оценка

М-С™А(/,1?)\\ = Ш\<Сф(т) где константа С > 0 зависит от р и ф(-), но не зависит от / и т.

Отметим, что для произвольных 0 < а < «о, /? > 0, а + /3 > 0, и С > 0 для функции ф е С1(К+) вида

0(г) = С(< + 1)-а(1п(г + 2))-^

выполняется неравенство (22).

Из теоремы 4.4 выводится сходимость .Х-ЖА по системе Хр для всех / 6 ¿г,(0,1).

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

Ит ||/-С^л(/,2р)||=0.

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

Теорема 4.6. Для любого р, 1 < р < 2, существует такое а0 = ®о(р) > 0, что для произвольной положительной убывающей функции ф € Ci(R+), удовлетворяющей неравенству

liminf Ц¥г = liminf i(ln(0(i)))' > -а0, i-> 00 Ф{1) t->oo

для любой / 6 Аф{Тр, Lp{0,1)) и для произвольного m > 1 будет справедлива оценка

II/ - GiCA{f,Uv)\\ = Ш\ < С1ф(т)(ln(m + 1)) А+2,

где константа ci > 0 зависит от р и ф(-), но не зависит от f и т.

Из справедливости включения (21) вытекает

Теорема 4.7. Для любого р, 1 < р < 2, существует такое ао = Q0(p) > 0, что для произвольной положительной убывающей функции ф 6 Ci(R+) , удовлетворяющей неравенству

liminf ^^ = liminf i (ln(0(i))' > -а0,

(->00 <рт t—>oo

для любой f 6 Аф{ир, Lp(0,1)) u для произвольного т > 1 будет справедлива оценка

II/ - GmG/1(/,"Hp)|| = ||/т|| < с^(т)(1п(т + 1))г^+2,

где константа q > 0 зависит от р и ф(-), по не зависит от / и т.

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

Теорема 4.8. Пусть задано р, 1 < р < 2, и функция / £ £р(0,1), для которой существует такое 6 > О, что

sup <rm(/: Wp)(ln(m + 2)) A+2+i < oo.

m> 0

Тогда

hm ||/-G£™(/,Wp)||=0. 27

Замечание 4.1. При р = 2 система Хаара 'Нг является ортонор-мированиъм базисом в пространстве 0,1), и хорошо известно, что для любой / € ¿г(0,1)

||/ - || = ||/ - С™А(/,Н2)|| = ат(/,Н2),

то есть теоремы ^Л и 4-8 в случае р = 2 не являются оптимальными.

Замечание 4.2. Если в банаховом пространстве X задан базис Шаудера В = {Фк}™-1> т0 гп-членные приближения к / € X по системе В, моэюно получать с помощью метода, основанного на разложении / в ряд по базису В

00 к=1

и существенно отличного от изложенного выше X -жадного алгоритма. Этот метод основан на переупорядочении коэффициентов разложения в порядке убывания модуля

К(/)|>Ы/)|>--.

В качестве т -членного приближения Б) берется

т 3=1

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

II/ - С*т(/,НР)\\ < С{р)ат{},Щ)-

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

Теорема 4.9. Для любого р, 1 < р < 2, существуют такие числа с3,с4 > 0, что для любого п 6 N и Н е ||Л|| = 1 найдется

конечное множество индексов Лц С М, для которого выполняются следующие неравенства

с3

г(Н, Н\) > —, для любого А 6 Лц, п

АеЛ0

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

Теорема 4.10. Для любого р, 1 < р < 2, существуют такие <?5,сб > 0, что для любого и 6 I, Л 6 Ип(Хр), ||Л|| = 1 « функции / 6 ¿,,(0,1) такой, что

\\f-h\l <с5(1П(П+1))-А-2,

найдется Ло 6 К, для которого

к/,//*>>!■

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

В параграфе 4.11 приводится доказательство теорем 4.4 и 4.5.

Литература

[1] Галатенко В. В. "Об орторекурсивном разложении по некоторой системе функций с ошибками при вычислении коэффициентов". // Матем. сб. 2004. Т. 195:7. С. 21-36.

[2] Исмагилов P.C. "Поперечники множеств в линейных нормированных пространствах и приближение функций тригонометрическими многочленами" // УМН 1974. Т. 29. № 3. С. 161-178.

[3] Кашин B.C. "Об аппроксимационных свойствах полных ортонормн-рованных систем." // Тр. МИАН СССР. 1985. Т. 172. С. 187-191.

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

[5] Майоров В.Е. " Тригонометрические поперечники соболевских классов Wp в пространстве Lq." // Матем. заметки 1986. Т. 40. № 2. С. 161-173.

[6] Осколков К.И. " Аппроксимативные свойства суммируемых функций на множествах полной меры." // Матем. сб. 1977. Т. 103(145):4(8). С. 563-589.

[7] Сильниченко А. "О скорости сходимости жадных алгоритмов" // Математические заметки 2004. Т. 76. № 4. С. 628-631.

[8] Стечкин B.C., Стечкин C.B. "Среднее квадратическое и среднее арифметическое" // Докл. АН СССР 1961. Т. 137. № 2. С. 287-290.

[9] Стечкин С.Б. "Об абсолютной сходимости ортогональных рядов" // Докл. АН СССР 1955. Т. 102. № 1. С. 37-40.

[10] Barron A. "Universal approximation bounds for superposition of n siginoidal functions" // IEEE Transactions on Information Theory. 1993. V. 39. P. 930-945.

[11] Barron A. "Approximation and estimation bounds for artificial neural networks" // in Proc. Fourth Annula Workshop on Computational Learning Theory. M. Kaufmaim. 1991. P. 243-249.

[12] Barron A., Cohen A., Dahinen W., DeVore R. "Approximation and learning by greedy algorithms" // Annals of Statistics 2008. V. 36. P. 64-94.

[13] Bergh .J., Lofstrem J. "Interpolation spaces" // Springer Verlag. Berlin. 1976.

[14] DeVore R. A., Temlyakov V. N. "Some remarks on Greedy Algorithms" // Advances in Computational Mathematics. 1996. V. 5. P. 173-187.

[15] Dilworth S., Kutzarova D., Shuman K., Temlyakov V.N., Wojtaszchyk P. "Weak Convergence of Greedy Algorithms in Banach spaces" // Journal of Fourier Analysis and Applications. 2008. V. 14. P. 608-629.

[16] Dilworth S., Odell E.,Schlumprecht Th., Zsak A. "On the Convergence of Greedy Algorithms for Initial Segments of the Haar Basis" //Math. Proc. Cambridge Philos. Soc. accepted 2009.

[17] Donoho D. L., Elad M., Temlyakov V.N. "Stable reeovey of sparse ovcrcomplete representations in the presense of noise" // IEEE Trans. Inform. Th. 2006. V. 52:1. P. 6-18.

[18] Donoho D.L., Elad M., Temlyakov V.N. " On Lebesgue-type inequalities for greedy approximation " // Journal of Approximation Theory 2007. V. 147:2. P. 185-195.

[19] V.V. Dubinin "Greedy Algorithms and Applications". // Ph.D. thesis, University of South Carolina. 1997.

[20] Friedman J. H, Stuetzle W. "Projection pursuit regression" //J. Amer. Statist. Assoc. 1981. V. 76. P. 817-823.

Ganichev M., Kalton N.J. "Convergence of the weak dual greedy algorithm in Lp -spaces" // Journal of Approximation Theory 2003. V. 124. P. 89-95.

Gilbert A.C., Muthukrishnan M., Strauss J. "Approximation of functions over redundant dictionaries using coherence" // Proc. 14th Annu. ACM-SI AM Symp. Discrete Algorithms. 2003. P. 243-252.

Gribonval R., Nielsen M. "On the strong uniqueness of highly sparse expansions from redundant dictionaries." // Proc. Int Conf. Independent Component Anal. (ICA'04) 2004.

.Jones L., "On a conjecture of Huber concerning the convergence of projection pursuit regression" // Ann. Statist. 1987. V. 15. P. 880-882.

Konyagin S. V., Temlyakov V. N. "Rate of convergence of Pure Greedy Algorithm" // East J. Approx. 1999. V. 5. P. 493-499.

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

Schmidt E. "Zur Theorie der linearen und nichtlineareii Integralgleichungen. I."// Math. Ann. (1906-1907). 63. P. 433-476.

Temlyakov V.N. "The best m-term approximation and greedy algorithms" // Advances in Comp. Math. 1998. V. 8. P. 249-265.

Temlyakov V. N. "Greedy approximation" // Acta Numerica. 2008. V. 17. P. 235-409.

Temlyakov V.N. "Greedy expansions in Banach Spaces" // IMI-preprint. 2003. No. 6. P. 1-21.

Temlyakov V.N., Zheltov P. "On performance of greedy algorithms" http://dsp.rice.edu/cs //submitted to Journal of Approximation Theory. 2010

Tropp J. A. "Greed is good: algorithmic results for sparse approximation" //IEEE Trans. Inform. Th. 2004. V. 50:10. P. 22312242.

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

[34] Лившиц Е. Д. " О сходимости Х-гридн-алгорнтма по системе сплайнов" // Труды XXIV конференции молодых ученых мех-мат факультета МГУ им М.В. Ломоносова . 2002. С. 113-116.

[35] Galatenko V.V., Livshitz E.D. "On the convergence of approximative weak greedy algorithms" // East J. Approx. 2003. V. 9. No. 1. P. 4349.

[36] Livshitz E. D., Temlyakov V. N., "Two lower estimates in greedy approximation" //' Constructive Approximation. 2003. V. 19. P. 509524.

[37] Галатенко В. В., Лившиц Е. Д. "Обобщенные приближенные слабые жадные алгоритмы" // Математические заметки. 2005. Т. 78. № 2. С. 186-201.

[38] Галатенко В. В., Лившиц Е. Д., Шмырев Н. В. "Сходимость обобщенных приближенных слабых жадных разложений но ортоиорми-рованным системам." // Технологии программирования, учетные системы, ортономированные системы. 2008. НИИ системных исследований РАН. С. 149-163.

[39] Livshits E.D. "On the optimality of Orthogonal Greedy Algorithm for M-cohercnt dictionaries " //2010. http://arxiv.org/abs/1003.5349

Основные публикации по теме диссертации (из перечня ВАК).

[40] Лившиц Е.Д. "О сходимости гриди-алгоритмов в банаховых пространствах" // Матем. залгетки 2003. Т. 73. № 3. С. 371-389.

[41] Лившиц Е.Д. "О скорости сходимости чисто жадного алгоритма" // Матем. заметки 2004. Т. 76. № 4. С. 539-552.

[42] Лившиц Е.Д. "О возвратном жадном алгоритме" // Изв. РАН. Серия матем. 2006. Т. 70. № 1. С. 95-116.

[43] Лившиц Е.Д. "Об оптимальности жадного алгоритма для некоторых классов функций" // Матем. сборник 2007. Т. 198. № 5. С. 95114.

[44] Лившиц Е.Д. "Об п-членном приближении с неотрицательными коэффициентами." // Матем. заметки 2007. Т. 82. № 3. С. 373382.

[45] Лившиц Е.Д. "О жадного алгоритме в пространстве Ьр[0,1]." // Матем. заметки 2009. Т. 85. № 5. С. 788-791.

[46] Лившиц Е.Д. "О нижних оценках скорости сходимости жадных алгоритмов" // Изв. РАН. Серия матем. 2009. Т. 73. № 6. С. 125144.

[47] Лившиц Е.Д. "О сходимости жадного алгоритма по системе Хаара в пространствах Ьр(0,1)" // Матем. сборник 2010. Т. 201. № 2. С. 99-130.

[48] Лившиц Е.Д. "О жадном алгоритме для словарей с ограниченной совокупной когерентностью" // Матем. заметки 2010. Т. 87. № 5. С. 792-795.

[49] Лившиц Е.Д. "Реализуемость жадных алгоритмов" // Труды ИММ УрО РАН. 2010. Т. 16:4. С. 228-236.

Подписано в печать 09.03.11

Объем: 1,5 усл.печ.л. Тираж: 100 экз. Заказ № 765 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, 39 (495) 363-78-90; www.reglet.ru

Введение

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.