Projektionsfreie Optimierung für niedrigrangige Matrizen: Von der Singulärwertzerlegung zum Linear Minimization Oracle

Einführung in die niedrigrangige Matrixoptimierung

In der modernen Datenwissenschaft begegnen wir ständig großen Datensätzen, die als Matrizen organisiert sind. Ob es sich um Benutzerbewertungen auf Netflix, Pixeldaten von Bildern oder Finanztransaktionen handelt – oft steckt hinter den beobachteten Daten eine niedrigrangige Struktur. Die niedrigrangige Matrixoptimierung zielt darauf ab, eine Matrix mit niedrigem Rang zu finden, die eine gegebene konvexe Zielfunktion minimiert. Ein Paradebeispiel ist die Matrixvervollständigung, wie sie in Empfehlungssystemen verwendet wird: Aus einer unvollständigen Matrix von Benutzerbewertungen soll die vollständige Bewertungsmatrix rekonstruiert werden.

Das Assignment Chef-Thema aus der Vorlesung EE-556 zeigt, dass die direkte Minimierung unter einer Rangbeschränkung NP-schwer ist. Daher greift man auf konvexe Relaxation zurück: Die Nuklearnorm (Summe der Singulärwerte) ersetzt den Rang und führt zu einem handhabbaren Problem. Der Haken: Die Projektion auf die Nuklearnormkugel erfordert eine vollständige Singulärwertzerlegung (SVD), die für große Matrizen extrem zeitaufwändig ist. Genau hier setzt der Trend zu projektionsfreien Verfahren an: Statt zu projizieren, nutzt man das Lineare Minimierungs-Orakel (LMO), das nur den dominanten Singulärvektor benötigt. Das spart Rechenzeit und ist der Schlüssel zu skalierbaren Algorithmen.

Projektion auf die Nuklearnormkugel

Die Projektion einer Matrix Z auf die Nuklearnormkugel {X : ||X||_* ≤ κ} ist definiert als die Matrix X, die ||X - Z||_F minimiert und gleichzeitig ||X||_* ≤ κ erfüllt. Wie in Problem 1.1 gezeigt, kann diese Projektion über die Singulärwertzerlegung berechnet werden: Ist Z = U Σ V^T, so projiziert man den Vektor der Singulärwerte σ auf den ℓ1-Ball vom Radius κ. Die projizierten Singulärwerte σ_ℓ1 ergeben die neue Matrix X = U diag(σ_ℓ1) V^T.

Der Beweis stützt sich auf die Mirsky-Ungleichung: ||X - Z||_F ≥ ||Σ_X - Σ_Z||_F, wobei Σ_X und Σ_Z die Diagonalmatrizen der Singulärwerte sind. Die Projektion auf die Nuklearnormkugel reduziert sich also auf die Projektion des Singulärwertvektors auf den ℓ1-Ball. Das ist elegant und effizient – aber die SVD selbst ist teuer.

Implementierung und Laufzeitmessung mit MovieLens

Die Implementierung der Projektion als Funktion projNuc nutzt die bereitgestellte Funktion projL1. Mit κ = 5000 und den MovieLens-Datensätzen (100k und 1M) werden die Laufzeiten gemessen. Die 100k-Daten enthalten 100.000 Bewertungen von 1000 Benutzern für 1700 Filme – eine Matrix der Größe 1000×1700. Die 1M-Daten sind mit 6000×4000 deutlich größer. Die durchschnittliche Zeit für die Projektion auf dem 100k-Datensatz beträgt etwa 0,2 Sekunden, auf dem 1M-Datensatz etwa 2,5 Sekunden (abhängig von der Hardware). Diese Zeiten sind für einmalige Berechnungen akzeptabel, aber in iterativen Verfahren (z.B. projected gradient descent) werden hunderte Projektionen benötigt – das wird schnell zum Flaschenhals.

„Die SVD hat eine Komplexität von O(min(m^2 p, m p^2)). Für die Netflix-Daten mit 480.000 Benutzern und 18.000 Filmen wäre eine einzige SVD praktisch unmöglich.“

Stellen Sie sich vor, Sie müssten für jeden Schritt in Ihrem Lieblingsspiel eine aufwändige Berechnung durchführen – das würde die Framerate ruinieren. Genauso bremst die SVD die Optimierung aus. Daher sind projektionsfreie Alternativen wie das LMO so wertvoll.

Linear Minimization Oracle (LMO) für die Nuklearnorm

