An Ideal-Sparse Generalized Moment Problem Reformulation for Completely Positive Tensor Decomposition Exploiting Maximal Cliques of Multi-hypergraphs

Abstract. In this paper, we present a novel framework for addressing the completely positive tensor decomposition problem with ideal-sparsity. First, we introduce a definition of maximal cliques of multi-hypergraphs associated with completely positive tensors. Furthermore, we propose a theoretically guaranteed algorithm to generate all such maximal cliques and establish a necessary condition for tensors to be completely positive. Second, we reformulate the completely positive tensor decomposition problem into an ideal-sparse generalized moment problem. This reformulation involves optimizing over several lower-dimensional measure variables supported on the maximal cliques of a multi-hypergraph, enabling a more efficient solution process. We apply moment-based relaxations to solve this reformulation. We prove not only the asymptotic convergence but also the finite convergence of this ideal-sparse moment hierarchy. Numerical results show that the ideal-sparse reformulation is faster to compute than the original dense formulation of completely positive tensor decomposition problems.