ISRMT: Improved very sparse matrix completing using an intentionally randomized "asymmetric SVD"

Joint work with: Charles Bordenave (University Aix-Marseille)
Simon Coste (Université de Paris P7, LPSM)

We consider the matrix completion problem in the very sparse regime where, on average, a constant number of entries of the matrix are observed per row (or column). In this very sparse regime, we cannot expect to have perfect recovery and the celebrated nuclear norm based matrix completion fails because the singular value decomposition (SVD) of the underlying very sparse matrix completely breaks down.

We demonstrate that it is indeed possible to reliably recover the matrix. The key idea is the use of a ``randomized asymmetric SVD'' (which we will define) to find informative singular vectors in this regime in a way that the SVD cannot.

We provide sharp theoretical analysis of the phenomenon, including a prediction of the lower limits of statistical recovery and demonstrate the efficacy of the new method(s) using simulations.

A recording of the talk can be found at https://youtu.be/nlSmfwla6L4