An application of Kolmogorov's superposition theorem to function reconstruction in higher dimensions [Elektronische Ressource] / vorgelegt von Jürgen Braun

Jürgen Braun

Sujets

• Mathematics

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2009
• Nombre de lectures: 141
• Langue: Deutsch
• Poids de l'ouvrage: 4 Mo

Extrait

An Application of
Kolmogorov’s Superposition Theorem
to Function Reconstruction
in Higher Dimensions
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch{Naturwissenschaftlichen Fakult at
der
Rheinischen Friedrich{Wilhelms{Universit at Bonn
vorgelegt von
Jurgen Braun
aus
Bornheim
Bonn 2009Angefertigt mit Genehmigung der Mathematisch{Naturwissenschaftlichen Fakult at
der Rheinischen Friedrich{Wilhelms{Universit at Bonn
1. Gutachter: Prof. Dr. Michael Griebel
2. Gutachter: Prof. Dr. Mario Bebendorf
Tag der Promotion: 20. November 2009
Erscheinungsjahr: 2009
Diese Dissertation ist auf dem Hochschulschriftenserver der ULB Bonn
http://hss.ulb.uni-bonn.de/diss online elektronisch publiziert.Zusammenfassung
In der vorliegenden Arbeit wird ein Regularisierungsnetzwerk zur Rekonstruktion
nvon stetigen Funktionen f : [0; 1] !R vorgestellt, welches direkt auf einer neuen
konstruktiven Version von Kolmogorovs Superpositionen Theorem basiert. Dabei
sind lediglich die Funktionswertef(x ) an diskreten Datenpunkten x ,j = 1;:::;Pj j
bekannt.
Typischerweise leidet die numerische Losung mathematischer Probleme unter
dem sogenannten Fluch der Dimension. Dieser Begri beschreibt das exponentiel-
le Wachstum der Komplexitat des verwendeten Verfahrens mit der Dimension n.
Um dies zumindest teilweise zu vermeiden, werden ublic herweise hohere Regula-
ritatsannahmen an die Losung des Problems gemacht, was allerdings hau g unrea-
listisch ist. Daher wird in dieser Arbeit eine Darstellung der Funktion f als Su-
perposition eindimensionaler Funktionen verwendet, welche keiner hoheren Regula-
ritatsannahmen als Stetigkeit bedarf. Zu diesem Zweck wird eine konstruktive Vari-
ante des Kolmogorov Superpositionen Theorems, welche auf D. Sprecher zuruckgeht,
so angepasst, dass nur eine au ere Funktion sowie eine universelle innere Funktion
zur Darstellung vonf notwendig ist. Die Funktion ist nach einer De nition von
M. Kopp en explizit und unabhangig von f als Fortsetzung einer Funktion, welche
auf einer Dichten Teilmenge der reellen Achse de niert ist, gegeben. Der fehlende
Beweis von Existenz, Stetigkeit und Monotonie von wird in dieser Arbeit gefuhrt.
Zur Berechnung der au eren Funktion wird ein iterativer Algorithmus von Spre-
cher so modi ziert, dass jeder Iterationsschritt, abh angig von f, ein Element einer
rFolge univariater Funktionenfg liefert. Es wird gezeigt werden, dass die Folger
gegen einen stetigen Grenzwert :R!R konvergiert. Dies liefert einen konstruk-
tiven Beweis einer neuen Version des Kolmogorov Superpositionen Theorems mit
einer au eren und einer inneren Funktion.
Da die numerische Komplexitat des Algorithmus zur Berechnung von exponen-
tiell mit der Dimension wac hst, stellen wir alternativ ein Regularisierungsnetzwerk,
basierend auf dieser Darstellung, vor. Dabei wird die au ere Funktion aus gegebe-
nen Daten (x ;f(x )), j = 1;:::;P berechnet. Das Modell zur Rekonstruktion vonj j
f wird in zwei Schritten eingefuhrt. Zunachst wird zur De nition eines vorl au gen
Modells die au ere Funktion, bzw. eine Approximation an , in einer endlichen Ba-
sis mit unbekannten Koe zienten dargestellt. Diese werden dann durch eine Varia-
tionsformulierung bestimmt, d.h. durch die Minimierung eines regularisierten em-
pirischen Fehlerfunktionals. Eine detaillierte numerische Analyse zeigt dann, dass
Kolmogorovs Darstellung die Dimensionalitat von f in Oszillationen von trans-
formiert. Somit ist die Verwendung von Basisfunktionen mit lokalem Trager nicht
geeignet, da die raumliche Au osung der Approximation die starken Oszillationen
erfassen muss. Des Weiteren zeigt eine Analyse der Fouriertransformation von ,
dass die relevanten Frequenzen, unabhangig von f, a priori bestimmbar sind, unddass die au ere Funktion Produktstruktur aufweist. Dies motiviert die De nition des
endgultigen Modells. Dazu wird nun durch ein Produkt von Funktionen ersetzt
und jeder Faktor in einer Fourierbasis entwickelt. Die Koe zienten werden ebenfalls
durch Minimierung eines regularisierten empirischen Fehlerfunktionals bestimmt.
Fur beide Modelle wird ein theoretischer Rahmen in Form von Hilbertraumen
mit reproduzierendem Kern entwickelt. Die zugehorigen Normen bilden dabei jeweils
den Regularisierungsterm der entsprechenden Fehlerfunktionale. Somit konnen beide
Ansatze als Regularisierungsnetzwerke interpretiert werden. Allerdings ist zu beach-
ten, dass das Fehlerfunktional fur den Produktansatz nicht konvex ist und nichtlinea-
re Minimierungsverfahren zur Berechnung der Koe zienten notwendig sind. Weitere
ausfuhrlic he numerische Tests zeigen, dass dieses Modell in der Lage ist Funktionen
zu rekonstruieren welche von bis zu zehn Variablen abhangen.
Danksagung
An dieser Stelle moc hte ich mich bei allen Personen bedanken, die mich bei der
Fertigstellung dieser Arbeit unterstutzt haben. Dieser Dank gebuhrt an erster Stelle
meinem Betreuer Prof. Dr. Michael Griebel fur die Moglic hkeit zur Erstellung dieser
Arbeit und die Bereitstellung des Themas. Darub er hinaus hat er durch zahlreiche
Diskussionen, mit wertvollen Ideen und Ratschlagen sowie einer ausgezeichneten In-
frastruktur ein hervorragendes Arbeitsumfeld bereitgestellt. Bei Prof. Dr. Mario Be-
bendorf mochte ich mich herzlich fur die Ubernahme des Zweitgutachtens bedanken.
Ebenso gebuhrt ein gro er Dank meinen Kollegen Dr. Sven Gro und Dr. Christian
Rieger fur das Korrekturlesen und die stetige Bereitschaft zur Diskussion inhaltlicher
Fragen. Des Weiteren moc hte ich mich bei allen Kollegen und Mitarbeitern des In-
stituts fur Numerische Simulation fur die freundliche, hilfsbereite und inspirierende
Arbeitsatmosphare bedanken. Nicht zuletzt gilt mein Dank auf personlicher Ebene
meiner Frau Bettina sowie meiner Familie fur das entgegengebrachte Verstandnis
und die Geduld wahrend meiner Promotionszeit.
Bonn, im Oktober 2009 Jurgen BraunContents
1 Introduction 1
2 Kolmogorov’s superposition theorem 11
2.1 Variants of Kolmogorov’s . . . . . . . . . . . . . . . . . 13
2.2 Geometric interpretation . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Sprecher’s constructive version . . . . . . . . . . . . . . . . . . . 20
2.3.1 Discontinuity of the inner function . . . . . . . . . . 21
2.3.2 Correction of the inner . . . . . . . . . . . . 23
2.3.3 Existence of K oppen’s function . . . . . . . . . . . . 27
2.3.4 Continuity of . . . . . . . . . . . . . . . . . . . . . 29
2.3.5 Monotonicity of . . . . . . . . . . . . . . . . . . . 31
2.3.6 De nitions and reformulation with a single outer func-
tion . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.7 Modi cation of Sprecher’s algorithm . . . . . . . . . 36
2.4 Relation to Space Filling Curves . . . . . . . . . . . . . . . . . . 48
3 Approximative versions of Kolmogorov’s superposition theorem 53
3.1 Relations to neural networks and other approximation schemes . 54
3.2 Two models based on Sprecher’s theorem . . . . . . . . . . . . . 60
3.2.1 First model . . . . . . . . . . . . . . . . . . . . . . . 61
3.2.2 Second model . . . . . . . . . . . . . . . . . . . . . . 62
4 Regularization networks 63
4.1 Reproducing kernel Hilbert spaces . . . . . . . . . . . . . . . . . 65
4.2 Statistical learning theory . . . . . . . . . . . . . . . . . . . . . 70
4.3 Structural risk minimization . . . . . . . . . . . . . . . . . . . . 75
4.4 Maximum A Posteriori Interpretation . . . . . . . . . . . . . . . 78
4.5 Approximation spaces and norms . . . . . . . . . . . . . . . . . . 79
4.5.1 Regularization Network approach for the rst model 87
4.5.2 Network approach for the second model 90
5 Implementational details 95
iii Contents
5.1 Nonlinear minimizers . . . . . . . . . . . . . . . . . . . . . . . . 95
(n) (n)5.1.1 Numerical complexities for evaluations of E ,rE 99
5.2 Multiple precision arithmetic . . . . . . . . . . . . . . . . . . . . 102
5.3 Boundary values . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.4 Further remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 Numerical results 107
6.1 First model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.1.1 B-splines . . . . . . . . . . . . . . . . . . . . . . . . . 108
Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . 110
General . . . . . . . . . . . . . . . . . . . . . . . . . 112
Boundary values . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.1.2 Trigonometric polynomials . . . . . . . . . . . . . . . 116
Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . 122
General . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.1.3 Locations of the relevant frequencies . . . . . . . . . 125
6.2 Second model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.2.1 Trigonometric polynomials . . . . . . . . . . . . . . . 130
Simple example . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Numerical analysis of the nonlinear minimizers . . . . . . . . . 137 of the model parameters . . . . . . . . . . 142
Higher dimensional examples . . . . . . . . . . . . . . . . . . 146
7 Conclusions 153
A Appendix 157
A.1 Duality between RKHS’s and stochastic processes . . . . . . . . 157
A.2 Real valued formulation of rst model . . . . . . . . . . . . . . . 159
A.3 Real valued formu of second model . . . .