Spectral Algorithms for Tensor Completion

• Published in: Communications on pure and applied mathematics 2018-11, Vol.71 (11), p.2381-2425
• Main Authors: Montanari, Andrea, Sun, Nike
• Format: Article
• Language: English
• ISSN: 0010-3640; 1097-0312
• DOI: 10.1002/cpa.21748

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. 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 method, based on unfolding, which outperforms naive ones for symmetric kth‐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 rd3/2 revealed entries), subject to a worse rank condition (r ≪ d3/4 rather than r ≪ d3/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 ≪ d3/2 from about rd3/2 revealed entries. © 2018 Wiley Periodicals, Inc.