As an Emmy-Noether research group funded by Deutsche Forschungsgemeinschaft, we investigate since 2012 problems arising in modern approximation theory. This article explains the goals of our research, highlights a number of achievements we made so far, and outlines intersting open research questions.
Solving Schrödinger's equation for many-particle systems, reconstructing images in computerized tomography, reverse engineering of a neural network: so different these problems sound, from an abstract mathematical point of view they have a lot in common. In fact, each of them can be posed as a problem to recover an unknown function from incomplete data. What is more, the number of influencing variables in the above examples is large or even huge. Mathematically speaking, we are facing multivariate approximation problems on high-dimensional vector spaces.
The amount of data needed to compute a reasonable approximation constitutes an important aspect when it comes to feasibility. A bad scenario in that respect is that this amount grows dramatically with the number of variables, which is commonly referred to as the curse of dimensionality. It can be an intricate business, however, to pin down exactly how hard a problem is. The modern field of information-based complexity provides the mathematical language to address this issue in a precise manner. Being a theoretical discipline, the incentive is not so much in the design of efficient algorithms for the practitioner but in establishing a taxonomy of high-dimensional problems. Mathematically, this is done by proving upper and, in particular, lower bounds for worst-case errors and then classifying the behaviour of these errors.
For some approximation problems, the required amount of information provably grows exponentially in the number of free variables---although the unknown function is smooth [KSU13a]. These problems suffer from the curse of dimensionality in a strict sense. At the same time, we know from empirical observation that many multivariate functions in the real world have much less degrees of freedom than their formal number of variables suggests [MUV14]. In information-based complexity, the aim now is twofold. First, we seek for reasonable function models that reflect these empirical observations. Second, we investigate if the prior knowledge given by the models helps to reduce the complexity of the approximation problem.
In the quest for function models, we make efforts in several directions at the INS. Sparsity models is one approach. The assumption here is that only a small number of variables may be active simultaneously. Alternatively, sparsity can mean that only a small number of Fourier or wavelet basis coefficients contribute to the function, but it is unclear which ones. Relaxing strict sparsity assumptions, we also study models where relevant Fourier modes lie in a nested hierarchy of sets with low intrinsic dimension, such as the hyperbolic cross [KSU13b] [DU13] [BDSU14]. For both hyperbolic cross and sparsity models, significant reductions in the information complexity can be shown. Recent methods from the fields of compressed sensing, sparse recovery, and convex optimization play a major role in this context [FPRU10].
The ridge function model, well-established in statistics and computerized tomography, provides a different way to describe low-dimensional structures hidden in a high-dimensional ambient space. The complexity analysis here reveals that the tractability of ridge function approximation is very sensitive with respect to the model parameters [MUV14]. Surprisingly, every degree of difficulty is possible within this very simple model.
For a given model of functions, one can pose the approximation problem in various forms, depending on what application one has in mind. Is it possible to find some inherent measure that indicates the complexity irrespectively to the specific problem formalization? A potential solution studied at the INS is metric entropy [KMU15] [MUV14] [HM2015]. It quantifies the number of representatives that are required to mimic all functions obeying the model approximately. In other words, metric entropy measures the degree of compactness of the model. A large metric entropy in fact implies that the approximation problem is hard (at least, when the function class is convex). The other way around, the implication can be strikingly wrong. The ridge function model has a small metric entropy comparable to univariate function classes. Nevertheless, for certain model parameters, the number of function values that have to be observed in order to recover an unknown ridge function grows exponentially in the number of variables.
Over the last years, the research on the complexity of high-dimensional approximation at the INS has yielded interesting results. In a number of cases, it turned out that very classical concecpts from functional analysis, such as Gelfand or dyadic entropy numbers, characterize the complexity of a problem completely. Yet, there is plenty of work to be done. There are many high-dimensional problems whose complexity is so far not well-understood. One central question for future research will be whether the use of non-discrete information (like wavelet coefficients) or non-linear algorithms helps to substantially reduce the required amount of information for certain approximation problems.