Geglättete Analyse von Konditionszahlen
Final Report Abstract
Die Laufzeit vieler iterativer numerischer Algorithmen wird von der Konditionszahl der Eingabe des Berechnungsproblems dominiert, einer kritischen Grösse, welche misst, wie sensitiv die Lösung von der Eingabe abhängt. Dies trifft zu auf iterative Verfahren der linearen Algebra, auf innere Punkt-Methoden der linearen und konvexen Optimierung, auf Homotopieverfahren zur Lösung polynomialer Gleichungssysteme, sowie auf gitterbasierte Methoden der nichtlinearen algorithmischen Geometrie. Zum Verständnis der typischen Laufzeit solcher Algorithmen wird eine Annahme über die zufällige Verteilung der Eingaben getroffen werden; häufig kann die Laufzeitanalyse auf eine entsprechende probabilistische Analyse einer Konditionszahl zurückgeführt werden. Dabei spielen geometrische Überlegungen eine wichtige Rolle. Dieser Ansatz geht zurück auf wichtige Arbeiten von Stephen Smale, Michael Shub und James Renegar. Eine Verfeinerung dieses Ansatzes, die geglättete Analyse (smoothed analysis) wurde von Daniel Spielman und Shang-Hua Teng vorgeschlagen. Hier werden kleine Störungen der Eingaben zufällig modelliert. Das Ziel des Projektes war die geglättete Analyse von Konditionszahlen und, damit verbunden, die geglättete Analyse der oben genannten numerischen Algorithmen. Das Projekt verlief insgesamt sehr erfolgreich: viele der neuen Ergebnisse sind in der Monographie Condition: The geometry of numerical algorithms von Peter Burgisser und Felipe Cucker umfassend dargestellt (Springer 2013). Ein Höhepunkt des Projekts war die Lösung von Smales 17. Problem durch Bürgisser und Cucker sowie Pierre Lairez, der für seine Arbeit mit dem “SIAM Activity Group on Algebraic Geometry Early Career Prize” ausgezeichnet wurde. Die Dissertation von Dennis Amelunxen (2011) schlägt eine Brücke zwischen konvexer Optimierung und sphärischer (konvexer) Integralgeometrie. Erstaunlicherweise sind die dabei auftretenden sphärischen intrinsischen Volumina das passende Konzept zur Analyse von Algorithmen im Compressive Sensing. (Letzere ist eine Methodik, welche die Signalverarbeitung revolutioniert hat.) Dies führte zu der mit dem “Information and Inference Best Paper Prize 2015” ausgezeichneten Arbeit von Dennis Amelunxen, Martin Lotz, Michael McCoy und Joel Tropp. Die Dissertation “Numerical and Statistical Aspects of Tensor Decompositions” von Paul Breiding (2017) und die daraus hervorgegangenen Publikationen mit seinen Coauthoren sind von grossem Interesse in der Datenanalyse. Weiterhin entwickelt Breiding zusammen mit Sascha Timme (TÜ Berlin) das leistungsfähige Julia Softwarepaket HomotopyContinuation.jl zur Lösung polynomialer Gleichungssysteme mittels Homotopieverfahren. Damit werden die theoretischen Grundlagen des Projekts den Anwendungen zugeführt. Nennenswerte, aus dem Projekt im weiteren Sinne hervorgegangene Entwicklungen sind neue numerische Algorithmen zur Berechnung von topologischen Informationen in hochdimensionalen Daten (Homologiegruppen), gegeben als semialgebraische Mengen. Schliesslich steht das Projekt in Zusammenhang mit einer fruchtbaren Entwicklung, die man als “zufällige reelle algebraische Geometrie” bezeichnen könnte.
Publications
- The probability that a slightly perturbed numerical analysis problem is difficult. Mathematics of Computation 77: 1559-1583 (2008)
P. Bürgisser, F. Cucker, and M. Lotz
(See online at https://doi.org/10.1090/S0025-5718-08-02060-7) - Coverage Processes on Spheres and Condition Numbers for Linear Programming. Annals of Probability 38(2): 570-604 (2010)
P. Bürgisser, F. Cucker, and M. Lotz
(See online at https://doi.org/10.1214/09-AOP489) - On a problem posed by Steve Smale. Annals of Mathematics 174(3): 1785–1836 (2011)
P. Bürgisser and F. Cucker
(See online at https://doi.org/10.4007/annals.2011.174.3.8) - Condition: The Geometry of Numerical Algorithms. Grundlehren der mathematischen Wissenschaften, No. 349, Springer Verlag, 570 pages, ISBN 978-3-642-38895-8, 2013
P. Bürgisser, F. Cucker
(See online at https://doi.org/10.1007/978-3-642-38896-5) - Probabilistic analysis of the Grassmann condition number. Foundations of Computational Mathematics 15(1): 3–51 (2015)
D. Amelunxen and P. Bürgisser
(See online at https://doi.org/10.1007/s10208-013-9178-4) - A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time. Foundations of Computational Mathematics 17(5): 1265–1292 (2017)
P. Lairez
(See online at https://doi.org/10.1007/s10208-016-9319-7) - The expected number of eigenvalues of a real gaussian tensor. SIAM J. Appl. Algebra Geometry 1(1), 254–271 (2017)
P. Breiding
(See online at https://doi.org/10.1137/16M1089769) - A stable, polynomial-time algorithm for the eigenpair problem. J. European Math. Society 20(6): 1375–1437 (2018)
D. Armentano, C. Beltrán, P. Bürgisser, F. Cucker, and M. Shub
(See online at https://doi.org/10.4171/JEMS/789) - Computing the homology of basic semialgebraic sets in weak exponential time. Journal of the ACM 66(1):5:1–5:30, 2018
P. Bürgisser, F. Cucker, and P. Lairez
(See online at https://doi.org/10.1145/3275242) - Probabilistic Schubert Calculus. J. reine angew. Math., 2018
P. Bürgisser and A. Lerario
(See online at https://doi.org/10.1515/crelle-2018-0009)
