Persistent Nonnegative Matrix Factorization via Multi-Scale Graph Regularization

Jichao Zhang; Ran Miao; Limin Li

cs.LGFeb 26, 2026

Persistent Nonnegative Matrix Factorization via Multi-Scale Graph Regularization

Authors: Jichao Zhang, Ran Miao, Limin Li

Organizations: School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, Shaanxi Province, 710049, China

Abstract

Matrix factorization techniques, especially Nonnegative Matrix Factorization (NMF), have been widely used for dimensionality reduction and interpretable data representation. However, existing NMF-based methods are inherently single-scale and fail to capture the evolution of connectivity structures across resolutions. In this work, we propose persistent nonnegative matrix factorization (pNMF), a scale-parameterized family of NMF problems, that produces a sequence of persistence-aligned embeddings rather than a single one. By leveraging persistent homology, we identify a canonical minimal sufficient scale set at which the underlying connectivity undergoes qualitative changes. These canonical scales induce a sequence of graph Laplacians, leading to a coupled NMF formulation with scale-wise geometric regularization and explicit cross-scale consistency constraint. We analyze the structural properties of the embeddings along the scale parameter and establish bounds on their increments between consecutive scales. The resulting model defines a nontrivial solution path across scales, rather than a single factorization, which poses new computational challenges. We develop a sequential alternating optimization algorithm with guaranteed convergence. Numerical experiments on synthetic and single-cell RNA sequencing datasets demonstrate the effectiveness of the proposed approach in multi-scale low-rank embeddings.

Figures & tables

Figure 1: Illustration of the construction of multi-scale topological graphs from persistent homology. (a) Vietoris–Rips complex $\mathcal{X}(\varepsilon)$ on a dataset $X\in\mathbb{R}^{2\times 10}$ . (b) The associated $0$ -dimensional persistence diagram $\mathcal{D}_{0}$ , encoding the death times of connected components. (c) A sequence of weighted graphs defined at the persistence-based scales $\{\varepsilon_{t}\}$ , which serve as the multi-scale topological graphs.

Figure 2: Multi-scale embeddings visualization on simulation data. The first panel shows the intrinsic three-dimensional simulation data before embedding into a 100-dimensional ambient space. The remaining nine panels display the corresponding two-dimensional embeddings

\{H_{t}\}_{t=1}^{80}

uniformly sampled across scales.

Figure 3: Effect of persistence-based scale selection on multi-scale embeddings visualization. Each column corresponds to the same scale index, while each row represents a different scale selection strategy, ordered as pNMF, pNMF-UDS, pNMF-RDS, and pNMF-MSS.

Figure 4: Correlations among scale increments, Laplacian increments, and embedding increments for pNMF. Left: Correlation between

\Delta\varepsilon_{t}

and

\Delta L_{t}

; Middle: Correlation between

\Delta L_{t}

and

\Delta H_{t}

; Right: Correlation between

\Delta\varepsilon_{t}

and

\Delta H_{t}

. Correlation coefficients and p-values are reported in each panel.

Dataset	Metric	NMF	GNMF	TNMF	$k$ -TNMF	pNMF	pNMF-best
GSE75748time	ARI $\uparrow$	0.611	0.602	0.644	0.592	0.722	0.727
	NMI $\uparrow$	0.735	0.731	0.768	0.711	0.854	0.860
	Purity $\uparrow$	0.745	0.720	0.749	0.751	0.850	0.852
	Accuracy $\uparrow$	0.693	0.679	0.744	0.736	0.850	0.852
GSE94820	ARI $\uparrow$	0.547	0.615	0.617	0.607	0.629	0.629
	NMI $\uparrow$	0.665	0.710	0.705	0.699	0.724	0.724

Table 1: Clustering results of different methods on scRNA-seq datasets.

Figure 5: Multi-scale clustering Accuracy across different scales

t

. The curves compare pNMF and baseline methods in terms of Accuracy as the scale index varies.

Figure 6: Clustering performance across different label granularities on the GSE75748time dataset. Each subfigure corresponds to a clustering metric (ARI, NMI, Purity, or Accuracy) and shows the performance across different label granularities (6-, 5-, 4-, and 3-class labels) as a function of the scale index

