Fast and Effective Computation of Generalized Symmetric Matrix Factorization

Lei Yang; Han Wan; Min Zhang; Ling Liang

math.OCMar 19, 2026

Fast and Effective Computation of Generalized Symmetric Matrix Factorization

Authors: Lei Yang, Han Wan, Min Zhang, Ling Liang

Organizations: School of Computer Science and Engineering, and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University · School of Computer Science and Engineering, Sun Yat-sen University · School of Mathematics and Information Science, Guangzhou University · Department of Mathematics, The University of Tennessee, Knoxville

Abstract

In this paper, we study a nonconvex, nonsmooth, and non-Lipschitz generalized symmetric matrix factorization model that unifies a broad class of matrix factorization formulations arising in machine learning, image science, engineering, and related areas. We first establish two exactness properties. On the modeling side, we prove an exact penalty property showing that, under suitable conditions, the symmetry-inducing quadratic penalty enforces symmetry whenever the penalty parameter is sufficiently large but finite, thereby exactly recovering the associated symmetric formulation. On the algorithmic side, we introduce an auxiliary-variable splitting formulation and establish an exact relaxation relationship that rigorously links stationary points of the original objective function to those of a relaxed potential function. Building on these exactness properties, we propose an average-type nonmonotone alternating updating method (A-NAUM) based on the relaxed potential function. At each iteration, A-NAUM alternately updates the two factor blocks by (approximately) minimizing the potential function, while the auxiliary block is updated in closed form. To ensure the convergence and enhance practical performance, we further incorporate an average-type nonmonotone line search and show that it is well-defined under mild conditions. Moreover, based on the Kurdyka-Łojasiewicz property and its associated exponent, we establish global convergence of the entire sequence to a stationary point and derive convergence rate results. Finally, numerical experiments on real datasets demonstrate the efficiency of A-NAUM.

Figures & tables

Z^{k}={\textstyle\left(\mathcal{I}-\frac{\beta}{\alpha+\beta}\mathcal{A}^{*}\mathcal{A}\right)}(X^{k}(Y^{k})^{\top})+{\textstyle\frac{\beta}{\alpha+\beta}}\mathcal{A}^{*}(\bm{b}).

(4.3)

Algorithm 1 A-NAUM for computing a stationary point of

\mathcal{F}_{\lambda}

	$\lambda=0$						$\lambda=1$
	M-NAUM			A-NAUM			M-NAUM			A-NAUM
$\alpha$	iter	relobj	time	iter	relobj	time	iter	relobj	time	iter	relobj	time
0.2	181308	8.38e-03	112.86	319155	8.38e-03	203.13	38628	8.38e-03	24.15	31660	8.38e-03	18.09
0.4	69086	8.38e-03	37.38	120227	8.38e-03	69.39	16440	8.38e-03	9.23	32363	8.38e-03	18.40
0.6	41026	8.38e-03	11.44	39884	8.38e-03	11.14	8114	8.38e-03	2.25	8255	8.38e-03	2.36
0.8	51993	8.38e-03	14.55	50518	8.38e-03	14.25	8056	8.38e-03	2.21	7872	8.38e-03	2.15

Table 1: Comparisons between M-NAUM and A-NAUM with different

\alpha

t=0.001

r=5

, and

\lambda\in\{0,1\}

on ORL.

Panel of Figure 1 — Figure 1: Average relative objective values versus running time (over 5 independent runs) for different factorization ranks $r\in\{5,50,150\}$ and noise levels $t\in\{0.001,0.01,0.1\}$ on ORL.

Panel of Figure 2 — Figure 2: Average relative objective values versus running time (over 5 independent runs) for different penalty parameters $\lambda\in\{0.01,1,100\}$ on ORL and CBCL.

Matrix Factorization

Matrix factorization represents data or model weights as products of lower-dimensional matrices for compression, prediction, and latent-structure discovery.

See all 54 papers

Jun 1, 2026

A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering

Symmetric nonnegative matrix factorization (Symmetric NMF) approximates a matrix as

WW^T

with nonnegative rectangular factor

W