Das Linear Minimization Oracle löst für eine gegebene Matrix Z das Problem: Finde X in der Nuklearnormkugel, das das innere Produkt ⟨X, Z⟩ minimiert. Für die Nuklearnormkugel hat dieses Problem eine geschlossene Lösung: X = -κ u v^T, wobei u und v die linken und rechten Singulärvektoren zum größten Singulärwert von Z sind. Das ist in Problem 1.2 bewiesen: Man nutzt die Variationsformel der Nuklearnorm und die Tatsache, dass ⟨X, Z⟩ ≥ -κ σ_max(Z) für alle X mit ||X||_* ≤ κ gilt. Die Gleichheit wird durch die Rang-1-Matrix -κ u v^T erreicht.

Der entscheidende Vorteil: Statt der vollständigen SVD wird nur der dominante Singulärvektor benötigt. Das lässt sich mit der Potenzmethode oder dem Lanczos-Verfahren in O(nnz(Z)) Zeit berechnen – also linear in der Anzahl der Nichtnull-Einträge. Für die dünn besetzten MovieLens-Matrizen ist das enorm schnell.

Laufzeitvergleich: Projektion vs. LMO

Die Implementierung lmoNuc wird mit denselben Datensätzen getestet. Die durchschnittliche Laufzeit für den 100k-Datensatz liegt bei etwa 0,01 Sekunden, für den 1M-Datensatz bei 0,1 Sekunden – also 20- bis 25-mal schneller als die Projektion. Dieser Geschwindigkeitsvorteil wird umso größer, je größer die Matrix ist. In der Praxis werden Algorithmen wie der Frank-Wolfe-Algorithmus (auch conditional gradient genannt) verwendet, die in jeder Iteration nur ein LMO benötigen und keine Projektion. Damit können selbst riesige Probleme mit Millionen von Zeilen und Spalten angegangen werden.

Ein aktuelles Beispiel aus dem Jahr 2026: Bei der Entwicklung von KI-Modellen für personalisierte Medizin werden Genexpressionsdaten als niedrigrangige Matrizen modelliert. Die Dimensionen liegen oft im Bereich von 20.000 Genen × 100.000 Patienten – eine vollständige SVD wäre unmöglich. Projektionsfreie Verfahren ermöglichen hier erst die Analyse.

Blinde Entfaltung (Blind Deconvolution) – Ein praktisches Experiment

Im zweiten Teil des Assignments geht es um blinde Entfaltung: Aus einem unscharfen Bild (z.B. einem Kfz-Kennzeichen von einer Überwachungskamera) sollen das scharfe Bild und der Verwischungskern rekonstruiert werden. Mathematisch ist das ein bilineares inverses Problem: y = w * x, wobei w der Kern und x das Bild ist. Beide sind unbekannt, aber man weiß, dass sie in bekannten Unterräumen liegen: w = B h, x = C m. Die Matrizen B und C kodieren Vorwissen – beim Bild ist das z.B. eine Wavelet-Basis, die die Sparsity natürlicher Bilder ausnutzt.

Das Problem wird als niedrigrangige Matrixoptimierung formuliert, indem man die Faltung in eine Matrixmultiplikation umschreibt. Die Lösung erfolgt mit dem Frank-Wolfe-Algorithmus, der nur das LMO benötigt. Die Ergebnisse zeigen, dass selbst mit einer groben Schätzung des Kerns (ein einfacher Kasten in der Bildmitte) das Kennzeichen lesbar wird – ein eindrucksvoller Beweis für die Leistungsfähigkeit der Methode.

Fazit und Ausblick

Die Projektion auf die Nuklearnormkugel ist ein mächtiges Werkzeug, aber für große Datenmengen oft zu langsam. Das Linear Minimization Oracle bietet eine effiziente Alternative, die auf der Berechnung des dominanten Singulärvektors basiert. In Kombination mit dem Frank-Wolfe-Algorithmus lassen sich Probleme lösen, die sonst rechenintensiv wären. Dieser Ansatz ist nicht nur in der Bildverarbeitung, sondern auch in der Empfehlungssystem-Entwicklung, der Finanzmodellierung und der Bioinformatik weit verbreitet.

Für Studierende der Optimierung und des maschinellen Lernens ist das Verständnis dieser Techniken essenziell. Die EE-556 Hausaufgabe 4 bietet eine hervorragende Gelegenheit, Theorie und Praxis zu verbinden. Mit den bereitgestellten Code-Gerüsten und Datensätzen können Sie die Laufzeiten selbst messen und die Überlegenheit des LMO nachvollziehen.

Bleiben Sie neugierig und experimentieren Sie – die Welt der niedrigrangigen Matrizen steckt voller Überraschungen!