Friday, March 24, 2023
Lecture room B6
Institute for Exact Sciences
Sidlerstr. 5
CH-3012 Bern
16:45-17:45 h
Completing large low rank matrices with only few observed entries:
A one-line algorithm with provable guarantees
Boaz Nadler (Weizmann Institute of Science, Israel)
Suppose you 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 many 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.
