Deformed Decomposition for Non-negative Tensors

Non-negative tensor factorization finds widespread use in numerous applications, however, its global optimization has been a long-standing challenge. As such, the Frobenius norm minimization even in the rank-1 setting is an NP-hard problem. We presently reformulate tensor decompositions using deformed algebra, and show that the best rank-1 approximation thereby reduces to a convex optimization problem for the rich χ-divergence family. Building on this foundation, we propose the deformed many-body approximation for non-negative tensors, which expands model capacity while maintaining global optimality by preserving the flatness of the model manifold. Introducing latent variables, for a subclass of χ-divergences, we further develop an Expectation-Maximization-based framework for the deformed extension of traditional low-rank approximations as iterative convex subproblems. We empirically demonstrate in tensor-based discrete density estimation that the deformed decompositions induce regularization and robustness against noise and mislabelled data. Beyond ordinary tensor algebra, our findings provide a factorization framework that enables us to leverage various divergences with convex rank-1 and many-body approximations.