The information is prepared on the basis of data from the information-analytical system RSF, informative part is represented in the author's edition. All rights belong to the authors, the use or reprinting of materials is permitted only with the prior consent of the authors.

AffiliationFederal State Budgetary Educational Institution of Higher Education Lomonosov Moscow State University,

Research area 01 - MATHEMATICS, INFORMATICS, AND SYSTEM SCIENCES, 01-109 - Substantial and functional analysis

Keywordsgreedy approximation, nonlinear approximation, multivariate approximation, sparse approximation, compressed sensing, greedy algorithms, discretization, optimal recovery, big data, data sciences, learning theory, deep learning, Kolmogorov width, random Dirichlet series, uniform convergence, random Dirichlet series, uniform convergence

Annotation
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 finnd 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. The laboratory "High-dimensional approximation and applications" of the Lomonosov Moscow State University, headed by Prof. V.N. Temlyakov, has a unique set of world-class specialists and can provide breakthrough research in the above mentioned areas with the aim of building a general theory of sparse representation of big data and developing new high performance algorithms for its compression and analysis. The results of the project can be used to create information systems for collecting, processing, and storing big data, including geoinformational, genomic, industrial, and financial data. Also, they can be used for construction and training of neural networks designed for analysis and processing of digital video and audio signals, for image recognition, as well as for collecting and ordering other big data arising in applied problems of modeling physical and socio-economic processes.

Expected results
The project will consider the following set of scientific problems (tasks) that have important theoretical and applied value. Research of the sparse approximations. Work on the theory of sparse representation with respect to an arbitrary dictionary will be conducted in two directions: sparse approximation and sparse optimization. In addition to studying the general properties of solutions to these problems (m-term approximations for a given dictionary, classification of dictionaries by their approximative properties, etc.), various greedy-type algorithms for sparse approximation and optimization with respect to an arbitrary dictionary will be designed and studied. We will prove theorems about the convergence, convergence rate, and stability (to noise and inaccuracy of calculations) of the corresponding algorithms. Development and analysis of greedy algorithms. New greedy-type algorithms will be constructed, and their detailed analysis in terms of convergence rate and stability will be carried out.We propose to study the case of general Banach spaces and very general dictionaries in them. We plan to apply greedy algorithms in the convex minimization problem. The practical effectiveness of the developed methods of greedy approximations will be verified by numerical experiments. Problems of multidimensional approximation and related questions of convex geometry. Multidimensional approximation and calculation methods. Smoothness classes. It is expected to obtain new estimates of the asymptotic characteristics of classes of mixed smoothness functions and some other classes. In addition, we plan to find new relations between various asymptotic characteristics, for example, between the Kolmogorov widths and the optimal recovery errors from the sample. In addition to theoretical interest these results are important in numerical methods, for example, for numerical analysis of the Schrodinger equation. A theoretical analysis of multidimensional approximation problems that are important in numerical calculations will be made. General greedy-type algorithms will be applied to the problem of constructive sparse approximation of functions by tensor products. In particular, we plan to develop practical algorithms for sparse approximation with respect to dictionaries with a tensor product structure. Greedy-type algorithms will be used for constructive sparse approximation with respect to a dictionary of ridge functions. This problem is closely related to neural networks and has important applications in statistics and learning theory. Methods of multidimensional convex geometry will be developed, necessary for proving new results in the theory of cross-sections, in a number of problems on the properties of restrictions of linear operators on coordinate subspaces, and in the theory of compressed sensing. The discretization problem. Universal discretization. The recovery by the sample. A number of results are expected for the discretization problem. To recover an unknown function of many variables from a sample of its values at a finite number of points, we will construct recovery operators (algorithms) that are good in terms of accuracy, stability, and software implementation. We will find relationships between Kolmogorov widths and optimal recovery errors for a given class of functions. The corresponding analysis will be based on deep results of discretization of integral norms of functions from finite-dimensional subspaces. A universal discretization will be studied for a set of subspaces of a given dimension defined by a given dictionary. The obtained results, developed methods and algorithms can be applied to build practical systems for processing big data. The expected results will be at or above the level of existing Russian and foreign analogues.

