On Polynomial Time Methods for Exact Low Rank Tensor Completion
This provides an efficient and practical method for tensor completion without imposing extra structures, addressing a computational bottleneck in data analysis.
The paper tackles the problem of exact low-rank tensor completion from a subset of entries, showing that a gradient descent algorithm with spectral initialization can reconstruct a d×d×d tensor with ranks (r,r,r) from O(r^{7/2}d^{3/2}log^{7/2}d + r^7d log^6d) entries with high probability.
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^7d\log^6d)$ 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.