# Accelerated Nonnegative Tensor Completion via Integer Programming

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 28 Nov 2022.

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

- [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)
- [FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients](https://mlsanity.com/paper/2104.06675/) (2021)
- [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)
- [Sparser Kernel Herding with Pairwise Conditional Gradients without Swap Steps](https://mlsanity.com/paper/2110.12650/) (2021)

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

- [Tensor Completion via Integer Optimization](https://mlsanity.com/paper/2402.05141/) (2024)

## Abstract (arXiv)

The problem of tensor completion has applications in healthcare, computer vision, and other domains. However, past approaches to tensor completion have faced a tension in that they either have polynomial-time computation but require exponentially more samples than the information-theoretic rate, or they use fewer samples but require solving NP-hard problems for which there are no known practical algorithms. A recent approach, based on integer programming, resolves this tension for nonnegative tensor completion. It achieves the information-theoretic sample complexity rate and deploys the Blended Conditional Gradients algorithm, which requires a linear (in numerical tolerance) number of oracle steps to converge to the global optimum. The tradeoff in this approach is that, in the worst case, the oracle step requires solving an integer linear program. Despite this theoretical limitation, numerical experiments show that this algorithm can, on certain instances, scale up to 100 million entries while running on a personal computer. The goal of this paper is to further enhance this algorithm, with the intention to expand both the breadth and scale of instances that can be solved. We explore several variants that can maintain the same theoretical guarantees as the algorithm, but offer potentially faster computation. We consider different data structures, acceleration of gradient descent steps, and the use of the Blended Pairwise Conditional Gradients algorithm. We describe the original approach and these variants, and conduct numerical experiments in order to explore various tradeoffs in these algorithmic design choices.