New method certifies exact parts in nonnegative tensor decompositions
Structure and Exact Certification of Nonnegative Tensor Decompositions
Data Structures and AlgorithmsComputational Complexity
Summary
Tensors are like multi-dimensional tables of numbers, and breaking them into simpler parts helps understand complex data. The authors study ways to check if such, so-called, nonnegative decompositions are the simplest and unique. They create a method that can exactly determine the smallest number of parts needed and verify if the solution is unique or not. This method works efficiently even for big tensors and can provide precise answers where previous approaches could not. They also tested their method on tricky examples and resolved cases that were unclear before.
What this means in practice
- •For machine learning engineers: Exact certification of tensor decompositions supports building interpretable models from multidimensional data with guaranteed minimal and unique factorization.
- •For signal processing teams: Enables precise verification of signal source decompositions when nonnegative constraints apply, improving reliability in blind source separation tasks.
Authors
Haoming Wang, Ming Yuan
Abstract
We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices. Every failure of minimality or essential uniqueness contains an irreducible positive exchange between $p$ supplied terms and $q$ competing terms. A dimension count based on the Lovitz--Petrov splitting theorem bounds the effective order of such an exchange, the sum over the modes of the joint factor-span dimension minus one, by $p+q-2$, and this bound is attained at every supplied length $R\ge2$. After eliminating ambient-row variables by the Farkas lemma, the resulting semialgebraic systems have fewer than $2R^2$ real variables. For input bit length $L$, this gives a deterministic $G(R)L^{O(R^2)}$-time algorithm that computes the nonnegative rank and an exact minimum-length decomposition, decides minimality and essential uniqueness, and returns exact witnesses when either property fails. The exponent is independent of the tensor order and the mode dimensions. For Lebesgue moment tensors, positive quadrature determines the nonnegative rank and the uniqueness behavior, and some rational length-$R$ inputs force a common field of degree at least $\lfloor R/2\rfloor!$ for any exact minimum-length output. As an illustration, an implementation resolves all 114 instances left inconclusive by earlier positive-scattering criteria, of which 95 are minimal and essentially unique and 19 are minimal but nonunique.