On Polynomial Time Methods for Exact Low Rank Tensor Completion

Abstract

In this paper, we investigate the sample size requirement for exact recovery of a high order tensor of low rank from a subset of its entries. We show that a gradient descent algorithm with initial value obtained from a spectral method can, in particular, reconstruct a $d\times d\times d$ tensor of multilinear ranks $(r,r,r)$ with high probability from as few as $O(r^{7/2}{d}^{3/2}{\log }^{7/2}d+r^{7}d{\log }^{6}d)$ entries. In the case when the ranks $r=O(1)$, our sample size requirement matches those for nuclear norm minimization (Yuan and Zhang, 2016a), or alternating least squares assuming orthogonal decomposability (Jain and Oh, 2014). Unlike these earlier approaches, however, our method is efficient to compute, easy to implement, and does not impose extra structures on the tensor. Numerical results are presented to further demonstrate the merits of the proposed approach.

56 pages, 4 figures

References in corpus (5)

• A Simpler Approach to Matrix Completion
• Estimation of low-rank tensors via convex optimization
• Matrix Completion from a Few Entries
• Spectral algorithms for tensor completion
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion

Cited by in corpus (7)

• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Tensor Completion Algorithms in Big Data Analytics
• Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Partially Observed Dynamic Tensor Response Regression
• Implicit Regularization in Tensor Factorization
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering