The Probabilitas Seminar series focuses on high-dimensional problems that combine statistics, probability, artificial intelligence, information theory, computer science, and other related fields. The upcoming seminar takes place on Tuesday, December 2, at 1:30pm in Science Center 705. This week's speaker will be Raj Rao Nadakuditi, Associate Professor at University of Michigan's Department of Electrical Engineering and Computer Science, at Maxwell Dworkin G125, 3-4pm.
Improved very sparse matrix completion using an intentionally randomized 'asymmetric' SVD
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 to find informative singular vectors in this regime in a way that the SVD cannot. We provide sharp theoretical analysis of the phenomenon, the lower limits of statistical recovery and demonstrate the efficacy of the new method using simulations.