Spectral algorithms for tensor completion

2016/12/23 by Montanari, Andrea, Sun, Nike · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1612.07866

Abstract

In the tensor completion problem, one seeks to estimate a low-rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial-time algorithms. Among the latter, the best statistical guarantees have been proved, for third-order tensors, using the sixth level of the sum-of-squares (SOS) semidefinite programming hierarchy (Barak and Moitra, 2014). However, the SOS approach does not scale well to large problem instances. By contrast, spectral methods --- based on unfolding or matricizing the tensor --- are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new unfolding-based method, which outperforms naive ones for symmetric k-th order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third-order tensors, our algorithm matches the SOS method in terms of sample size (requiring about rd^3/2 revealed entries), subject to a worse rank condition (r≪ d^3/4 rather than r≪ d^3/2). We complement this result with a different spectral algorithm for third-order tensors in the overcomplete (r≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d≤ r ≪ d^3/2 from about rd^3/2 revealed entries.

Cited by

• Solving exact and noisy rank-one tensor completion with semidefinite programming
• Near-Efficient and Non-Asymptotic Multiway Inference
• Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks
• ACT-Tensor: Tensor Completion Framework for Financial Dataset Imputation

Related

• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries
• Tensor Completion Made Practical
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• Spectral gap-based deterministic tensor completion