  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.
