CS Paper Radar

Structure and Exact Certification of Nonnegative Tensor Decompositions

Haoming Wang, Ming Yuan

cs.DS cs.CCmath.AGmath.COstat.ML ·submitted 2026-10-23 15:35 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Identifiability of Nonnegative Tensor Decompositions via Positive Scattering

cs.LG stat.MLmath.COmath.ST ·2026-09-10 ·Haoming Wang, Ming Yuan
theory similarity 0.76
Abstract

Identifiability of tensor decompositions is often established through linear-algebraic conditions on the factor families. For nonnegative decompositions, however, positivity provides additional information that is not captured by dimension and independence alone: nonnegative terms cannot cancel, and their supports constrain competing decompositions. We introduce a positive scattering term that quantifies this additional source of identifiability and combine it with the dimension budget underlying the Lovitz--Petrov generalization of Kruskal's theorem. For every subset of components, we obtain two sufficient conditions: a threshold of $2|S|-2$ guarantees minimality and nonnegative rank, while the stronger threshold $2|S|-1$ guarantees uniqueness among nonnegative decompositions of the same length. The key result is a positive splitting inequality for irreducible exchanges of nonnegative rank-one tensors, which combines the dimension constraint with support-induced geometric rigidity. Although the scattering term is defined through an optimization over intermediate factor spaces, we show that its mode costs are exactly $0$, $1$, or $+\infty$, yielding an exact activation characterization in terms of graph connectivity. The resulting criterion can strictly certify sparse nonnegative tensor decompositions beyond the reach of Kruskal and Lovitz--Petrov conditions, including examples for which those conditions fail even after reshaping. In the matrix case, the two criteria reduce respectively to full-rank factorization and two-sided separability.

0.36

Polynomial-time Tensor Decomposition under the Kruskal Condition and the Lovitz--Petrov Generalization

cs.DS math.CO ·2026-09-12 ·Shiri Sivan
similarity 0.67
Abstract

An identifiability criterion is a condition on a tensor decomposition that certifies uniqueness when the condition holds. Kruskal's classical condition is one of the best-known deterministic criteria for identifiability. However, no polynomial-time decomposition algorithm is known under the Kruskal condition; verifying the condition itself is NP-hard. Lovitz and Petrov introduced a strictly more general identifiability condition which, in contrast, is polynomial-time verifiable, but no polynomial-time decomposition algorithm was known under this condition either. In this paper we give a randomized polynomial-time algorithm, in the algebraic model over $\mathbb R$, for tensor decomposition under the Lovitz--Petrov condition, and therefore also under the stricter Kruskal condition. Moreover, combining our algorithm with polynomial-time verification of the Lovitz--Petrov condition yields an efficient end-to-end certification procedure: after computing a decomposition, one can deterministically certify in polynomial time that it is unique and therefore of minimum rank.

0.27

Certified local rank and uniqueness barriers for a 48-term matrix-multiplication decomposition

cs.SC cs.CC ·2026-09-11 ·Abhinav Agarwal
theoryhot direction similarity 0.62
Abstract

We study replacements in fixed bilinear tensor decompositions, counting changes to complete rank-one summands, including output factors. The shortening frontier records the maximum rank defect of a fixed-size subset and determines the minimum length attainable within a change budget. For the rational 48-term Li--Wang--Hu decomposition \(D(2)\) of \(4\times4\) matrix multiplication over \(\mathbb{C}\), we prove rank radius at least 12, strong radius exactly 11, and border radius at least 8. Every shorter complex decomposition therefore changes at least thirteen original summands. An exact rational twelve-term replacement attains the equal-length barrier. The proofs combine exhaustive support reductions with saturated projected kernels and zero-corner completion arguments controlling arbitrary minimal competitors. A reduced-incidence argument transfers kernel certificates to tensor-space neighborhoods. A Laurent normal form gives strong radius exactly 11 for the sixteen-term core at every nonzero complex parameter. On a nonempty Zariski-open subset of the actual parameter curve, the rank radius is at least 12, the strong radius exactly 11, and the border radius at least 8. We also prove incomparability of the full Kothari--Moitra--Wein sufficient criterion and the Sylvester-equipped kernel criterion. These results describe local decomposition structure rather than a new rank bound for full matrix multiplication.

0.25

Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization

cs.CC math.OC ·2026-10-15 ·Arnaud Vandaele
theory similarity 0.60
Abstract

Nonnegative matrix factorization (NMF) approximates a nonnegative matrix by the product of two nonnegative matrices with a prescribed inner dimension~$r$. The existence of an exact NMF can be decided in polynomial time for every fixed~$r$, and a best rank-$1$ NMF in the Frobenius norm can be obtained from a truncated singular value decomposition. We prove that computing a best rank-$2$ NMF in the Frobenius norm is strongly NP-hard. Our proof uses a polynomial-time reduction from \textsc{Clique} that produces symmetric positive-definite, completely positive matrices with polynomially bounded integer entries. The same reduction also establishes strong NP-hardness of rank-$2$ symmetric NMF.

