  CUR matrix decomposition computes the low rank approximation of a given
matrix by using the actual rows and columns of the matrix. It has been a very
useful tool for handling large matrices. One limitation with the existing
algorithms for CUR matrix decomposition is that they need an access to the {\it
full} matrix, a requirement that can be difficult to fulfill in many real world
applications. In this work, we alleviate this limitation by developing a CUR
decomposition algorithm for partially observed matrices. In particular, the
proposed algorithm computes the low rank approximation of the target matrix
based on (i) the randomly sampled rows and columns, and (ii) a subset of
observed entries that are randomly sampled from the matrix. Our analysis shows
the relative error bound, measured by spectral norm, for the proposed algorithm
when the target matrix is of full rank. We also show that only $O(n r\ln r)$
observed entries are needed by the proposed algorithm to perfectly recover a
rank $r$ matrix of size $n\times n$, which improves the sample complexity of
the existing algorithms for matrix completion. Empirical studies on both
synthetic and real-world datasets verify our theoretical claims and demonstrate
the effectiveness of the proposed algorithm.
