# Deterministic tensor completion with hypergraph expanders

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2019.

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

- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [When big data actually are low-rank, or entrywise approximation of certain function-generated matrices](https://mlsanity.com/paper/2407.03250/) (2024)
- [Guaranteed Multidimensional Time Series Prediction via Deterministic Tensor Completion Theory](https://mlsanity.com/paper/2501.15388/) (2025)
- [Spectral gap-based deterministic tensor completion](https://mlsanity.com/paper/2306.06262/) (2023)
- [Sharp spectral norm concentration of sparse random tensors](https://mlsanity.com/paper/2609.20520/) (2026)

## Abstract (arXiv)

We provide a novel analysis of low-rank tensor completion based on hypergraph expanders. As a proxy for rank, we minimize the max-quasinorm of the tensor, which generalizes the max-norm for matrices. Our analysis is deterministic and shows that the number of samples required to approximately recover an order-t tensor with at most n entries per dimension is linear in n, under the assumption that the rank and order of the tensor are O(1). As steps in our proof, we find a new expander mixing lemma for a t-partite, t-uniform regular hypergraph model, and prove several new properties about tensor max-quasinorm. To the best of our knowledge, this is the first deterministic analysis of tensor completion. We develop a practical algorithm that solves a relaxed version of the max-quasinorm minimization problem, and we demonstrate its efficacy with numerical experiments.