  In this paper, we consider matrix completion from non-uniformly sampled
entries including fully observed and partially observed columns. Specifically,
we assume that a small number of columns are randomly selected and fully
observed, and each remaining column is partially observed with uniform
sampling. To recover the unknown matrix, we first recover its column space from
the fully observed columns. Then, for each partially observed column, we
recover it by finding a vector which lies in the recovered column space and
consists of the observed entries. When the unknown $m\times n$ matrix is
low-rank, we show that our algorithm can exactly recover it from merely
$\Omega(rn\ln n)$ entries, where $r$ is the rank of the matrix. Furthermore,
for a noisy low-rank matrix, our algorithm computes a low-rank approximation of
the unknown matrix and enjoys an additive error bound measured by Frobenius
norm. Experimental results on synthetic datasets verify our theoretical claims
and demonstrate the effectiveness of our proposed algorithm.
