Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
<|reference_start|>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 = \Theta(1)$, we prove it uses no more than $m = O(d^2 \log d)$ samples and runs in $O(md^2)$ time. Moreover, we show any algorithm requires $\Omega(d\log d)$ samples.   By contrast, existing upper bounds on the sample complexity are at least as large as $d^{1.5} \mu^{\Omega(1)} \log^{\Omega(1)} d$, where $\mu$ can be $\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.<|reference_end|>
@article{gomez-leos2024simple,
    title={Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via
  Gauss-Jordan},
    author={Alejandro Gomez-Leos, Oscar L'opez},
    journal={arXiv preprint arXiv:2408.05431},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.05431},
    primaryClass={cs.DS cs.LG math.ST stat.ML stat.TH}
}