mlsanityData to 7 Oct 2026

Nonnegative Tensor Completion via Integer Optimization

arXiv 2111.04580 ↗First posted 8 Nov 2021cs.LG math.OC stat.MLcited by 4

Not on the map. Why?

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.

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

Builds on

8 of 40 references.

References · 8

  1. 2017Tensor Completion Algorithms in Big Data Analyticscited by 48
  2. 2013Square Deal: Lower Bounds and Improved Relaxations for Tensor Recoverycited by 37
  3. 2014On Tensor Completion via Nuclear Norm Minimizationcited by 32
  4. 2016Spectral algorithms for tensor completioncited by 27
  5. 2016Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completioncited by 10
  6. 2014Forward - Backward Greedy Algorithms for Atomic Norm Regularizationcited by 9
  7. 2014Low-Rank Approximation and Completion of Positive Tensorscited by 4
  8. 2016The Computational Complexity of Dualitycited by 3

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 1; 2024: 1.

4 papers.

  1. 2022Zero-Truncated Poisson Regression for Sparse Multiway Count Data Corrupted by False Zeroscited by 3
  2. 2022Accelerated Nonnegative Tensor Completion via Integer Programmingcited by 1
  3. 2023A generalizable framework for low-rank tensor completion with numerical priorscited by 1
  4. 2024Tensor Completion via Integer Optimizationcited by 0