Deformed Decomposition for Non-negative Tensors

Abstract

Non-negative tensor factorization finds widespread use in numerous applications, however, its global optimization has been a long-standing challenge. In particular, the Frobenius norm minimization, even in the rank-1 setting, is an NP-hard problem. We presently reformulate tensor decompositions using deformed algebra, which is associated with a generalized product such that the exponential law holds for generalized exponential functions, 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. Through experiments on tensor-based probability mass function estimation, we show that the deformed decompositions provide implicit regularization and robustness against noise and mislabeled 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.