Annotation of the results obtained in 2023
It is shown how a combination of known results on universal sampling discretization of the uniform norm and recent results on universal sampling representation allows us to provide good universal methods of sampling recovery for anisotropic Sobolev and Nikol'skii classes of periodic functions of several variables. Some results on the rate of convergence of greedy algorithms, which provide expansions, were proved. In particular, it was established that the pure greedy algorithm (PGA) is as good as the orthogonal greedy algorithm (OGA) in this new sense of the rate of convergence, while it is known that the PGA is much worse than the OGA in the standard sense. New estimates for the number of points required for the sharp in order discretization of all functions from a given N-dimensional subspace in the space of continuous functions are obtained. The new breakthrough results on the density of quantized approximations in Banach spaces are obtained. In particular, the nontrivial conditions on a subset of Banach space sufficient for the density of arbitrary sums of elements of this subset in the entire space are found. These conditions are applied for particular problems of approximation by simple partial fractions, sums of shifts of a single function, integer combinations of an arbitrary countable family of functions, etc. The families of convex closed symmetric sets in Hilbert space which have a nonempty intersection are considered. It is proved that the subsequent projections on them for which the new point is projected on the remotest set always converge to the same common point of this family. It is proved that the sets of lattice and symmetric finite representability for any separable Orlicz space coincide. Moreover, these sets can be desribed in terms of the Boyd indices and coincide with the set of all r such that the corresponding space contains a sequence of disjoint functions equivalent to the canonical l_r-basis. A characterization of strongly embedded subspaces of an Orlicz space generated by independent and identically distributed functions is obtained and conditions which guarantee that the unit ball of such subspace consists of functions with equicontinuous norms in this space are found. A class of Orlicz spaces for which these properties can be characterized using the Orlicz–Matuszewska indices is identified. An exact description of the trace-space of the Sobolev space to the lower content regular subsets of metric measure spaces is obtained in terms of generalized Calderon maximal functions. It is proved that it is impossible to have a good approximation of the identity matrix by sparse matrices of logarithmic rank. For classes of periodic splines and splines on the segment the estimates of concentration of L_1 norm are improved. The new effective method for computation of the regularity in L_2 for refinable functions in non-isotropic case, when the dilation matrix is not similar to orthogonal matrix multiplied by a number, is developed. This method allows the computation of the regularity of some tile B-splines in higher dimensions. A complete classification of invariant Barabanov norms (Lyapunov norms) for linear switching systems is derived. The criterion of uniqueness of the invariant norm is found. A class of systems with degenerate matrices is also considered, and it is shown that in this case the invariant body is a polygon. The problem of the existence of self-dual antinorms in a positive orthant of the real space whose dimension is greater than two is solved. An explicit construction allowing to construct corresponding to uniquely defined antinorms autopolar polytopes with any given number of vertices in any positive orthant of the real space whose dimension is greater than two, is presented. For a finite orthogonal system of functions bounded by one in the L_p norm for p > 2, the existence of a partition into dense subsystems with the lacunarity property in Orlicz space close to L_2 and with good estimates of the norm of maximal partial sum operator is established. The study of unitary (k,a)-generalized Fourier transform on the line with power weight is reduced to the study of unitary nondeformed generalized Dunkl transform. For generalized Dunkl Laplacian for which the kernel of generalized Dunkl transform is an eigenfunction, the description of invariant space is obtained. The linear intertwining operator is constructed. It allows to obtain the kernel of generalized Dunkl transform from the kernel of classical Fourier transform and establish the connection between generalized Dunkl Laplacian and Laplace operator. Two generalized translation operators are defined. Integral representations are obtained for them and boundness in L^p spaces with power weight is proved. Two convolutions are defined for which the Young theorem is established. Two types of generalized means are defined, and the sufficient conditions on their L_p convergence and convergence almost everywhere are given. The generalized means of Gauss-Weierstrass, Poisson, and Bochner–Riesz are studied. It is proved that for any class of multidimensional integrable functions or quasi-measures whose Fourier coefficients in the Vilenkin–Chrestenson system are majorized by a given sequence tending to zero, there are recovering sets of arbitrarily small measure. For functions from p-ary Sobolev and Korobov classes with small smoothness parameters, their approximations are constructed using the values of the functions on sets of small measure, and the accuracy of such approximations is found. Some constructions of frames and systems of orthorecursive decomposition from sequences of discretized values of the Szego kernel in the Hardy space are given. The class of deviation sequences is expanded, for which the problem of the existence of an element of a Banach space with these deviations from a system of nested subspaces is solved positively, regardless of the space and the system of subspaces. Based on this result, the constants of weak asymptotics in S. V. Konyagin's theorem on the existence of an element whose deviations are asymptotically close to the given ones are improved. During the reporting period, 11 articles were published in leading peer-reviewed scientific journals, including one review. The members of group took participation in organization of two international conferences: "Approximation, Expansions and Computer Science" (Sochi, Sirius, Russia, 19–23.09.2023) and "Nonlinear Approximation and Discretization" (Moscow, Russia, October 29 – November 3, 2023). Two Ph.D. theses were defended in September 2023: T.I. Zaitseva "Self-affine tilings and multivariate approximation", K.S. Shklyaev "New topological and geometrical properties of metric projection". The defense of a doctoral dissertation is planned in December 2023: A.I. Tyulenev "The characterization of traces of Sobolev spaces on irregular subsets of metric spaces with measure".

