Efficient Models for Multivariate Functions and High-Dimensional Approximation
Final Report Abstract
Im Projekt “Effiziente Modelle für multivariate Funktionen und hochdimensionale Approximation” arbeiteten ein Gruppenleiter und zwei Doktoranden sowie verschiedene studentische Hilfskräfte an aktuellen Fragen der multivariaten Approximationstheorie. Im einzelnen ging es um praktisch relevante Modelle multivariater Funktionen, die einerseits durch Regularitätsannahmen (Glattheit) oder andererseits durch strukturelle Annahmen beschrieben werden. Ziel des Projektes war es, solche Funktionen effizient zu approximieren und dabei den Fluch der Dimension zu vermeiden. Darunter versteht man das rasche Anwachsen der notwendigen Rechenzeit in der Dimension. Ein wichtiger Aspekt in diesem Zusammenhang ist das Verständnis der Präasymptotik, d.h. den Verlauf des worst-case Fehlers bei vergleichsweise wenig Eingabeinformatio. Dazu sind untere Schranken geeigneter Gelfand-Weiten bzw. Untersuchungen zur metrischen Entropie unerlässlich. Konkret lassen sich die Projektziele in drei Punkte unterteilen. Zunächst geht es um die Approximation von Funktionen mit beschränkter gemischter Ableitung. Anschließend werden die zulässigen Algorithmen dahingehend eingeschränkt, dass nur diskrete Information erlaubt ist (Punktauswertungen). In diesem Zusammenhang betrachten wir Approximation und numerische Integration multivariater Funktionen und interessieren uns für die optimale Wahl der Abtastpunkte im Rd, eine anspruchsvolle Frage mit Bezügen zur Zahlentheorie und hochdimensionalen Geometrie. Schließlich geht es im dritten Punkt um die Verbesserung der Komplexität durch zusätzliche strukturelle Annahmen wie sie beispielsweise bei sogenannten Ridgefunktionen vorliegen. Außerdem spielen Dünnbesetztheitsannahmen eine wichtig Rolle. In allen drei Bereichen wurden praktisch relevante und teilweise überraschende Entdeckungen gemacht. Die präasymptotische Rate ist ein gewaltiger Fortschritt gegenüber der Abschätzung, die für kleine n nutzlos ist. Außerdem haben wir das Problem der optimalen Ordnung des Fehlers bei der numerischen Integration multivariater Funktionen dominierend gemischter Glattheit abschließend und umfassend gelöst. Unsere Analyse der Frolov-Methode zeigt, dass diese universell und optimal ist, zunächst im asymptotischen Sinne. Eine solche Schlagkraft war bisher nur für die Fibonacci-Methode bekannt. Für die multivariate Situation ist das neu und interessant, insbesondere für Anwender, die nun nach effizienten Implementierungen dieser fragen [B1]. Darüber hinaus liefert unsere Analyse neue strukturelle Einblicke in klassische Funktionenraäume. Das eigenartige und überraschende Verhalten des Integrationsfehlers hat weitere Forschungen motiviert. Hier konnten wir eine ca. 30 Jahre alte Frage zur Unbedingtheit der Haar-Basis negativ beantworten. Geht man von der Integration einen Schritt weiter und fragt nach der Approximation solcher Funktionen, so ist eine maßgeschneiderte Methode entwickelt worden, mit der man elegant Samplingzahlen abschätzen kann. Auf diese Weise lässt sich Approximation mittels diskreter Information und nichtdiskreter Information vergleichen. Es stellt sich außerdem heraus, dass die Dünngitterapproximation nach wie vor die asymptotisch beste Methode ist, die man bisher kennt. Überraschenderweise sind Punktmengen, die sich gut bei der Integration verhalten, nicht unbedingt gut für die Approximation. Im Hinblick auf die Rekonstruktion von Ridge-Funktion zeigen unsere Resultate, dass dieses Problem im Allgemeinen viel schwieriger ist, als die simple Struktur der Ridge-Funktionen vermuten lässt. Wir konnten zeigen, dass zusätzliche Annahmen, die über die Ridge-Struktur hinaus gehen, essentiell sind um eine effiziente Lösbarkeit des L∞-Rekonstruktionsproblems sicherzustellen, selbst dann, wenn es den Algorithmen gestattet ist, Zufallselemente zu verwenden. Das Studium von Glattheitsgewichten unter Verwendung von Dünnbesetztheitsannahmen (bzw. Relaxierung davon wie Kompressibilität oder Hyperbolisches-Kreuz-Annahmen) haben eine neue interessante Beziehung zwischen klassischen isotropen Sobolev-Räumen und Sobolev-Räumen dominierend gemischter Glattheit aus dem Blickwinkel der informationsbezogenen Komplexitätstheorie offenbart. Weiterhin wurde eine elegante Charakterisierungsmethode entwickelt, die Approximationszahlen auf durch die Glattheitsgewichte bestimmte Entropiezahlen zurückführt. Diese Methode verspricht interessante Anwendungen.
Publications
- N-widths and ε-dimensions for high-dimensional approximations. Found. Comput. Math., 13(6):965–1003, 2013
D. Dũng and T. Ullrich
(See online at https://doi.org/10.1007/s10208-013-9149-9) - Approximation of mixed order Sobolev functions on the d-torus–asymptotics, preasymptotics and d-dependence. Constr. Appr., 42(3), 353–398, 2015
T. Kühn, W. Sickel, and T. Ullrich
(See online at https://doi.org/10.1007/s00365-015-9299-x) - Entropy and sampling numbers of classes of ridge functions. Constr. Appr., 42:231–264, 2015
S. Mayer, T. Ullrich, and J. Vybiral
(See online at https://doi.org/10.1007/s00365-014-9267-x) - Counting via entropy – new preasymptotics for the approximation numbers of Sobolev embeddings. SIAM J. Num. Analysis, 54(6):3625-3647, 2016
T. Kühn, S. Mayer, and T. Ullrich
(See online at https://doi.org/10.1137/16M106580X) - The role of Frolov’s cubature formula for functions with bounded mixed derivative. SIAM J. Numer. Anal., 54(2):969–993, 2016
M. Ullrich and T. Ullrich
(See online at https://doi.org/10.1137/15M1014814) - Haar projection numbers and failure of unconditional convergence in Sobolev spaces. Mathematische Zeitschrift, 285:91–119, 2017
A. Seeger and T. Ullrich
(See online at https://doi.org/10.1007/s00209-016-1697-7) - On the orthogonality of the Chebyshev-Frolov lattice and applications. Monatshefte für Mathematik, 184(3):425–441, 2017
C. Kacwin, J. Oettershagen, and T. Ullrich
(See online at https://doi.org/10.1007/s00605-017-1078-2) - Optimal sampling recovery of mixed order Sobolev embeddings via discrete Littlewood-Paley type characterizations. Analysis Mathematica, 43(2):133–191, 2017
G. Byrenheid and T. Ullrich
(See online at https://doi.org/10.1007/s10476-017-0303-5) - Hyperbolic cross approximation. Advanced Courses in Mathematics. CRM Barcelona. Birkhäuser/Springer, 218 pp., Nov. 2018
D. Dũng, V.N. Temlyakov, and T. Ullrich
(See online at https://doi.org/10.1007/978-3-319-92240-9) - The Haar system as a Schauder basis in spaces of Hardy-Sobolev type. J. Fourier Anal. Appl. 2018, Volume 24, Issue 5, pp 1319–1339
G. Garrigós, A. Seeger, T. Ullrich
(See online at https://doi.org/10.1007/s00041-017-9583-1)
