Zufällige Nyström-Approximation von nicht-negativen selbstadjungierten Operatoren

Die zufällige Singularwertzerlegung (SVD) hat sich zu einem beliebten Ansatz für die Berechnung kostengünstiger, aber genauer niedrigrangiger Approximationen von Matrizen entwickelt, aufgrund ihrer Effizienz und starken theoretischen Garantien. Neuere Arbeiten von Boullé und Townsend (FoCM, 2023) präsentieren einen unendlichen dimensionalen Analogon der zufälligen SVD zur Approximation von Hilbert-Schmidt-Operatoren. Viele Anwendungen beinhalten jedoch die Berechnung von niedrigrangigen Approximationen für symmetrische positiv semi-definite Matrizen. In diesem Kontext ist gut etabliert, dass die zufällige Nyström-Approximation in der Regel der zufälligen SVD vorgezogen wird. Dieses Papier untersucht ein unendliches dimensionales Analogon der Nyström-Approximation zur Berechnung von niedrigrangigen Approximationen nicht-negativer selbstadjungierter spurenklassiger Operatoren. Wir präsentieren eine Analyse der Methode und verbessern dabei die bestehenden unendlichen dimensionalen Schranken für die zufällige SVD. Unsere Analyse liefert Schranken für den Erwartungswert und Schranken für den Tail-Fehler der Nyström-Approximation in den Operator-, Trace- und Hilbert-Schmidt-Normen. Numerische Experimente mit einfachen Integraloperatoren validieren den vorgeschlagenen Rahmen.