Matrix-Vervollständigung auf Graphen

Das Problem der Bestimmung fehlender Werte einer Matrix auf Grundlage einiger ihrer Einträge, als Matrix vervollständigen (Matrix Completion) bezeichnet, hat in den letzten Jahren viel Aufmerksamkeit erhalten. Obwohl das Problem unter der üblichen Annahme eines niedrigen Rangs NP-schwer ist, zeigten Candès und Recht, dass es genau gelöst werden kann, wenn die Anzahl der beobachteten Einträge ausreichend groß ist. In dieser Arbeit führen wir ein neues Modell zur Matrix vervollständigen ein, das Nutzinformationen über Zeilen und Spalten durch die Annahme von Gemeinschaften (Communities) nutzt. Diese Annahme ist in verschiedenen realen Problemen sinnvoll, wie zum Beispiel in Empfehlungssystemen, wo es Gemeinschaften von Menschen mit ähnlichen Vorlieben gibt und Produkte Clustern angehören, die ähnliche Bewertungen erhalten.Unser Hauptziel besteht daher darin, eine lösung mit niedrigem Rang zu finden, die durch die Proximitäten der Zeilen und Spalten strukturiert ist, die durch Graphen kodiert sind. Wir greifen auf Ideen des Manifold-Learnings zurück, um unsere Lösung so zu beschränken, dass sie auf diesen Graphen glatt ist. Dies zwingt implizit die Proximitäten von Zeilen und Spalten. Unser Modell zur Matrixrekonstruktion wird als konvexes nichtglattes Optimierungsproblem formuliert, für das ein gut gestelltes iteratives Verfahren bereitgestellt wird. Wir untersuchen und evaluieren das vorgeschlagene Matrix vervollständigen an synthetischen und realen Daten und zeigen, dass das vorgeschlagene strukturierte Modell mit niedrigem Rang in vielen Situationen dem Standardmodell der Matrix vervollständigen überlegen ist.