Verteilte Unsicherheitsquantifizierung der Kernelinterpolation auf Kugeln

Inhaltsübersicht

Zusammenfassung und Einführung

Unsicherheitsbeziehung der Kernelinterpolation auf Kugeln

Verteilte Kernel-Interpolation

Operatordifferenzen über Quadraturregeln

Beweise

Numerische Überprüfungen

Verweise

Abstrakt

Für die Kernelinterpolation mit radialer Basisfunktion (RBF) von verstreuten Daten bewies Schaback [30] 1995, dass der erreichbare Approximationsfehler und die Bedingungszahl der zugrunde liegenden Interpolationsmatrix nicht gleichzeitig klein gemacht werden können. Er bezeichnete diesen Befund als „Unsicherheitsbeziehung“, deren unerwünschte Folge darin besteht, dass die RBF-Kernelinterpolation anfällig für verrauschte Daten ist. In diesem Artikel schlagen wir eine verteilte Interpolationsmethode vor und untersuchen sie, um die Unsicherheit zu verwalten und zu quantifizieren, die durch die Interpolation verrauschter sphärischer Daten nicht vernachlässigbarer Größenordnung entsteht. Wir präsentieren auch numerische Simulationsergebnisse, die zeigen, dass unsere Methode praktisch und robust im Hinblick auf den Umgang mit verrauschten Daten aus anspruchsvollen Computerumgebungen ist.

Schlüsselwörter. Kernel-Interpolation, verteilte Unsicherheitsminderung, verstreute sphärische Daten

Unsicherheitsbeziehung der Kernelinterpolation auf Kugeln

3. Verteilte Kernel-Interpolation.

Folgerung 2.2 zeigt, dass die Kernel-Interpolation bei verrauschten Daten nicht vernachlässigbarer Größenordnung schlecht abschneidet. Um diesen großen Nachteil zu überwinden, schlagen wir in diesem Abschnitt eine Methode der verteilten Kernelinterpolation (DKI) vor und untersuchen sie, die durch das „verteilte Lernen“ in der Literatur motiviert ist [37, 19]. Im übertragenen Sinne handelt es sich hierbei um eine Divide-and-Conquer-Strategie zur Unsicherheitsquantifizierung. Zur Erläuterung beschreiben wir die Methode in drei Schritten.

4. Operatorunterschiede über Quadraturregeln.

In diesem Abschnitt stellen wir zunächst kurz einen Integraloperator-Ansatz dar, der in [8] initiiert wurde, und leiten dann enge Obergrenzen für Unterschiede von Operatoren von unserem Interesse ab, wobei wir als Nebenprodukt eine bestimmte Art von Sobolev-Stichprobenungleichungen erhalten [12]. Zu den Höhepunkten des Abschnitts gehören Proposition 4.5) und Lemma 4.8.

6. Numerische Überprüfungen

In diesem Abschnitt werden vier Simulationen durchgeführt, um die hervorragende Leistung von DKI zu überprüfen. Die erste zeigt, dass es DKI gelingt, die Unsicherheit der Kernel-Interpolation zu umgehen. Der zweite zeigt die Rolle von m im DKI. Der dritte Schwerpunkt liegt auf der Rolle der Divisionsstrategie im DKI. Der letzte vergleicht DKI mit mehreren gängigen sphärischen Datenanpassungsschemata, einschließlich der verteilten gefilterten Hyperinterpolation (DFH) [21], dem Skizzieren mit s ∗ -Designs [20] und der verteilten Kernel-Ridge-Regression (DKRR) [8].

