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

arXiv: https://arxiv.org/abs/2408.05431 · HTML: https://mlsanity.com/paper/2408.05431/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 10 Aug 2024.

## Builds on (most cited first, 13 of 13)

- [Tensor Completion Algorithms in Big Data Analytics](https://mlsanity.com/paper/1711.10105/) (2017)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017)
- [Low-Rank Matrix and Tensor Completion via Adaptive Sampling](https://mlsanity.com/paper/1304.4672/) (2013)
- [Tensor Completion Made Practical](https://mlsanity.com/paper/2006.03134/) (2020)
- [Exact tensor completion with sum-of-squares](https://mlsanity.com/paper/1702.06237/) (2017)
- [Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems](https://mlsanity.com/paper/2204.01815/) (2022)
- [The geometry of rank-one tensor completion](https://mlsanity.com/paper/1605.01678/) (2016)
- [The Rank-1 Completion Problem for Cubic Tensors](https://mlsanity.com/paper/2404.08171/) (2024)

## Abstract (arXiv)

We revisit the sample and computational complexity of completing a rank-1 tensor in otimesi=1N ℝ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(d2 log d) samples and runs in O(md2) time. Moreover, we show any algorithm requires Omega(dlog d) samples. By contrast, existing upper bounds on the sample complexity are at least as large as d1.5 μOmega(1) logOmega(1) d, where μ 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.