t

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Empirical convergence behavior of pNMF on the simulation dataset. (a) Objective function value versus outer iteration. (b) Relative decrease of the objective function between successive outer iterations. (c) Fine-grained evolution of the objective function across all update steps in the outer–scale–inner optimization process.

Figure 8: Effect of regularization ablation on multi-scale embedding visualization. Each column corresponds to the same scale index, while each row represents a different model variant. From top to bottom: pNMF (Full), pNMF-noGeom, pNMF-noSmooth, pNMF-noAnchor, pNMF-GeomOnly, and pNMF-SmoothOnly.

Figure 9: t-SNE and UMAP visualizations for scRNA-seq datasets. Each dataset is represented by two rows of panels: the first row shows t-SNE embeddings and the second row shows UMAP embeddings. The first column corresponds to the raw data $X$ directly visualized, while the remaining columns show embeddings from different methods.

Figure 10: Parameter analysis radar charts for scRNA-seq datasets. Each chart displays the clustering performance of pNMF under 27 combinations of regularization parameters

\lambda_{1}

\lambda_{2}

, and

\lambda_{3}

. The metrics plotted are ARI, NMI, Purity, Accuracy, and their average.

Non-Negative Matrix Factorization

Non-negative matrix factorization (NMF) decomposes nonnegative data into additive, interpretable latent components for analysis and discovery.

See all 33 papers

Separable Nonnegative Matrix Factorization Using Powered Ratio-of-Norms Regularization
Aug 28, 2026Matthew McCarver, Jing QinNon-Negative Matrix Factorization Nonconvex Optimization
Department of Mathematics, University of Kentucky, Lexington, KY 40506, USA
Non-negative Matrix Factorisation with Topological Regularisation
Jun 16, 2026Matias de Jong van Lier, Shizuo Kaji, Keunsu KimNon-Negative Matrix Factorization
Recursive Inc. · Tokyo, 150-0002, Japan · Graduate School of Science +5
A Spectral Decomposition Framework for Multiscale Nonlinear Dimensionality Reduction
Apr 2, 2026Zeyang Huang, Angelos Chatzimparmpas, Thomas Höllt +1Dimensionality Reduction Spectral Methods
Linköping University, Sweden · Utrecht University, The Netherlands · University of Bergen, Norway +1

Aug 28, 2026J/K move · Enter open · S save

Separable Nonnegative Matrix Factorization Using Powered Ratio-of-Norms Regularization

Matthew McCarver, Jing Qin

Department of Mathematics, University of Kentucky, Lexington, KY 40506, USA

Non-Negative Matrix Factorization Nonconvex Optimization

Open paper AskPDF arXiv

Separable nonnegative matrix factorization (SNMF) has been widely used for low-rank representation and clustering of nonnegative data, owing to its ability to produce part-based and interpretable decompositions. In particular, SNMF is closely related to graph clustering and community detection. To enhance sparsity and identifiability of the learned factors, we propose an

\ell_1^p/\ell_2

-regularized SNMF model based on a powered ratio-of-norms regularizer. The resulting formulation is nonconvex and nonsmooth, which poses significant challenges for optimization. To address this, we develop efficient algorithms based on the difference-of-convex function algorithm (DCA) and the alternating direction method of multipliers (ADMM). The proposed methods decompose the original problem into tractable subproblems, leveraging closed-form proximal operators associated with the powered norm terms. We establish descent and limiting criticality properties for the DCA scheme and convergence under standard assumptions for the ADMM scheme. Extensive numerical experiments on synthetic datasets and hand gesture classification tasks demonstrate that the proposed approach achieves competitive or improved performance in anchor identification and classification accuracy compared with existing SNMF methods, while maintaining competitive computational efficiency.

Abstract

Non-Negative Matrix Factorization

Explore similar work

Separable Nonnegative Matrix Factorization Using Powered Ratio-of-Norms Regularization

Non-negative Matrix Factorisation with Topological Regularisation

A Spectral Decomposition Framework for Multiscale Nonlinear Dimensionality Reduction