0.16

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy

cs.CC ·2026-11-06 ·Mrinalkanti Ghosh
theory similarity 0.59
Abstract

Semidefinite programming (SDP), particularly the sum-of-squares (SoS) hierarchy, provides $n^{O(q)}$-time approximation and certification algorithms for optimizing degree-$d$ homogeneous polynomials on the unit sphere. For arbitrary inputs, degree-$q$ SoS gives a powered-objective approximation factor $O_d((n/q)^{d/2-1})$ [BGGLT17]. For random order-$d$ tensors, degree-$d$ SoS has an integrality-gap lower bound of $2^{-O(d)}(n/d)^{d/4-1/2}$ relative to the true spherical maximum; lower bounds also extend to growing SoS degree in tensor PCA [BGL17,HKP17]. We establish lower bounds for weaker linear-programming relaxation hierarchies. Our degree-$q$ moment LPs impose the sphere identities and any prescribed, instance-independent family $\mathcal{G}$ of valid polynomial inequalities of degree at most $q$. They include Sherali--Adams-type product hierarchies. For every even $d\ge2$, constant $C>0$, and $q$ satisfying $2d | q$ and $2d\le q\le n$, every such relaxation with at most $n^{Cq}$ tests has instances $P$ satisfying \[ \frac{\mathrm{PowLP}_{q,\mathcal{G}}(P)}{\|P\|_\infty}\ge \frac{c_{d,C}}{\sqrt{q\log n}}\left(\frac nq\right)^{d/2-1/2}.\] Here $\|P\|_\infty$ is the maximum absolute value of the polynomial over the sphere and $\mathrm{PowLP}_{q,\mathcal{G}}(P)$ is the relaxed objective. The exponent $d/2-1/2$ improves the leading dependence on $d$ relative to the $d/4$-type exponents in prior random-tensor SoS lower bounds. Our LP hierarchies impose weaker positivity conditions than semidefinite moment relaxations. It leaves open whether analogous degree dependence can be achieved in lower bounds for SDP hierarchies.

0.25

Equivalence of Fixed-Rank and Rank-One Even-Order Symmetric Tensor Factorization

cs.IT math-phmath.ST ·2026-09-07 ·Ruba Hussen Morsi, Anas A. Rahman
similarity 0.59
Abstract · 10 pages

In the recent work of Barbier, Ko, and the second present author on sublinear-rank symmetric matrix factorization [Math. Stat. Learn. 9 (2026), 1-68], a key result is that, in the Bayes-optimal setting, the large-size limit of the free entropy of the finite-rank spiked Wigner model is the same as in the rank-one case when the signal has centered i.i.d. entries. In this paper, we show that this rank-one equivalence result extends to the case of finite-rank, even-order, symmetric tensor factorization. Moreover, we give a natural reformulation of a hypothesis that was stated in the aforementioned work to be necessary for this result. As in the matrix case, we use information-theoretic identities and replica symmetry to reduce a known multi-dimensional variational formula for the limiting free entropy to its one-dimensional analog. The novelty stems from the fact that said formula involves a replica symmetric potential containing Hadamard (entrywise) powers, rather than squares, of the matrix-valued variational parameter, so the eigenvalue-based approach used in the matrix case must be adjusted.

0.31

Disjoint and nearly disjoint sums of matrix multiplication tensors and their centroids

cs.CC math.AGmath.ACmath.RA ·2026-08-27 ·Martin Kassabov, J. M. Landsberg, Victor Souza, Philip Speegle
theory similarity 0.58
Abstract · 52 pages, 3 figures

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

0.46

Concise tensors with maximal symmetries

cs.CC math.AGmath.GR ·2026-09-15 ·Annika Holtrup, Jeroen Zuiddam
theory similarity 0.58
Abstract

Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise $n\times n \times n$ tensors that are binding, and they determined the corresponding maximizing tensors to be the null algebra tensors. They left as an open problem to extend this to all concise $n \times n \times n$ tensors (i.e. dropping binding). We solve this problem: We prove that the largest stabilizer dimension of concise $n\times n\times n$ tensors is $n^2 + 1$ and the maximizers are the null algebra tensors (as in the binding case) and the skew symmetric tensor $e_1 \wedge e_2 \wedge e_3$. As part of our approach we obtain upper bounds on the stabilizer dimension of matrix tuples under left-right action (generalized Kronecker quiver representations), which we think are of independent interest.

0.27