CS Paper Radar

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

Ruba Hussen Morsi, Anas A. Rahman

cs.IT math-phmath.ST ·submitted 2026-09-07 03:10 UTC · v1

Abstract

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.

Comment
10 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A Random Matrix Analysis of Symmetric Tensor Unfolding

cs.LG stat.MLmath.PR ·2026-11-03 ·Tom Szwagier, Xiaoyi Mai, José Henrique de Morais Goulart
similarity 0.64
Abstract

We study a fundamental problem in machine learning: partial recovery of a planted signal $\boldsymbol{v} \in \mathbb{S}^{n-1}$ from a spiked tensor $\boldsymbol{\mathsf{X}} = λ\, \boldsymbol{v}^{\otimes p} + \boldsymbol{\mathsf{Z}}$, where $\boldsymbol{\mathsf{Z}}$ has symmetric Gaussian entries of variance $\asymp n^{-1}$. While previous works replace $\boldsymbol{\mathsf{Z}}$ by an i.i.d. standard Gaussian tensor to circumvent technical difficulties caused by dependencies, this paper directly analyzes the symmetric model via random matrix theory. We show that the square unfolding algorithm is subject to a sharp phase transition for partial recovery at $λ\asymp n^{(p-2) / 4}$, validating an open conjecture from Montanari and Richard (2014). We get precise expressions for the limiting spectral distribution, deterministic equivalent, phase transition threshold and overlap. The main message is that unfolded symmetric tensors spectrally behave like standard Wigner matrices, up to simple transformations accounting for high-order symmetries. We consider extensions to multiple orthogonal spikes, recursive unfolding and non-square unfolding via disproportionate random matrix theory, leading to an interesting conjectured statistical-computational tradeoff regarding the choice of unfolding: square versus long.

0.20

A Complete Characterization of Tensorizable $f$-divergences

cs.IT math.PRmath.ST ·2026-08-28 ·Rodrigo Cruz, Flavio P. Calmon, Qian Yu
similarity 0.61
Abstract

Csiszar's formulation of the $f$-divergence introduced a vast family of functionals for quantifying dissimilarity between probability distributions. However, many applications in statistics and information theory rely only on a few $f$-divergences, such as the Kullback-Leibler divergence, the $χ^2$-divergence, and the squared Hellinger distance. These divergences are especially useful because they admit simple compositional formulas under product measures, a property sometimes referred to as tensorization. In this work, we refine a formalism of tensorization previously introduced in the literature. Then, we show that any possible tensorization formula has a multi-affine form characterized by a single parameter, and identify all tensorizable $f$-divergences under our adopted notion of tensorization.

0.45

Identifiability of Nonnegative Tensor Decompositions via Positive Scattering

cs.LG stat.MLmath.COmath.ST ·2026-09-10 ·Haoming Wang, Ming Yuan
theory similarity 0.60
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

Structure and Exact Certification of Nonnegative Tensor Decompositions

cs.DS cs.CCmath.AGmath.CO+1 ·2026-10-23 ·Haoming Wang, Ming Yuan
theory similarity 0.59
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.

0.12

Robust low-rank tensor completion via factorized weighted tensor schatten-p norm minimization

cs.CV math.OC ·2026-09-13 ·Binghao Wang, Feng Zhang, Wendong Wang, Jianjun Wang
hot direction similarity 0.59
Abstract

Low-rank tensor factorization provides a flexible framework for completing multidimensional data from incomplete and corrupted observations. However, unweighted spectral regularizers impose a common shrinkage profile across singular components, which may excessively attenuate dominant low-rank components, and factorized variants either lack component-specific weighting or require costly singular value decompositions (SVDs). This paper proposes two weighted Schatten-$p$ tensor factorization models, termed \WSpTFI{} and \WSpTFII{}, under the tensor-tensor product (t-product) framework to address these limitations. \WSpTFI{} is motivated by a factorized weighted tensor Schatten-$p$ norm identity and permits flexible, possibly asymmetric factor exponents. \WSpTFII{} constructs a regularizer from transform-domain column-pair energies, yielding SVD-free main factor updates and a column-pruning mechanism for reducing redundant rank components. This paper further develops an iteratively reweighted alternating direction method of multipliers (ADMM)-type scheme for \WSpTFI{} and an iteratively reweighted least squares (IRLS)--block successive upper-bound minimization (BSUM) scheme for \WSpTFII{}. Theoretical analysis establishes the weighted factorization relation and provides a conditional limiting Karush--Kuhn--Tucker (KKT) characterization for \WSpTFI{}. For \WSpTFII{}, the actual damped quadratic block updates yield a quantitative sufficient-decrease mechanism for the fixed-$δ$ smoothed factor objective. This implies asymptotic regularity, and every accumulation point of the fixed-dimensional tail is stationary. Experiments on synthetic tensor completion, color-image restoration, hyperspectral inpainting, and printed-circuit-board defect detection demonstrate competitive reconstruction quality and robustness under various degradation conditions.

0.26

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.57
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

RDT based upper bounds on the largest average submatrix values

cs.IT math.PRcond-mat.stat-mechmath.ST ·2026-09-16 ·Mihailo Stojnic
theory similarity 0.57
Abstract

We study statistical variants of the classical largest average submatrix problem. For small submatrices (where the dimension is less than linearly proportional to the original matrix), the problem is typically well understood and believed to exhibit the statistical-computational gap (SCG). However, analytical treatment of both the information-theoretic and algorithmic aspects of the linear regime remains challenging, and no mathematically rigorous results have yet arrived anywhere close to proving or disproving SCG existence in this setting. Focusing on the linear regime, we make strong progress in several key directions: 1) We develop a generic Random Duality Theory (RDT) framework to characterize largest average submatrix values. 2) Using the plain RDT variant, we obtain closed-form upper bounds as explicit functions of dimensionality proportionality parameters. 3) We demonstrate that a lifted RDT variant strictly improves upon the plain RDT within a certain linear range of submatrix dimensions. 4) For small submatrices where the dimensional proportionality constants approach zero, we prove that our results match both the replica results from [34] (obtained via one-step replica symmetry breaking) and the sublinear results from [18,45].

0.30

A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees

cs.DS ·2026-09-18 ·Tarun Kathuria
theory similarity 0.56
Abstract · The author explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for t…

Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_i A_i=I$ and $\norm{A_i}\le\varepsilon$. We prove that one sign can be assigned to each original matrix with discrepancy $O(\sqrt{\varepsilon\log(2r)})$, independently of their dimension and number, which is known to be optimal upto constants. We give a separate existence proof and a deterministic algorithm with polynomial work in a real-arithmetic model with semidefinite-value and exact spectral primitives. Separate Lean formalizations verify the existence proof and the algorithm in this arithmetic model. The proof extends the variational approach to discrepancy developed in the companion papers, motivated by operator-valued free interpolation, Lehner's formula, and spectral Tsallis regularization. A concave matrix power interpolates between a trace source and a sandwich source. Its concavity controls the response of the optimizing density. The walk maintains independent source reserves and a second matrix recording reserve expenditure. This matrix certifies contraction of the unfinished input mass between epochs; within an epoch, preparation and a negative-curvature step control the spectral potential while the coefficients advance toward signs. As applications, one spanning tree can be chosen simultaneously $O(\varepsilon\log(2s))$-spectrally thin for $s$ positive weightings of a common graph whose edge leverages are at most $\varepsilon$. The diagonal specialization gives discrepancy $O(\sqrt{L\log(2k)})$ for matrices with row sums at most $L$ and at most $k$ nonzero entries per column, through a walk of fractional colorings.

0.38