# Tensor Completion via Integer Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 59 references that are in the map.
- First posted on arXiv 6 Feb 2024.

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

- [Tensor Completion Algorithms in Big Data Analytics](https://mlsanity.com/paper/1711.10105/) (2017)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [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)
- [Low Rank Regularization: A Review](https://mlsanity.com/paper/1808.04521/) (2018)
- [Forward - Backward Greedy Algorithms for Atomic Norm Regularization](https://mlsanity.com/paper/1404.5692/) (2014)
- [Rank regularization and Bayesian inference for tensor completion and extrapolation](https://mlsanity.com/paper/1301.7619/) (2013)
- [Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis](https://mlsanity.com/paper/1705.09844/) (2017)
- [Low-Rank Approximation and Completion of Positive Tensors](https://mlsanity.com/paper/1412.0620/) (2014)
- [Nonnegative Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2111.04580/) (2021)
- [The Computational Complexity of Duality](https://mlsanity.com/paper/1601.07629/) (2016)
- [Noisy Tensor Completion for Tensors with a Sparse Canonical Polyadic Factor](https://mlsanity.com/paper/1704.02534/) (2017)
- [Accelerated Nonnegative Tensor Completion via Integer Programming](https://mlsanity.com/paper/2211.15770/) (2022)

## Abstract (arXiv)

The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution, or have polynomial-time algorithms that require an exponentially-larger number of samples for low estimation error. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate. Our approach formulates tensor completion as a convex optimization problem constrained using a gauge-based tensor norm, which is defined in a way that allows the use of integer linear optimization to solve linear separation problems over the unit-ball in this new norm. Adaptations based on this insight are incorporated into a Frank-Wolfe variant to build our algorithm. We show our algorithm scales-well using numerical experiments on tensors with up to ten million entries.