. It has broad applications in graph clustering and machine learning. In contrast to the NMF, projected gradient methods for the symmetric problem had been associated with slow convergence. To address this, we introduce SNMPBB, the first adaptation of nonmonotone projected Barzilai-Borwein methods to Symmetric NMF, demonstrating that gradient algorithms are significantly more effective than previously understood. We further extend SNMPBB to graph clustering using the graph Laplacian regularization (Graph-SNMPBB) and to large problems with low-rank approximations (LAI-SNMPBB). For all variants we prove global convergence to first-order stationary points and also that Barzilai-Borwein curvature information is preserved with randomized approximations. On synthetic data, SNMPBB achieves 6 times speedup over the alternative SymANLS for similar residuals, with advantages growing at higher ranks. Across six real-world clustering benchmarks, Graph-SNMPBB matches or exceeds SymANLS accuracy. Lastly, LAI-SNMPBB outperforms state-of-the-art LAI-SymPGNCG on 34 SuiteSparse matrices in both runtime and residual quality.

Ryan Swart, Johannes Brust

School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ

Non-Negative Matrix Factorization Graph Clustering Matrix Optimization

Ask PDF

Jul 27, 2026

Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization

Symmetric non-negative matrix factorization (SymNMF) recovers latent group structure from a dependence matrix, but its dense, quadratic-memory objective has confined prior work to moderate sizes. We present a large-scale GPU study of seven algorithm families (over 30 configurations) on absolute Pearson correlation and tail pairwise dependence matrices from Extreme Value Theory, two proxies for empirical risk-factor estimation on large portfolios. A trace-identity reformulation eliminates all

n \times n

intermediates, so a single GPU reaches

n \approx 10^5

and multi-node distribution scales to

n = 10^6

and beyond. Under a two-phase protocol, eleven methods converge at moderate scale; six remain efficient enough at

n = 10^5

(five AdaGrad-family plus ADMM), and five AdaGrad-family methods still converge at

n = 10^6

: AdaGrad, RMSprop, and three we introduce (Piecewise AdaGrad, Row-Stochastic SVRG, Block-SVRG AdaptGrow). At

n = 10^6

the fastest solver tracks the matrix spectrum: Block-SVRG AdaptGrow wins on the flat, ill-conditioned tail-dependence spectrum, where its lower per-iteration cost decides a long factorization, and full-batch AdaGrad wins on the dominant-low-rank correlation spectrum, where the run is short. We also benchmark spherical K-means as a hard-label baseline: cheaper when angular cluster structure is present, yet provably degenerate once the matrix collapses toward a single common factor, where the soft factorization remains necessary.

Lavinia Ghita, Dhruv Desai, Jake Goldberg +1

NVIDIA

Non-Negative Matrix Factorization Low-Rank Matrix Decomposition Matrix Optimization Adaptive Gradient Methods Stochastic Gradient Descent

Ask PDF

Jun 6, 2026

On solving symmetric multi-type orthogonal non-negative matrix tri-factorization problem

We study the symmetric multi-type orthogonal non-negative matrix tri-factorization problem, where several symmetric non-negative matrices are simultaneously approximated by factors of the form

GS_{i}G^{\top}

, with a shared non-negative and orthogonal factor

G

. This model is motivated by clustering and network analysis, where non-negativity improves interpretability and orthogonality gives a natural assignment-type structure to the latent factor. Since the resulting optimization problem is highly non-convex, we develop two heuristic algorithms for computing high-quality local solutions. The first one is a fixed point method derived from the Karush-Kuhn-Tucker conditions after adding a penalty term for the orthogonality constraint. The second one is a three-stage ADAM-based method that combines non-negativity-preserving optimization, orthogonalization, and restricted ADAM refinement on the feasible set. We evaluate both methods on synthetic data, including noisy instances, and on citation network benchmarks. The synthetic experiments show that both algorithms recover factorizations close to the optimum and remain stable under noise. On real networks, the learned embeddings are competitive with or better than standard baselines such as SVD, node2vec, and classical link prediction heuristics in link prediction, node clustering, and node classification tasks.

Rok Hribar, Gregor Papa, Janez Povh +1

Computer Systems Department, Jožef Stefan Institute, Jamova cesta 39, Ljubljana, 1000, Slovenia. · Laboratory for Engineering Design, Faculty of Mechanical Engineering, University of Ljubljana, Aškerčeva cesta 6, Ljubljana, 1000, Slovenia. · Rudolfovo – Science and Technology Centre Novo mesto, Podbreznik 15, Novo mesto, 8000, Slovenia. +1

Non-Negative Matrix Factorization Graph Clustering Matrix Optimization Graph Embedding

Ask PDF

Abstract

Matrix Factorization

Explore similar work

A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering

Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization

On solving symmetric multi-type orthogonal non-negative matrix tri-factorization problem