# Spectral gap-based deterministic tensor completion

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 9 Jun 2023.

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

- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [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)
- [Universal Matrix Completion](https://mlsanity.com/paper/1402.2324/) (2014)
- [Poisson Matrix Recovery and Completion](https://mlsanity.com/paper/1504.05229/) (2015)
- [Near-optimal sample complexity for convex tensor completion](https://mlsanity.com/paper/1711.04965/) (2017)
- [Deterministic tensor completion with hypergraph expanders](https://mlsanity.com/paper/1910.10692/) (2019)
- [Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution](https://mlsanity.com/paper/1904.04283/) (2019)
- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)

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

- [Near-Efficient and Non-Asymptotic Multiway Inference](https://mlsanity.com/paper/2511.05368/) (2025)

## Abstract (arXiv)

Tensor completion is a core machine learning algorithm used in recommender systems and other domains with missing data. While the matrix case is well-understood, theoretical results for tensor problems are limited, particularly when the sampling patterns are deterministic. Here we bound the generalization error of the solutions of two tensor completion methods, Poisson loss and atomic norm minimization, providing tighter bounds in terms of the target tensor rank. If the ground-truth tensor is order t with CP-rank r, the dependence on r is improved from r2(t-1)(t2-t-1) in arXiv:1910.10692 to r2(t-1)(3t-5). The error in our bounds is deterministically controlled by the spectral gap of the sampling sparsity pattern. We also prove several new properties for the atomic tensor norm, reducing the rank dependence from r3t-3 in arXiv:1711.04965 to r3t-5 under random sampling schemes. A limitation is that atomic norm minimization, while theoretically interesting, leads to inefficient algorithms. However, numerical experiments illustrate the dependence of the reconstruction error on the spectral gap for the practical max-quasinorm, ridge penalty, and Poisson loss minimization algorithms. This view through the spectral gap is a promising window for further study of tensor algorithms.