Simulation 2: In dieser Simulation zeigen wir die Rolle des Parameters m im DKI. Wir generieren 10014 Trainingsbeispiele (mit 141 Designs als Eingaben). Die Anzahl der Unterteilungen m reicht von {5, 10, · · · , 200}. Abbildung 6.2 zeigt die Beziehung zwischen RMSE von DKI und der Anzahl lokaler Maschinen bei unterschiedlichem Gauß-Rauschen, vorausgesetzt, dass die Gesamtzahl der Trainingsbeispiele angegeben ist. Aus Abbildung 6.2 können wir die folgenden Aussagen schließen: 1) Bei Trainingsproben mit höheren Rauschpegeln nimmt der Test-RMSE im Allgemeinen zunächst ab und steigt dann langsam an, wenn die Anzahl der lokalen Maschinen zunimmt. Moderate Werte von m führen eher zu einer guten Näherung für DKI. Der Grund dafür ist, dass ein zu kleines m das Unsicherheitsproblem bei der Kernel-Interpolation nicht erfolgreich löst; Ein zu großes m erhöht den Anpassungsfehler, was zu einer etwas schlechteren Generalisierungsleistung führt. 2) Die optimale Zahl m mit dem niedrigsten RMSE wächst mit zunehmendem Gaußschen Rauschen. Dies bestätigt die Gleichung (3.3) von Theorem 3.2, in der der Näherungsfehler hauptsächlich mit dem Stichprobenfehler für großes Rauschen (dh großes M) zu tun hat und mit einem großen m reduziert werden kann.

VERWEISE

[1] R. Bhatia, Matrix Analysis, vol. 169, Springer Science & Business Media, 2013.

[2] JS Brauchart und K. Hesse, Numerical Integration over Spheres of Arbitrary Dimension, Constructive Approximation, 25 (2007), S. 41–71.

[3] G. Brown und F. Dai, Approximation of Smooth Functions on Compact Two-Point Homogen Spaces, Journal of Functional Analysis, 220 (2005), S. 401–423.

[4] A. Chernih, IH Sloan und RS Womersley, Wendland-Funktionen konvergieren mit zunehmender Glätte zu einer Gaußschen Funktion, Advances in Computational Mathematics, 40 (2014), S. 185–200.

[5] F. Dai, Multivariate polynomiale Ungleichungen in Bezug auf Verdopplungsgewichte und a∞-Gewichte, Journal of Functional Analysis, 235 (2006), S. 137–170.

[6] F. Dai, On generalized hyperinterpolation on the sphere, Proceedings of the American Mathematical Society, 134 (2006), S. 2931–2941.

[7] HW Engl, M. Hanke und A. Neubauer, Regularization of Inverse Problems, vol. 375, Springer Science & Business Media, 1996.

[8] H. Feng, S.-B. Lin und D.-X. Zhou, Radiale Basisfunktionsnäherung mit verteilt gespeicherten Daten auf Kugeln, arXiv:2112.02499, (2021).

[9] T. Hangelbroek, FJ Narcowich,

[10] T. Hangelbroek, FJ Narcowich und JD Ward, Kernel approximation on mannigfaltigkeiten i: Bounding the Lebesgue Constant, SIAM Journal on Mathematical Analysis, 42 (2010), S. 1732–1760.

[11] K. Hesse, IH Sloan und RS Womersley, Radial Basis Function Approximation of Noisy Scattered Data on the Sphere, Numerische Mathematik, 137 (2017), S. 579–605.

[12] K. Hesse, IH Sloan und RS Womersley, Local rbf-based bestrafte Approximation der kleinsten Quadrate auf der Sphäre mit verrauschten Streudaten, Journal of Computational and Applied Mathematics, 382 (2021), S. 113061.

[13] S. Hubbert, QT Le Gia und TM Morton ˆ , Sphärische radiale Basisfunktionen, Theorie und Anwendungen, Springer, 2015.

[14] MA King, RJ Bingham, P. Moore, PL Whitehouse, MJ Bentley und GA Milne, Lower Satellite-Gravimetry Estimates of Antarctic Sea-Level Contribution, Nature, 491 (2012), S. 586–589.

[15] QT Le Gia, FJ Narcowich, JD Ward und H. Wendland, Continuous and Discrete Least Squares Approximation by Radial Basis Functions on Spheres, Journal of Approximation Theory, 143 (2006), S. 124–133.

[16] P. Leopardi, Eine Aufteilung der Einheitssphäre in Regionen gleicher Fläche und kleinen Durchmessers, Electronic Transactions on Numerical Analysis, 25 (2006), S. 309–327.

[17] J. Levesley, Z. Luo und X. Sun, Normschätzungen von Interpolationsmatrizen und deren Umkehrungen im Zusammenhang mit streng positiv definiten Funktionen, Proceedings of the American Mathematical Society, (1999), S. 2127–2134.

