CS Paper Radar

Singularities of Non-negative Matrix Factorization and their application to Bayesian inference

Naoki Hayashi, Yota Maeda, Yasushi Esaki

cs.LG stat.MLmath.ST ·submitted 2026-09-28 00:09 UTC · v1
theory

Abstract

Non-negative matrix factorization (NMF) is a singular statistical model whose Bayesian asymptotics are governed by the real log canonical threshold (RLCT). We study the local geometry of the factorization map and derive an upper bound for the RLCT of NMF. Let $H$ be the model inner dimension and $H_0$ the non-negative rank of the true $M\times N$ matrix. Assuming that the true matrix admits a strictly positive factorization of inner dimension $H_0$ in the interior of the parameter domain, we prove, for smooth positive priors, that $λ\leq \{(H-H_0)\min(M,N)+H_0(M+N-H_0)\}/2$. This bound strictly improves the previous bound when $H_0\geq3$. The proof uses a local analytic normal form that separates independent linear coordinates from a residual matrix product. When $H=H_0$ also equals the ordinary rank of the true matrix, we obtain the exact value $λ=H_0(M+N-H_0)/2$. Under the standard assumptions of singular learning theory, these results bound the leading coefficients of the expected Bayesian generalization error and the Bayesian free energy.

Comment
23 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Nuclear Norm-Regularized Bayesian Matrix Completion

cs.LG stat.ML ·2026-09-24 ·Calvin Tolbert
similarity 0.65
Abstract · 40 pages, 7 figures

Nuclear-norm-regularized least squares is a standard approach to matrix completion, but it yields only a point estimate. Its Bayesian counterpart, a prior combining the nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the matrix after a number of steps polynomial in the matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the matrix, and bounds the error this propagates to the posterior on the matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the polynomial complexity is not intended as a practical algorithm at current problem scales.

0.26

Singularity-Induced Local Complexity for High-Dimensional Learning Models

cs.LG ·2026-11-02 ·Atsuyoshi Muta, Masaaki Imaizumi
similarity 0.61
Abstract · 40pages

Many overparameterized models that have achieved remarkable success are singular models. That is, the set of optimal parameters consists of multiple points, or the Hessian of the generalization error at such parameters is degenerate, reflecting redundancy in the model parametrization. Therefore, understanding the effective dimension and intrinsic model complexity, beyond the apparent dimension of the parameter space, is essential for studying the generalization ability of such overparameterized models. In this work, we focus on the real log canonical threshold (RLCT) and its localized counterpart, the local RLCT, which are fundamental quantities for characterizing the generalization of singular models. We clarify the theoretical relationship between the local RLCT and existing two key metrics related to generalization under some localization assumption: (I) the rank of the Hessian matrix of the generalization error and (II) the covering number of a family of loss functions. This result provides novel insights into effective dimension and intrinsic complexity of overparameterized models.

0.23

Faster Linear Programming with $\sqrt{\mathrm{rank}}$ Linear System Solves

cs.DS math.OC ·2026-09-25 ·Zhao Song
similarity 0.56
Abstract

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $ε$ using $O(\sqrt n\log^{13}m\cdot\log(mU/ε))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{13}m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$, we give an algorithm that uses $O(\sqrt n\log^{4}m\cdot\log(mU/ε))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/ε))$ such linear-system solves suffice.

0.26

Intrinsic Interaction Geometry Controls the Low-Rank Complexity of Softmax Attention

cs.LG cs.AI ·2026-08-28 ·Yuhe Sui, Jianing Zhang, Yingzhi Tang
theory similarity 0.55
Abstract · 36 pages, 4 figures. Expanded theoretical appendix with complete weighted Gibbs-cover, intrinsic factorization, gauge-boundary, sharpness, a…

How much matrix rank is required to preserve every bounded value output of normalized softmax attention? We study the unrestricted maximum-row-\(\ell_1\) approximation rank \(r_\varepsilon(A)\), exactly the least rank achieving uniform error over all bounded vector-valued values. Row softmax exposes the intrinsic interaction \(C=P_m(\log A)P_N\), whereas invertible \(Q/K\) gauges leave \(A\) fixed while changing the Euclidean geometry of a chosen query/key factorization. We replace that coordinate-dependent description by a projective residual \(q(C-T)\) and an attained factor-radius size \(κ(T)\). For every rank-\(r\) retained interaction with \(τ(T)<\varepsilon\), we prove $$ r_\varepsilon(A)\le \min\left\{ N,\; C_r\left( 1+\frac{κ(T)} {(\varepsilon-τ(T))^2} \right)^{r/2} \right\}, $$ with the same unknown dimension constant as the underlying weighted Gibbs-row cover. The profile is gauge invariant, termwise no worse than native retained-subspace bounds at the same declared dimension, and has a worst-case sharp \(r/2\) size exponent at fixed \(r\) and \(\varepsilon\). We then measure \(r_\varepsilon(A)\) directly on learned attention using 9,978 certified brackets across BERT, GPT-2, Qwen2.5, and two ViT checkpoints; where certificates do not close, the optimum remains interval-valued. A pre-specified 2,302-cell held-out study further shows that the historical native-coordinate geometry block contains coarse, mostly head-level information but no detectable incremental information beyond a strong calibrated baseline. The new intrinsic descriptor is not evaluated in that study. Together, the theory and measurements distinguish an operator-intrinsic complexity control from a stronger empirical explanation that the learned-head evidence does not support.

0.24

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

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β\leq \frac{1}{2}+\varepsilon$

cs.DS math-phmath.PR ·2026-09-11 ·Mathews Boban, Anqi Li, Shayan Oveis Gharan
similarity 0.55
Abstract · 34 pages

We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by $λI$ (where $λ$ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for $β\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.

0.39

A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer

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

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis--$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison--Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.49

Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization

cs.CC math.OC ·2026-10-15 ·Arnaud Vandaele
theory similarity 0.55
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