Nonnegative Tensor Completion via Integer Optimization. (arXiv:2111.04580v2 [cs.LG] UPDATED)

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 …

arxiv optimization tensor