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.