ИСТИНА

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

We aim to conduct a theoretical study of the fundamental methods used in sparse data representation and to develop a theory of sparse representation that widely applies to problems of big data. The project includes research in the following areas of modern mathematics: greedy approximation and optimization, multivariate approximation, discretization and learning theory in their natural relationship with the goal of building practical big data processing algorithms. Greedy approximation. We plan to develop and analyze new greedy-type algorithms. Convergence, rate of convergence, and stability of these algorithms will be studied in general Banach spaces. We plan to find classes of dictionaries for which the known general convergence characteristics of greedy algorithms can be improved or extended to wider classes of spaces. Also it is planned to obtain an effcient algorithm for constructing a deep neural network approximating a given function. Multivariate approximation. We plan to: obtain new estimates for the widths of functional classes; study application of the theory of widths to estimates of the stiffness of matrices in theoretical computer science; study ridge approximation and the corresponding properties of ridge functions; study approximation of functions by multidimensional Haar systems and multidimensional B-splines and study related problems on the structure of self-similar sets; study approximation of tensors from different classes by tensors of small rank. During the study of all these problems the techniques and ideas of greedy algorithms will be used systematically. Discretization. We plan to: establish connections between numerical integration, discrepancy, dispersion and universal discretization; obtain new results on the discretization of integral norms of functions from a given finite-dimensional subspace and to study related problems concerning the behavior of the entropy numbers of classes of functions with bounded integral norms. Using the technique of greedy approximation, we plan to show the possibility of effcient numerical integration in classes of functions without any assumptions on their smoothness. Also, we plan to obtain new estimates for the discrepancy with a fixed volume. Learning theory. Learning algorithms include a wide variety of algorithms beginning with classical least squares algorithms, greedy-type algorithms and ending with recent algorithms based on neural networks, which are used in deep learning. We stress the importance of theoretical study by noticing that some of the theoretical results obtained by participants of the project are implemented in practice by leading western companies. Primarily, we mean the use of "Kashin's representation" in "federated learning". The popularity of learning algorithms stems from their empirical success on several challenging learning problems (computer chess/go, autonomous navigation, face recognition). However, most scholars agree that a convincing theoretical explanation for this success is still lacking. We hope that the use of greedy-type algorithms which we used earlier will allow us to build provably good algorithms for neural networks approximation.

Исследование разреженных приближений. Работы по теории разреженного представления относительно произвольного словаря будут вестись по двум направлениям: разреженная аппроксимация и разреженная оптимизация. Помимо исследования общих свойств решений этих задач (m-членные приближения по заданному словарю, классификация словарей по их аппроксимативным свойствам и т.п.), будут разработаны и исследованы различные алгоритмы жадного типа для разреженной аппроксимации и оптимизации относительно произвольного словаря. Будут доказаны теоремы о сходимости, скорости сходимости и устойчивости (к шуму и неточности вычислений) соответствующих алгоритмов. Разработка и анализ жадных алгоритмов. Будут построены новые жадные алгоритмы, а также проведен детальный анализ их скорости сходимости и устойчивости. Предполагается изучить случай общих банаховых пространств и весьма общих словарей в них. Жадные алгоритмы планируется применить в задаче выпуклой минимизации. Практическая эффективность развитых методов жадных приближений будет проверена численными экспериментами. Задачи многомерной аппроксимации и смежные вопросы выпуклой геометрии. Многомерная аппроксимация и методы вычислений. Классы гладкости. Предполагается получить новые оценки асимптотических характеристик как классов функций смешанной гладкости, так и некоторых других классов. Кроме того, планируется найти новые соотношения между различными асимптотическими характеристиками, например, между поперечниками по Колмогорову и оптимальными ошибками восстановления по выборке. Эти результаты помимо теоретического интереса важны в численных методах, например, для численного анализа уравнения Шредингера. Будет проведен теоретический анализ задач многомерной аппроксимации, которые важны в численных расчетах. Общие алгоритмы жадного типа будут применены к задаче конструктивной разреженной аппроксимации функций тензорными произведениями. В частности, планируется разработать практические алгоритмы разреженной аппроксимации относительно словарей со структурой тензорного произведения. Алгоритмы жадного типа будут применены для конструктивной разреженной аппроксимации относительно словаря из ридж-функций. Эта задача тесно связана с нейронными сетями и имеет важные приложения в статистике и теории обучения. Будут развиваться методы многомерной выпуклой геометрии, необходимые для доказательства новых результатов в теории поперечников, в ряде задач о свойствах ограничений линейных операторов на координатные подпространства, в теории сжатых измерений. Задача дискретизации. Универсальная дискретизация. Восстановление по выборке. Предполагается получение ряда результатов по задаче дискретизации. Для восстановления неизвестной функции многих переменных по выборке ее значений в конечном числе точек будут построены восстанавливающие операторы (алгоритмы), которые хороши в смысле точности, устойчивости и программной реализации. Будут найдены связи между поперечниками Колмогорова и ошибками оптимального восстановления для заданного класса функций. Соответствующий анализ будет основан на глубоких результатах дискретизации интегральных норм функций из конечномерных подпространств. Будет исследоваться универсальная дискретизация для набора подпространств данной размерности, определяемых заданным словарем.