Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 13 of its 25 references that are in the map. First posted on arXiv 10 Aug 2024.
Builds on
13 of 25 references.
References · 13
- 2017Tensor Completion Algorithms in Big Data Analyticscited by 48
- 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
- 2014Provable Tensor Factorization with Missing Datacited by 31
- 2014Uniform Sampling for Matrix Approximationcited by 31
- 2013Incoherence-Optimal Matrix Completioncited by 27
- 2016Spectral algorithms for tensor completioncited by 27
- 2017On Polynomial Time Methods for Exact Low Rank Tensor Completioncited by 27
- 2013Low-Rank Matrix and Tensor Completion via Adaptive Samplingcited by 19
- 2020Tensor Completion Made Practicalcited by 15
- 2017Exact tensor completion with sum-of-squarescited by 14
- 2022Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systemscited by 4
- 2016The geometry of rank-one tensor completioncited by 1
1 more
- 2024The Rank-1 Completion Problem for Cubic Tensorscited by 1
Built on by
Not cited yet.