Nonnegative Tensor Completion via Integer Optimization
This addresses a fundamental gap in tensor completion theory for nonnegative tensors, with potential applications in domains like recommendation systems or image processing, though it is incremental as it focuses on a special case.
The paper tackles the problem of tensor completion for nonnegative tensors, which lacks algorithms achieving the information-theoretic sample complexity rate, and develops a new algorithm that provably converges linearly while achieving this rate, demonstrated on tensors with up to 100 million entries.
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.