Iterative Collaborative Filtering for Sparse Noisy Tensor Estimation

摘要

We consider the task of tensor estimation, i.e. estimating a low-rank 3-order n × n × n tensor from noisy observations of randomly chosen entries in the sparse regime. In the context of matrix (2-order tensor) estimation, a variety of algorithms have been proposed and analyzed in the literature including the popular collaborative filtering algorithm that is extremely well utilized in practice. However, in the context of tensor estimation, there is limited progress. No natural extensions of collaborative filtering are known beyond "flattening" the tensor into a matrix and applying standard collaborative filtering.As the main contribution of this work, we introduce a generalization of the collaborative filtering algorithm for the setting of tensor estimation and argue that it achieves sample complexity that (nearly) matches the conjectured lower bound on the sample complexity. Interestingly, our generalization uses the matrix obtained from the "flattened" tensor to compute similarity as in the classical collaborative filtering but by defining a novel "graph" using it. The algorithm recovers the tensor with mean-squared-error (MSE) decaying to 0 as long as each entry is observed independently with probability p = Ω(n^−3/2+ϵ) for any arbitrarily small ϵ > 0. It turns out that p = Ω(n^−3/2) is the conjectured lower bound as well as "connectivity threshold" of graph considered to compute similarity in our algorithm.