Approximation und Optimierung in höheren Dimensionen

Die Dimension von zu verarbeitenden Daten in Problemen unserer modernen Gesellschaft ist mittlerweile sehr groß geworden. Um aus dieser Menge von Daten, die in einer Vielzahl moderner Anwendungen (wie das Internet, physikalische Experimente, medizinische Diagnostik um nur ein paar zu nennen) gesammelt werden, nur die wesentliche Information zu extrahieren und zu interpretieren, ist die Etablierung eines neuen Fachgebietes der Natur- und Ingenieurwissenschaften vonnöten. Die Durchführung numerischer Simulationen basierend auf diesen Daten (skaliert zu der jeweils geforderten Größenordnung) ist eine der wichtigsten Aufgaben des 21ten Jahrhunderts. Kurz gesagt müssen wir imstande sein, Komplexität zu verstehen und zu organisieren. Die bemerkenswertesten Vorstöße in diese Richtung in der modernen Datenanalyse und in numerischen Simulationen basieren auf der Erkenntnis, dass in etlichen Situationen, sogar für sehr komplexe Phänomene, nur ein paar wenige führende Komponenten benötigt werden, um die Dynamik des ganzen Problems zu beschreiben; eine Reduktion der Dimensionalität kann hierbei durch die Forderung, dass das Ergebnis dünn besetzt (englisch "sparse") bzw. komprimierbar ist, erreicht werden. Da die relevanten Freiheitsgrade des Ergebnisses nicht vorgeschrieben sind und von Problem zu Problem variieren können, brauchen wir effiziente Optimierungsmethoden um das schwierige kombinatorische Problem derer Identifizierung zu lösen. In diesem Projekt werden wir uns zuerst mit der Entwicklung effizienter Algorithmen beschäftigen, mit denen es möglich ist, auch in höher dimensionalen Fragestellungen optimale dünn besetzte Ergebnisse zu erhalten. In einem zweiten Schritt sollen die dadurch gewonnenen Werkzeuge für die Lösung partieller Differenzialgleichungen und Variationsproblemen, die auf Gebieten von großem Maßstab gelöst werden sollen, eingesetzt werden. Zuletzt werden wir diese gesamte Maschinerie in interessanten Anwendungen in der Bildverarbeitung, in Problemen freier Unstetigkeiten und freien Randwertproblemen, wie z.B. der Erkennung von Korressionsstellen und der Identifizierung von Brüchen, verwenden. Außerdem werden wir uns mit neuen Anwendungen in innovativen Gebieten wie dem automatisierten Lernen beschäftigen. In der Durchführung dieser Vorhaben werden wir mit etlichen profunden mathematischen Problemen konfrontiert. Darunter sind die Bestimmung von wohl-konditionierten Spaltenteilungen für allgemeine Matrizen (englisch "paving"), die schwierige Abschätzung der Komplexität der von uns entwickelten Algorithmen und die Etablierung der Fähigkeit dieser Verfahren die am dünnsten besetzte Lösung des jeweiligen Problems zu berechnen. Dazu werden Handwerkzeuge aus etlichen verschiedenen mathematischen Teilgebieten gebraucht. Diese beinhalten Methoden der angewandten harmonischen Analyse, der Funktionalanalysis, der Wahrscheinlichkeitstheorie, der konvexen Optimierung und der Variationsrechnung. Die wichtigsten Techniken aus der numerischen Mathematik, die verwendet werden, sind iterative Schwellenwertverfahren, Operatorenkompression, zufällige alternierende Projektionen, Teilraumkorrektur und Gebietszerlegungsverfahren.

