Montag, 16. Oktober 2023, 16:45 - 17:45 iCal

ISOR Colloquium


"Completing large low rank matrices with only few observed entries: A one-line algorithm with provable guarantees."

Speaker: Boaz Nadler (Weizmann Institute of Science, Israel)

HS 7 OMP1 (#1.303)
Oskar-Morgenstern-Platz 1, 1090 Wien


Suppose we observe very few entries from a large matrix. Can we predict the missing entries, say assuming the matrix is (approximately) low rank ? We describe a very simple method to solve this matrix completion problem. We show our method is able to recover matrices from very few entries and/or with ill conditioned matrices, where several other popular methods fail. Furthermore, due to its simplicity, it is easy to extend our method to incorporate additional knowledge on the underlying matrix, for example to solve the inductive matrix completion problem. On the theoretical front, we prove that our method enjoys some of the strongest available theoretical recovery guarantees.

Finally, for inductive matrix completion, we prove that under suitable conditions the problem has a benign optimization landscape with no bad local minima.

Zur Webseite der Veranstaltung


Institut für Statistik und Operations Research


Sabine Sobotka-Tompits, BA
Fakultät für Wirtschaftswissenschaften
Institut für Statistik und Operations Research
+43 1 4277 38631