Approximation, sampling and compression in data science

Programme Theme

Approximation theory is the study of simulating potentially extremely complicated functions, called target functions, with simpler, more easily computable functions called approximants. The purpose of the simulation could be to approximate values of the target function with respect to a given norm, to estimate the integral of the target function, or to compute its minimum value. Approximation theory's relationship with computer science and engineering encourages solutions that are efficient with regards to computation time and space. In addition, approximation theory problems may also deal with real-life restrictions on data, which can be incomplete, expensive, or noisy. As a result, approximation theory often overlaps with sampling and compression problems.

The main aim of this programme is to understand and solve challenging problems in the high-dimensional context, but this aim is dual. On one hand, we would like to use the high-dimensional context to understand classical approximation problems. For example, recent developments have revealed promising new directions towards a break-through in a set of classical unsolved problems related to sampling in hyperbolic cross approximations. On the other hand, we want to understand why classical multivariate approximation methods fail in the modern high-dimensional context and to find methods that will be better and more efficient for modern approximation in very high dimensions. This direction will focus on two conceptual steps: First, replacement of classical smoothness assumptions by structural assumptions, such as those of sparsity used by compressed sensing. Second, the use of a nonlinear method, for instance a greedy algorithm, to find an appropriate sparse approximant.

In order to achieve the goal the programme will bring together researchers from different fields to work in groups on modern problems of high-dimensional approximation and related topics. It will foster exchange between different groups of researchers and practitioners.