Der Maßstab der Dimension der in unserer modernen Informationsgesellschaft auftretenden Probleme ist sehr groß geworden. Ein neuer Bereich in der Natur- und Ingenieurwissenschaft wird dringend Benötigt um bedeutende Informationen aus der Gesamtheit von gesammelten Daten, die aus einer Vielfalt von modernen Quellen (Internet, Finanzdaten, physikalische Experimente, medizinische Diagnostik, etc.) stammen, zu extrahieren und zu interpretieren. Numerische Simulationen in der erforderlichen Größenordnung werden eine der größten Herausforderungen des 21. Jahrhunderts. Kurz gesagt, müssen wir die Fähigkeit entwickeln die großen Datenmengen zu organisieren und deren Komplexität zu verstehen. Die bemerkenswertesten jüngsten Fortschritte in der Datenanalyse und numerischen Simulation sind auf der Beobachtung gegründet, dass in verschiedenen Situationen, sogar für sehr komplexe Phänomene, nur einige wenige leitende Komponenten benötigt werden, um die vollständige Dynamik zu beschreiben; Eine Dimensionalitätsreduktion kann erreicht werden, indem man eine dünnbesetzte (sparse) oder kompressible Losung fordert. Da die relevanten Freiheitsgerade nicht vorgegeben sind und von der jeweiligen Lösung abhängen können, brauchen wir effiziente Optimierungsmethoden um das schwere kombinatorische Problem, die Freiheitsgrade zu identifizieren, zu losen. Im START-Projekt sind wir zuerst das Problem angegangen, effiziente Algorithmen zu entwerfen, welche uns erlauben, dünnbesetzte Optimierungen in hoher Dimension auszuführen. Zweitens wurden darauffolgend die Werkzeuge, welche wir entwickelt haben um adaptive Dimensionalitätsreduktionen zu erzielen, als Bausteine bei der Lösung von großskaligen partiellen Differentialgleichungen oder Variationsproblemen genutzt, die in diversen Zusammenhangen auftraten. Zuletzt haben wir den gesamten Mechanismus auf interessante Anwendungen der Bildverarbeitung und numerischen Simulation angewandt und jüngst haben wir auch neue Anwendungen in innovativen Feldern, wie dem automatischen Lernen und der Regelung großer dynamischer Systeme in hoher Dimension, erforscht. Als ein Hohepunkt des Projektes und unter den wichtigsten Errungenschaften zählt die verständliche Analyse eines Algorithmus, welcher Iteratively Reweighted Least Squares genannt wird. Wir haben nicht nur gezeigt, dass dieser Algorithmus in der Lage ist sehr effizient dünnbesetzte Optimierungsprobleme zu lösen, sondern, in Betracht seiner intuitiven und leichten Implementierung und möglichen Anpassung an etliche andere Probleme (Optimierung von dünnbesetzten Vektoren und Matrizen von niedrigem Rank, nichtlineare PDEs), wurde er sehr beliebt unter Anwendern in mehreren Feldern der Angewandten Mathematik, der Mathematischen Signalverarbeitung, Informatik und Elektrotechnik. Eine andere wichtige konzeptuelle Entwicklung des Projekts war die Fusion der Werkzeuge der dünnbesetzten Optimierung und der sogenannten Mean-Field Approximation zum Konzept des Mean-Field Sparse Optimal Control für die Beschreibung von großen Systemen interagierender Repräsentanten. In einfachen Worten haben wir gezeigt, dass die Kontrolle einer sozialen Dynamik in einigen Situationen, obwohl nur limitierte Ressourcen zur Verfügung stehen, durch die ausschließliche Nutzung von sparsamen Eingriffen realisiert werden kann, solang sie geeignet durchgeführt werden. Die Botschaft ist positiv und negativ zugleich. Einerseits beweist unsere Mathematik, dass es für eine Regierung theoretisch möglich ist, eine Gesellschaft zu höherem Wohl zu führen, wenn sie ihren Status erhöhen muss. Andererseits können unsere Ergebnisse als eine Warnung an die Gesellschaft interpretiert werden, dass wenige relevante Akteure die Entwicklung von großen Gesellschaften signifikant beeinflussen können, was vielleicht nicht nur Theorie ist.