Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model

Yihua Li, Devavrat Shah, Dogyoon Song, Christina Lee YuIEEE Trans. Information Theory 2020 · OpenReview

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_{row}(u)$ and $x_{col}(i)$ respectively, and the $(u, i)$-th entry of the matrix, $A(u, i)$ is equal to $f(x_{row}(u), x_{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 “denoise” 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(m^{-1+\delta}, n^{-1/2+\delta})$, 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.

Introduction

Matrix completion—the task of filling in missing entries in a large, noisy data table—is a cornerstone of modern recommendation systems. Traditionally, this problem is solved using matrix factorization, which assumes the matrix is "low-rank," meaning the data can be explained by a few linear factors.

However, many real-world datasets do not fit this linear low-rank mold. Collaborative Filtering (CF), a popular heuristic that finds "similar" users or items, often performs better in practice but has historically lacked strong theoretical guarantees in non-parametric settings. This paper bridges this gap by framing matrix completion as Blind Regression. In this framework, the matrix is viewed as the result of an unknown function $f$ acting on hidden (latent) features of rows and columns. Because these features are not directly observed, the task becomes a regression problem where the independent variables are unknown.

The Latent Variable Model

The authors model the matrix $A$ such that each entry is defined by: $$A(u, i) = f(x_{row}(u), x_{col}(i)) + \epsilon_{u,i}$$ where $x_{row}(u)$ and $x_{col}(i)$ are latent features in a hidden space, $f$ is a Lipschitz continuous function, and $\epsilon$ represents noise. This model is significantly more flexible than low-rank models, as it can capture complex, non-linear interactions that linear factorization methods might miss.

The Nearest-Neighbor Algorithm

The proposed solution is a User-User Fixed Radius Nearest Neighbor algorithm. The core logic follows three distinct steps:

  1. Similarity Estimation: For any two rows, the algorithm calculates their dissimilarity by comparing the squared distance between their entries. Crucially, this is only calculated for the columns where both rows have observed data.
  2. Neighbor Selection: For a target entry $(u, i)$, the algorithm identifies "reliable neighbors"—other rows $v$ that fall within a specific distance threshold $\eta$ of row $u$.
  3. Estimation: The missing value is estimated by averaging the observed values in column $i$ from those identified reliable neighbor rows.

While this mirrors standard collaborative filtering, the theoretical contribution lies in proving that the empirical distance between rows in the observed data effectively approximates the functional distance in the hidden latent space.

Theoretical Consistency

A key insight of the paper is the establishment of consistency guarantees. The authors prove that the estimator is consistent (mean-squared error approaches zero) as the matrix size grows, provided the fraction of observed entries $p$ satisfies $p \ge \max(m^{-1+\delta}, n^{-1/2+\delta})$.

The threshold $\eta$ serves as a critical tuning parameter representing the bias-variance tradeoff. A large $\eta$ includes more neighbors (lowering variance) but risks including dissimilar rows (increasing bias). The paper provides a mathematical framework for selecting $\eta$ to balance these factors perfectly.

Experimental Results

Matrix Completion

The algorithm was evaluated on the MovieLens 1M and Netflix Prize datasets. In these benchmarks, the proposed nearest-neighbor approach systematically outperformed classical user-user and item-item collaborative filtering. Furthermore, it remained competitive with SoftImpute, a state-of-the-art matrix factorization method, despite the simplicity of the neighbor-averaging approach.

Tensor Completion and Image In-painting

The algorithm extends naturally to higher-order tensors by "flattening" them into matrices. The authors tested this on image in-painting tasks using benchmark images (Lenna, Pepper, and Facade) treated as 3rd-order tensors (Rows $\times$ Columns $\times$ RGB). Even when 70% of pixels were removed, the algorithm was competitive with complex Bayesian and spectral tensor factorization methods like FaLRTC and FBCP.

Limitations and Future Directions

Despite its theoretical and empirical strengths, the algorithm has limitations:

  • Overlap Requirement: The similarity metric relies on rows having overlapping observed entries. In extremely sparse datasets, the algorithm may struggle to find enough neighbors. The authors suggest "extended neighborhoods" (comparing neighbors of neighbors) as a potential solution.
  • Computational Complexity: Calculating similarities for all pairs of rows scales at $O(m^2 np)$. While highly parallelizable, scaling to industrial-sized datasets would require integration with approximate nearest neighbor (ANN) techniques.
  • Latent Space Geometry: The current proof assumes a bounded diameter Polish space. Future research could explore how the algorithm performs when latent spaces have specific structures, such as manifolds or hierarchical trees.

Summary updated

Abstract

We consider the setup of nonparametric blind regression for estimating the entries of a large m × n matrix, when provided with a small, random fraction of noisy measurements. We assume that all rows u ∈ [m] and columns i ∈ [n] of the matrix are associated to latent features xrow(u) and xcol(i) respectively, and the (u, i)-th entry of the matrix, A(u, i) is equal to f(x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">row</sub> (u), x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">col</sub> (i)) for a latent functionf. 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 “denoise” 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 (m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1+δ</sup> , n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1/2+δ</sup> ), for any δ > 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.
BibTeX
@article{li2020nearest,
  author = {Yihua Li and Devavrat Shah and Dogyoon Song and Christina Lee Yu},
  title = {{Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  url = {https://openreview.net/forum?id=IaAlGG4cRo},
}
Figure