  We consider the setup of nonparametric {\em blind regression} for estimating
the entries of a large $m \times n$ matrix, when provided with a small, random
fraction of noisy measurements. We assume that all rows $u \in [m]$ and columns
$i \in [n]$ of the matrix are associated to latent features $x_{\text{row}}(u)$
and $x_{\text{col}}(i)$ respectively, and the $(u,i)$-th entry of the matrix,
$A(u, i)$ is equal to $f(x_{\text{row}}(u), x_{\text{col}}(i))$ for a latent
function $f$. Given noisy observations of a small, random subset of the matrix
entries, our goal is to estimate the unobserved entries of the matrix as well
as to "de-noise" the observed entries. As the main result of this work, we
introduce a nearest-neighbor-based estimation algorithm, and establish its
consistency when the underlying latent function $f$ is Lipschitz, the
underlying latent space is a bounded diameter Polish space, and the random
fraction of observed entries in the matrix is at least $\max \left( m^{-1 +
\delta}, n^{-1/2 + \delta} \right)$, for any $\delta > 0$. As an important
byproduct, our analysis sheds light into the performance of the classical
collaborative filtering algorithm for matrix completion, which has been widely
utilized in practice. Experiments with the MovieLens and Netflix datasets
suggest that our algorithm provides a principled improvement over basic
collaborative filtering and is competitive with matrix factorization methods.
Our algorithm has a natural extension to the setting of tensor completion via
flattening the tensor to matrix. When applied to the setting of image
in-painting, which is a $3$-order tensor, we find that our approach is
competitive with respect to state-of-art tensor completion algorithms across
benchmark images.
