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 ⊗ᵢ₌₁N Rᵈ, 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 = Θ(1), we prove it uses no more than m = O(d² log d) samples and runs in O(md²) time. Moreover, we show any algorithm requires Ω(dlog d) samples. By contrast, existing upper bounds on the sample complexity are at least as large as d1.5 μΩ(1) logΩ(1) d, where μ can be Θ(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.