Abstract:

Suppose you observe very few entries from a large matrix. In many applications, you can safely assume the matrix is (approximately) low rank. How can you use this knowledge to complete the missing entries? In this talk, I will present a novel yet surprisingly simple method to solve the problem. Our method is shown to recover the matrix in the challenging settings of very few observations and/or ill-conditioning, where many popular methods fail. We also prove strong theoretical guarantees for our method, some of which improve upon the state of the art. Finally, I will discuss how one can complete a matrix by incorporating extra knowledge beyond its observed entries, a problem known as inductive matrix completion. The talk is based on two joint papers with Boaz Nadler, published in SIMODS and ICML.