Sample Complexity of Low-rank Tensor Recovery from Uniformly Random Entries

Abstract

We show that a generic tensor $T\in {\mathbb{F}}^{n\times n\times \cdots \times n}$ of order $k$ and CP rank $d$ can be uniquely recovered from $n\log n+dn\log \log n+o(n\log \log n)$ uniformly random entries with high probability if $d$ and $k$ are constant and $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. The bound is tight up to the coefficient of the second leading term and improves on the existing $O(n^{\frac{k}{2}}\mathrm{polylog}(n))$ upper bound for order $k$ tensors. The bound is obtained by showing that the projection of the Segre variety to a random axis-parallel linear subspace preserves $d$-identifiability with high probability if the dimension of the subspace is $n\log n+dn\log \log n+o(n\log \log n)$ and $n$ is sufficiently large.