[18] S.-B. Lin, X. Chang und X. Sun, Kernel-Interpolation hochdimensionaler Streudaten, arXiv-Vorabdruck arXiv:2009.01514, (2020).

[19] S.-B. Lin, X. Guo und D.-X. Zhou, Verteiltes Lernen mit regulierten kleinsten Quadraten, The Journal of Machine Learning Research, 18 (2017), S. 3202–3232.

[20] S.-B. Lin, D. Wang und D.-X. Zhou, Skizzieren mit sphärischen Designs auf Kugeln, SIAM Journal on Scientific Computation, im Druck (2023).

[21] S.-B. Lin, YG Wang und D.-X. Zhou, Verteilte gefilterte Hyperinterpolation für verrauschte Daten auf der Kugel, SIAM Journal on Numerical Analysis, 59 (2021), S. 634–659.

[22] JD McEwen und Y. Wiaux, A Novel Sampling Theorem on the Sphere, IEEE Transactions on Signal Processing, 59 (2011), S. 5876–5887.

[23] H. Mhaskar, F. Narcowich und J. Ward, Spherical marcinkiewicz-zygmund inequalities and positive quadrature, Mathematics of Computation, 70 (2001), S. 1113–1130.

[24] HN Mhaskar, Weighted Quadrature Formulas and Approximation by Zonal Function Networks on the Sphere, Journal of Complexity, 22 (2006), S. 348–370.

[25] C. Muller ¨ , Spherical Harmonics, vol. 17, Springer, 1966.

[26] FJ Narcowich, N. Sivakumar und JD Ward, Stabilitätsergebnisse für die Interpolation verstreuter Daten auf euklidischen Sphären, Advances in Computational Mathematics, 8 (1998), S. 137–163.

[27] FJ Narcowich,

[28] FJ Narcowich und JD Ward, Scattered Data Interpolation on Spheres: Error Estimates and Local Supported Basis Functions, SIAM Journal on Mathematical Analysis, 33 (2002), S. 1393–1410.

[29] A. Rudi, R. Camoriano und L. Rosasco, Weniger ist mehr: Nystrom computational regularization., in NIPS, 2015, S. 1657–1665.

[30] R. Schaback, Fehlerschätzungen und Bedingungszahlen für die Interpolation radialer Basisfunktionen, Advances in Computational Mathematics, 3 (1995), S. 251–264.

[31] S. Smale und D.-X. Zhou, Shannon Sampling und Funktionsrekonstruktion aus Punktwerten, Bulletin of the American Mathematical Society, 41 (2004), S. 279–305.

[32] S. Smale und D.-X. Zhou, Shannon Sampling II: Verbindungen zur Lerntheorie, Applied and Computational Harmonic Analysis, 19 (2005), S. 285–302.

[33] Y.-T. Tsai und Z.-C. Shih, All-Frequenz-vorberechneter Strahlungstransfer unter Verwendung sphärischer radialer Basisfunktionen und Clustered-Tensor-Approximation, ACM Transactions on Graphics (TOG), 25 (2006), S. 967–976.

[34] H. Wendland, Scattered data approximation, vol. 17, Cambridge University Press, 2004.

[35] MA Wieczorek und RJ Phillips, Potenzielle Anomalien auf einer Kugel: Anwendungen auf die Dicke der Mondkruste, Journal of Geophysical Research: Planets, 103 (1998), S. 1715–1724.

[36] RS Womersley, Efficient sphärische Designs mit guten geometrischen Eigenschaften, in Contemporary Computational Mathematics – Eine Feier zum 80. Geburtstag von Ian Sloan, Springer, 2018, S. 1243–1285.

[37] Y. Zhang, J. Duchi und M. Wainwright, Teilen und Erobern der Kernel-Ridge-Regression: Ein verteilter Algorithmus mit minimalen optimalen Raten, The Journal of Machine Learning Research, 16 (2015), S. 3299–3340.

SM1. Anhang A: Select-and-Judge-Strategie für die Datenabteilung. In diesem Anhang stellen wir die detaillierte Umsetzung der Select-and-Judge (SAJ)-Strategie vor. Unser Ziel ist es, eine Reihe von Teilmengen ähnlicher Kardinalität abzuleiten, deren Trennungsradius nicht kleiner als eine gegebene Toleranz c0 ist. Es gibt zwei Stufen für SAJ.