  The problem of low-rank matrix completion has recently generated a lot of
interest leading to several results that offer exact solutions to the problem.
However, in order to do so, these methods make assumptions that can be quite
restrictive in practice. More specifically, the methods assume that: a) the
observed indices are sampled uniformly at random, and b) for every new matrix,
the observed indices are sampled afresh. In this work, we address these issues
by providing a universal recovery guarantee for matrix completion that works
for a variety of sampling schemes. In particular, we show that if the set of
sampled indices come from the edges of a bipartite graph with large spectral
gap (i.e. gap between the first and the second singular value), then the
nuclear norm minimization based method exactly recovers all low-rank matrices
that satisfy certain incoherence properties. Moreover, we also show that under
certain stricter incoherence conditions, $O(nr^2)$ uniformly sampled entries
are enough to recover any rank-$r$ $n\times n$ matrix, in contrast to the
$O(nr\log n)$ sample complexity required by other matrix completion algorithms
as well as existing analyses of the nuclear norm method.
