Title: Blind Regression via Nearest Neighbors under Latent Variable Models,
Abstract: We consider the setup of nonparametric '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_1(u)$ and
$x_2(i)$ respectively, and the $(u,i)$-th entry of the matrix, $A(u, i)$ is
equal to $f(x_1(u), x_2(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 neighbor-based estimation
algorithm inspired by the classical Taylor's series expansion. We establish its
consistency when the underlying latent function $f$ is Lipschitz, the latent
features belong to a compact domain, and the 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 (CF) 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 CF and is competitive with matrix
factorization methods.
Our algorithm has a natural extension to tensor completion. For a $t$-order
balanced tensor with total of $N$ entries, we prove that our approach provides
a consistent estimator when at least $N^{-\frac{\lfloor 2t/3 \rfloor}{2t}+
\delta}$ fraction of entries are observed, for any $\delta > 0$. When applied
to the setting of image in-painting (a tensor of order 3), we find that our
approach is competitive with respect to state-of-art tensor completion
algorithms across benchmark images.