# Nonnegative Tensor Completion via Integer Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 40 references that are in the map.
- First posted on arXiv 8 Nov 2021.

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

- [Tensor Completion Algorithms in Big Data Analytics](https://mlsanity.com/paper/1711.10105/) (2017)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion](https://mlsanity.com/paper/1606.03504/) (2016)
- [Forward - Backward Greedy Algorithms for Atomic Norm Regularization](https://mlsanity.com/paper/1404.5692/) (2014)
- [Low-Rank Approximation and Completion of Positive Tensors](https://mlsanity.com/paper/1412.0620/) (2014)
- [The Computational Complexity of Duality](https://mlsanity.com/paper/1601.07629/) (2016)

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

- [Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeros](https://mlsanity.com/paper/2201.10014/) (2022)
- [Accelerated Nonnegative Tensor Completion via Integer Programming](https://mlsanity.com/paper/2211.15770/) (2022)
- [A generalizable framework for low-rank tensor completion with numerical priors](https://mlsanity.com/paper/2302.05881/) (2023)
- [Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2402.05141/) (2024)

## Abstract (arXiv)

Unlike matrix completion, tensor completion does not have an algorithm that is known to achieve the information-theoretic sample complexity rate. This paper develops a new algorithm for the special case of completion for nonnegative tensors. We prove that our algorithm converges in a linear (in numerical tolerance) number of oracle steps, while achieving the information-theoretic rate. Our approach is to define a new norm for nonnegative tensors using the gauge of a particular 0-1 polytope; integer linear programming can, in turn, be used to solve linear separation problems over this polytope. We combine this insight with a variant of the Frank-Wolfe algorithm to construct our numerical algorithm, and we demonstrate its effectiveness and scalability through computational experiments using a laptop on tensors with up to one-hundred million entries.