Geometric aspects of random information

In this project we are concerned with the study of random information from a geometric perspective. Here, "information" describes a finite set of measurements which we apply to only partially known objects. For example, we consider function evaluations in points sampled randomly from their domain or projections of high-dimensional convex sets onto random one-dimensional subspaces. For a given numerical problem, the quality of the obtained information is determined by the error of the best possible method of solution based on this information. For many interesting problems, such as approximating certain functions or high-dimensional sets, the quality of random information is with high probability comparable to the one of optimal information. Thus, random information is practically optimal. To deepen our understanding of this phenomenon, we want to study random information, that is random point sets and subspaces, using geometric properties. On the one hand, we study random point sets via quality criteria such as the largest "hole", meaning the radius of the largest ball empty of points, or the average distance to the point set. The mean value and the random fluctuations around this mean are known for both quantities, but not so the probability of large(r) deviations, which is what we want to determine. In this context we also want to analyze random point sets on the surface of smooth convex bodies, that is certain sets such as the ball. More precisely, we want to determine the distribution of the typical hole size and the typical deviations of the distance of the smallest convex set containing the point set to the original convex set. On the other hand, we are interested in the radius of the intersection of a high-dimensional convex body with a random subspace, and in particular how much larger it is compared to the section with an optimal subspace. There is a quite general result saying that this random section is with high probability not much larger, provided the body is sufficiently "thin". We want to expand our understanding of this behavior by improving upon this known result.

The quality of random information was studied for random point sets in fixed dimension and random subspaces of fixed dimension within a space of increasing dimension. More specifically, we studied random point sets on the surface of a smooth convex body, such as a sphere. The largest "hole" on the surface that does not contain any points is closely related to the quality of function approximation and the approximation of the body by the convex hull of the points with respect to Hausdorff distance. We investigated the quality of this approximation for random point sets and determined the shape of the fluctuations around the asymptotic limit. Furthermore, in case of a high-dimensional sphere, we studied which point sets have the smallest possible largest "hole" (spherical dispersion). The best point sets in high dimensions are typically a combination of random points and a few carefully placed points. We also investigated the number of edges and facets of the convex hull of random points on the surface of a smooth convex body. In dimensions at most three, this number is almost surely determined by the number of points. In dimension four or higher, the number of edges/facets is random. We showed a lower bound for their variance and also that the shape of the fluctuations is Gaussian. This closes a notable gap in the literature. Furthermore, we formalized how to determine certain averaged quantities of the convex hull of random points on the surface of a sphere when the number of points becomes very large. An example is the average hole size which is relevant for the quality of approximation algorithms. We found that the calculations can be traced back to a model from stochastic geometry, the Poisson-Voronoi mosaic. This allows us to derive previous results, which were shown separately by studying integrals, in a common framework. One example is the behavior of the size of a "typical hole" on the surface of a sphere, which had been conjectured for five years. In another part of the project, we investigated low-dimensional projections and sections of high-dimensional convex bodies. Here, we looked at the class of p-balls. Since high-dimensional structures are difficult to imagine, it is particularly helpful to have an image (low-dimensional projection/section) from different perspectives. Typically, for a random perspective, such an image will approximately have the shape of a Euclidean ball if the ambient dimension is large. We looked at which images can occur atypically (with exponentially small probability) and formalized this using a large deviation principle in the space of convex bodies. The resulting so-called rate function is sufficiently explicit to determine, for example, the probability that the image lies in a ball smaller than a typical ball.