Geometrische Aspekte zufälliger Information

In diesem Projekt beschäftigen wir uns mit dem Studium von zufälliger Information von einer geometrischen Perspektive aus. Hierbei bezeichnet "Information" eine endliche Menge von Messungen, die wir auf uns nur teilweise bekannte Objekte anwenden. Beispielsweise betrachten wir Auswertungen von Funktionen an zufälligen Punkten in ihrem Definitionsbereich oder Projektionen von hoch-dimensionalen konvexen Mengen auf zufällige ein-dimensionale Unterräume. Die Qualität der erhaltenen Information bestimmt sich für ein gegebenes numerisches Problem durch den Fehler der bestmöglichen Lösungsmethode basierend auf dieser Information. Die Qualität zufälliger Information ist für einige interessante Probleme, wie der Näherung von speziellen Funktionen oder hoch-dimensionalen Mengen, mit hoher Wahrscheinlichkeit ungefähr vergleichbar mit der von optimaler Information. In anderen Worten: zufällige Information ist praktisch optimal. Um das Verständnis dieses Phänomens zu vertiefen, wollen wir zufällige Information, also zufällige Punktmengen und Unterräume, anhand von geometrischen Eigenschaften studieren. Zum Einen studieren wir zufällige Punktmengen hin auf Qualitätskriterien wie das größte "Loch", also den Radius der größten Kugel, die keine Punkte enthält, oder den durchschnittlichen Abstand zur Punktmenge. Der Mittelwert und die zufälligen Fluktuationen um dieses Mittel sind für beide Größen bekannt, jedoch nicht die Wahrscheinlichkeit großer/größerer Abweichungen, die wir bestimmen wollen. In diesem Zusammenhang wollen wir auch zufällige Punktmengen auf der Oberfläche glatter konvexer Körper, also spezieller Mengen wie zum Beispiel der Kugel, analysieren. Genauer wollen wir die Verteilung der typischen Lochgröße und die zufälligen Fluktuationen für den Abstand der kleinsten konvexen Menge, die die Punktmenge enthält, von der ursprünglichen konvexen Menge bestimmen. Zum Anderen sind wir am Radius eines Schnittes eines hoch-dimensionalen konvexen Körpers mit einem zufälligen Unterraum interessiert und insbesondere, um wieviel dieser größer ist als der Schnitt mit einem optimalen Unterraum. Hier gibt es ein recht allgemeines Resultat, das besagt, dass der zufällige Schnitt mit hoher Wahrscheinlichkeit nicht viel größer sein kann, wenn der Körper ausreichend "dünn" ist. Wir wollen das Verständnis dieses Verhaltens erweitern, indem wir das bestehende Resultat verbessern.

Die Qualität zufälliger Information wurde anhand von zufälligen Punktmengen in fixer Dimension und zufälligen Unterräumen fixer Dimension innerhalb eines Raumes mit wachsender Dimension studiert. Genauer haben wir in einem Teil des Projekts zufällige Punktmengen auf der Oberfläche eines glatten konvexen Körpers, wie etwa der Kugeloberfläche, studiert. Das größte "Loch" auf der Oberfläche, das keine Punkte enthält, steht in engem Zusammenhang mit der Qualität für Funktionsapproximation und der Näherung des Körpers durch die konvexe Hülle der Punkte bezüglich des Hausdorffabstandes. Die Qualität dieser Näherung haben wir für zufällige Punktmengen untersucht und die Gestalt der Fluktuationen um den asymptotischen Grenzwert bestimmt. Weiters haben wir im Fall einer hochdimensionalen Kugeloberfläche studiert, welche Punktmengen ein möglichst kleines größtes "Loch" (sphärische Dispersion) besitzen. Die besten Punktmengen in hoher Dimension sind typischerweise eine Kombination aus zufälligen Punkten und wenigen gezielt plazierten Punkten. Außerdem haben wir die Anzahl der Kanten und Facetten der konvexen Hülle von zufälligen Punkten auf der Oberfläche eines glatten konvexen Körpers untersucht. In Dimension höchstens drei, ist diese Anzahl fast sicher durch die Anzahl der Punkte bestimmt. In Dimension vier oder höher ist die Anzahl der Kanten/Facetten zufällig. Wir haben eine untere Schranke für deren Varianz gezeigt und außerdem, dass die Gestalt der Fluktuationen einer Normalverteilung entspricht. Dies schließt eine bedeutende Lücke in der Literatur. Weiters haben wir formalisiert, wie man gewisse mittlere Größen der konvexen Hülle von zufälligen Punkten auf der Kugeloberfläche bestimmen kann, wenn die Anzahl der Punkte sehr groß wird. Ein Beispiel dafür ist etwa die mittlere Lochgröße, die für die Qualität von Approximationsalgorithmen relevant ist. Wir haben herausgefunden, dass man die Berechnung auf ein Modell aus der stochastischen Geometrie, das Poisson-Voronoi Mosaik, zurückführen kann. Das erlaubt uns bisherige Resultate, die separat durch das Studium von Integralen gezeigt wurden, in einem gemeinsamen Rahmen herzuleiten. Ein Beispiel ist etwa das Verhalten der Größe eines "typischen Loches" auf der Kugeloberfläche, was fünf Jahre lang vermutet wurde. In einem anderen Teil des Projektes haben wir niedrigdimensionale Projektionen und Schnitte von hochdimensionalen konvexen Körpern untersucht. Hierbei haben wir uns die Klasse der p-Kugeln angesehen. Da man sich hochdimensionale Strukturen schwer vorstellen kann, ist es besonders hilfreich ein Bild (niedrig-dimensionale(r) Projektion/Schnitt) aus verschiedenen Perspektiven zu haben. Typischerweise, für eine zufällige Perspektive, wird so ein Bild für große Umgebungsdimension näherungsweise die Form einer Kugel haben. Wir haben uns angesehen, welche Bilder atypischerweise (mit exponentiell kleiner Wahrscheinlichkeit) auftreten können und dies mithilfe eines Prinzip der großen Abweichungen im Raum der konvexen Körper formalisiert. Die auftretende sogenannte Ratenfunktion ist hinreichend explizit, um etwa die Wahrscheinlichkeit zu bestimmen, dass das Bild in einer kleiner als typischen Kugel liegt.