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.