Publications

1. Astashkin S.V. On Various Notions of Representability of l_r-Spaces in Orlicz Function Spaces Mathematical Notes, Volume 114, Issue 3, pp. 403-406 (year - 2023) https://doi.org/10.1134/S0001434623090110

2. Astashkin S.V. On Subspaces of an Orlicz Space Spanned by Independent Identically Distributed Functions Doklady Mathematics, Volume 108, Issue 1, pp. 297-299 (year - 2023) https://doi.org/10.1134/S1064562423700801

3. Ivanov V.I. Недеформированное обобщенное преобразование Данкля на прямой Математические заметки, Том 114, Выпуск 4, С. 509–524 (year - 2023) https://doi.org/10.4213/mzm14021

4. Ivanov V.I. Оператор сплетения для обобщенного преобразования Данкля на прямой Чебышевский сборник, Том 24, Выпуск 4, С. 108-122 (year - 2023) https://doi.org/10.22405/2226-8383-2023-24-4-108-122

5. Limonova I.V. Плотные слабо лакунарные подсистемы ортогональных систем и оператор мажоранты частных сумм Математический сборник, Том 214, Выпуск 11, С. 63-88 (year - 2023) https://doi.org/10.4213/sm9929

6. Makarov M.S. Antinorms and Self-Polar Polyhedra Siberian Mathematical Journal, Volume 64, Issue 5, pp. 1200-1212 (year - 2023) https://doi.org/10.1134/S0037446623050129

7. Skvortsov Yu.A. О существовании элемента с заданными уклонениями от расширяющейся системы подпространств Математические заметки, Том 114, Выпуск 5, С. 780-788 (year - 2023) https://doi.org/10.4213/mzm13982

8. Temlyakov V.N. On the Rate of Convergence of Greedy Algorithm Mathematics, Volume 11, Issue 11, 2559 (year - 2023) https://doi.org/10.3390/math11112559

9. Terekhin P.A. Орторекурсивные разложения, порожденные ядром Сеге Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика, Том 23, Выпуск 4, С. 443-455 (year - 2023) https://doi.org/10.18500/1816-9791-2023-23-4-443-455

10. Tyulenev A.I. Traces of Sobolev Spaces on Piecewise Ahlfors–David Regular Sets Mathematical Notes, Volume 114, Issue 3, pp. 351-376 (year - 2023) https://doi.org/10.1134/S0001434623090079

11. Borodin P.A., Shklyaev K.S. Плотность квантованных приближений Успехи математических наук, Том 78, Выпуск 5(473), С. 3-64 (year - 2023) https://doi.org/10.4213/rm10115