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

Raj Rao Nadakuditi

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.

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.

Building: | East Hall |
---|---|

Event Type: | Workshop / Seminar |

Tags: | Mathematics, seminar |

Source: | Happening @ Michigan from Integrable Systems and Random Matrix Theory Seminar - Department of Mathematics, Department of Mathematics |