Structure and Exact Certification of Nonnegative Tensor Decompositions
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≥2. After eliminating ambient-row variables by the Farkas lemma, the resulting semialgebraic systems have fewer than 2R2 real variables. For input bit length L, this gives a deterministic G(R)LO(R2)-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 ⌊ R/2⌋! 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.
Related
- Identifiability of Nonnegative Tensor Decompositions via Positive Scattering
- Recursive Reasoning Exploration: Mathematical Research through Evolving Reasoning Graphs : case study: An Exact Certificate-Degree Theorem for Two-Term Tensor Decompositions : Phase III of the Math Instruments Program
- Singular value decompositions over ∗-algebras with applications to tensor decompositions
- Minkowski Decompositions for Generic Infinitesimal Newton-Okounkov Bodies of Arbitrary-Degree External Tensor Products on Products of Curves
- Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions
BibTeX
@misc{wang2026structure,
title = {{Structure and Exact Certification of Nonnegative Tensor Decompositions}},
author = {Haoming Wang and Ming Yuan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32787},
eprint = {2610.32787},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32787},
}
RIS
TY - UNPB
TI - Structure and Exact Certification of Nonnegative Tensor Decompositions
AU - Haoming Wang
AU - Ming Yuan
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32787
UR - https://arxiv.org/abs/2610.32787
AB - 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≥2. 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 ⌊ R/2⌋! 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.
ER -