Matrix Completion from $O(n)$ Samples in Linear Time
  We consider the problem of reconstructing a rank-$k$ $n \times n$ matrix $M$
from a sampling of its entries. Under a certain incoherence assumption on $M$
and for the case when both the rank and the condition number of $M$ are
bounded, it was shown in \cite{CandesRecht2009, CandesTao2010, keshavan2010,
Recht2011, Jain2012, Hardt2014} that $M$ can be recovered exactly or
approximately (depending on some trade-off between accuracy and computational
complexity) using $O(n \, \text{poly}(\log n))$ samples in super-linear time
$O(n^{a} \, \text{poly}(\log n))$ for some constant $a \geq 1$.
  In this paper, we propose a new matrix completion algorithm using a novel
sampling scheme based on a union of independent sparse random regular bipartite
graphs. We show that under the same conditions w.h.p. our algorithm recovers an
$\epsilon$-approximation of $M$ in terms of the Frobenius norm using $O(n
\log^2(1/\epsilon))$ samples and in linear time $O(n \log^2(1/\epsilon))$. This
provides the best known bounds both on the sample complexity and computational
complexity for reconstructing (approximately) an unknown low-rank matrix.
  The novelty of our algorithm is two new steps of thresholding singular values
and rescaling singular vectors in the application of the "vanilla" alternating
minimization algorithm. The structure of sparse random regular graphs is used
heavily for controlling the impact of these regularization steps.
