# Tensor Completion with Nearly Linear Samples Given Weak Side Information

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 1 of 1)

- [Tensor Completion using Subspace Information](https://mlsanity.com/paper/2609.24501/) (2026)

## Abstract (arXiv)

Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only Theta(tn) degrees of freedom in a t-order tensor with nt entries, the best known polynomial time algorithm requires O(nt/2) samples in order to guarantee consistent estimation. In this paper, we show that weak side information is sufficient to reduce the sample complexity to O(n). The side information consists of a weight vector for each of the modes which is not orthogonal to any of the latent factors along that mode; this is significantly weaker than assuming noisy knowledge of the subspaces. We provide an algorithm that utilizes this side information to produce a consistent estimator with O(n1+kappa) samples for any small constant kappa > 0. We also provide experiments on both synthetic and real-world datasets that validate our theoretical insights.