Научная тема: «СХОДИМОСТЬ ЖАДНЫХ АЛГОРИТМОВ»
Специальность: 01.01.01
Год: 2011
Отрасль науки: Физико-математические науки
Основные научные положения, сформулированные автором на основании проведенных исследований:
  1. Показано, что чисто жадный алгоритм не является оптимальным по порядку в пространстве Л(Т>). Получены оценки снизу на скорость сходимости чисто жадного алгоритма в пространствах Aq(T>) и Ai(T>) достаточно близкие к наилучшим известным оценкам сверху (А.В. Cильниченко). Тем самым получен ответ на вопрос Девора - Темлякова об оптимальности ЧЖА и с точностью до 0.01 определена константа Конягина - Темлякова. (Теорема 1.12.)
  2. Показано, что чисто жадный алгоритм обладает оптимальной по порядку скоростью сходимости в интерполяционных пространствах [H,Ai(V)]etO0 при 0 < в < 1/3. (Теорема 1.15.)
  3. Получено точное по порядку неравенство типа Лебега для ортогонального жадного алгоритма по словарям с малой когерентностью. Ранее эта задача исследовалась в работах Д. Донохо, М. Элада, В.Н. Темлякова, А. Гильберт, М. Мутукришнана, Дж. Штраусса, Дж. Троппа, П. Желтова. (Теорема 2.7.)
  4. Предложен возвратный жадный алгоритм, который позволяет получать жадные разложения, обладающие оптимальной по порядку скоростью в интерполяционных пространствах [Н, А(Т>)]в оо при 0 < в < 1, и, в частности, в Ai(V). (Теоремы 3.3, 3.4.)
  5. Предложены положительный чисто жадный и положительный слабый жадный алгоритмы. Доказано, что если функция приближается элементами словаря с положительными коэффициентами, то жадные разложения, построенные с помощью этих алгоритмов, после приведения подобных будут иметь неотрицательные коэффициенты. Тем самым, получен ответ на вопрос Б.С. Кашина о конструктивном получении "положительных" m-членных приближений. (Теоремы 3.5, 3.6.)
  6. Построен пример гладкого банахова пространства, словаря в нем и целевой функции, для которых X -жадный алгоритм расходится. (Теорема 4.1.)
  7. Найдено новое геометрическое свойство банаховых пространств, являющееся достаточным для сходимости некоторых видов жадных алгоритмов в банаховых пространствах. Доказана сходимость R-жадного алгоритма в пространствах lp , p > 2. (Теоремы 4.2, 4.3.)
  8. Исследована сходимость X -жадного алгоритма в пространстве Lp(0,1) для конкретных систем: системы Хаара, и системы функций, пропорциональных индикаторам двоичных интервалов. Получены неравенства типа Лебега, а также доказана сходимость X -жадного алгоритма по "системе индикаторов" на всем пространстве Lp(0, 1), 1 < p < ∞. (Теоремы 4.4, 4.5, 4.6, 4.7.)
Список опубликованных работ
1.Лившиц Е.Д. “О сходимости гриди-алгоритмов в банаховых пространствах” // Матем. заметки 2003. Т. 73. № 3. С. 371–389.

2.Лившиц Е.Д. “О скорости сходимости чисто жадного алгоритма” // Матем. заметки 2004. Т. 76. № 4. С. 539–552.

3.Лившиц Е.Д. “О возвратном жадном алгоритме” // Изв. РАН. Серия матем. 2006. Т. 70. № 1. С. 95–116.

4.Лившиц Е.Д. “Об оптимальности жадного алгоритма для некоторых классов функций” // Матем. сборник 2007. Т. 198. № 5. С. 95– 114.

5.Лившиц Е.Д. “Об n-членном приближении с неотрицательными коэффициентами.” // Матем. заметки 2007. Т. 82. № 3. С. 373– 382.

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

7.Лившиц Е.Д. “О нижних оценках скорости сходимости жадных алгоритмов” // Изв. РАН. Серия матем. 2009. Т. 73. № 6. С. 125– 144.

8.Лившиц Е.Д. “О сходимости жадного алгоритма по системе Хаара в пространствах Lp(0,1)” // Матем. сборник 2010. Т. 201. № 2. С. 99–130.

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

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