Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan

We revisit the sample and computational complexity of completing a rank-1 tensor in ${\otimes }_{i=1}^N{\mathbb{R}}^d$, given a uniformly sampled subset of its entries. We present a characterization of the problem (i.e. nonzero entries) which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems. For example, when $N=\mathrm{\Theta }(1)$, we prove it uses no more than $m=O(d^2\log d)$ samples and runs in $O(m{d}^2)$ time. Moreover, we show any algorithm requires $\mathrm{\Omega }(d\log d)$ samples. By contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5}{\mu }^{\mathrm{\Omega }(1)}{\log }^{\mathrm{\Omega }(1)}d$, where $\mu$ can be $\mathrm{\Theta }(d)$ in the worst case. Prior work obtained these looser guarantees in higher rank versions of our problem, and tend to involve more complicated algorithms.