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

Matthew McCarver; Jing Qin

math.NAAug 28, 2026

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

Authors: Matthew McCarver, Jing Qin

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

Abstract

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.

Figures & tables

Figure 1: Geometry of the regularizer

R_{p}(x)=\|x\|_{1}^{p}/\|x\|_{2}

\mathbb{R}^{2}

Algorithm	Type 1 Data		Type 2 Data
DCA	Success Rate	Runtime	Success Rate	Runtime
$p=1$	$0.68$	$0.0633$	$1$	$0.0962$
ADMM-P	Success Rate	Runtime	Success Rate	Runtime
$p=1$	$0.32$	$0.0396$	$1$	$0.0021$
$p=2$	$1$	$0.0868$	$1$	$0.518$
$p=3$	$1$	$0.0657$	$0.38$	$0.0216$

Table 1: Noise-free recovery success rates and runtimes for Algorithms 1 – 2 with

R_{p,1}

-regularization on Type 1 and Type 2 data.

Algorithm	Type 1 Data		Type 2 Data
DCA	Success Rate	Runtime	Success Rate	Runtime
$p=1$	0	$0.0346$	$1$	$0.1004$
ADMM-P	Success Rate	Runtime	Success Rate	Runtime
$p=1$	$0.60$	$0.6788$	$1$	$2.1212$
$p=2$	$1$	$0.5421$	$1$	$2.5972$
$p=3$	$1$	$0.9027$	$1$	$2.6990$

Table 2: Noise-free recovery success rates and runtimes for Algorithms 1 – 2 with

R_{p,*}

-regularization on Type 1 and Type 2 data.

Figure 2: Performance comparison of the proposed algorithms and baseline methods on Type 1 data.

Figure 3: Performance comparison of the proposed algorithms and baseline methods on Type 2 data.

Panel of Figure 4 — Figure 4: Sample images in the binary hand gesture data.


Features	Factorization Rank $r$
	130	259	388	517	646
SPA	0.6333	0.8000	0.8333	0.9000	0.9667
FGNSR	0.6667	0.8333	0.8333	0.9333	0.9667
MERIT	0.6667	0.6667	0.8667	0.9000	0.9667
DCA	0.9867	0.9960	0.9960	0.9947	0.9960

Table 4: Classification accuracy comparison on binary hand gesture data using HOG and LBP features.


Features	Factorization Rank $r$
	130	259	388	517	646
SPA	0.0387	0.0583	0.0822	0.1078	0.1979
FGNSR	30.12	27.57	21.95	18.36	15.28
MERIT	38.08	35.26	27.27	18.73	15.64
DCA	30.34	18.18	21.90	18.52	35.18

Table 5: Runtime (seconds) comparison of Algorithms 1 and 2 versus baseline methods on binary hand gesture data.

Panel of Figure 5 — Figure 5: Gray-Scale hand gestures


Features	Factorization Rank $r$
	130	260	389	519	648
SPA	0.4000	0.4400	0.4400	0.5600	0.8000
FGNSR	0.3200	0.4800	0.7600	0.8000	0.8000
MERIT	0.5600	0.4000	0.6400	0.8000	0.7200
DCA	0.7888	0.8880	0.8304	0.7616	0.7792

Table 7: Classification accuracies for grayscale dataset,

R_{p,1}(X)

regularizer


Algorithm	Factorization Rank $r$
	130	260	389	519	648
SPA	0.0946	0.1212	0.1487	0.1770	0.1995
FGNSR	33.03	29.99	21.38	16.93	14.24
MERIT	37.63	35.48	27.88	16.93	13.74
DCA	41.32	34.28	35.35	34.48	35.54

Table 8: Runtime (seconds) for grayscale dataset–

R_{p,1}(X)

regularizer

Figure 6: Success rate across

p\in\{1,2,3,4\}

for Algorithm 2 on Type 1 data for the

R_{p,1}

and

R_{p,*}

-regularized models.

Figure 7: Accuracy versus iteration budget for the proposed

R_{p,1}

-regularized algorithms on Type 1 data.

Figure 8: Accuracy versus iteration budget for the proposed

R_{p,*}

-regularized algorithms on Type 1 data.

Figure 9: Accuracy of DCA and ADMM-P with

R_{p,1}

regularization for different matrix sizes on Type 2 data.

Figure 10: Runtime scalability of ADMM-P with

R_{p,*}

and

R_{p,1}

regularization on Type 2 data. The nuclear-norm computation dominates the runtime for

R_{p,*}

, whereas

R_{p,1}

is substantially more efficient as the matrix size increases.

Algorithm / Operation	Complexity: $R_{p,1}(X)$	Complexity: $R_{p,*}(X)$
$\mathcal{P}_{\Omega}(\cdot)$	$\mathcal{O}(n^{2}\log n)$	$\mathcal{O}(n^{2}\log n)$
Alg. 1 or Alg. 2	$\mathcal{O}(n^{2}\log n)$	$\mathcal{O}(n^{3})$

Table 9: Per-inner-iteration computational complexities for Algorithms 1 – 2 under each regularizer choice.

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

A Provably-Correct and Robust Convex Model for Smooth Separable NMF
Nov 10, 2025Junjun Pan, Valentin Leplat, Michael Ng +1Non-Negative Matrix Factorization Hyperspectral Unmixing
Department of Mathematics, Hong Kong Baptist University, Hong Kong. · Institute of Data Science and Artificial Intelligence, Faculty of Computer Science and Engineering, Innopolis University. · Department of Mathematics and Operational Research, Université de Mons, Rue de Houdain 9, 7000 Mons, Belgium.
An Exterior Method for Nonnegative Matrix Factorization
May 19, 2026Qiujing Lu, Tonmoy Monsoor, Ehsan Ebrahimzadeh +2Non-Negative Matrix Factorization Low-Rank Matrix Decomposition
1ECE, UCLA · 2eBay Search Science Team
A Nonmonotone Gradient-Based Algorithm for Symmetric Nonnegative Matrix Factorization and Graph Clustering
Jun 1, 2026Ryan Swart, Johannes BrustNon-Negative Matrix Factorization Graph Clustering
School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ

Nov 10, 2025J/K move · Enter open · S save

A Provably-Correct and Robust Convex Model for Smooth Separable NMF

Junjun Pan, Valentin Leplat, Michael Ng, Nicolas Gillis

Department of Mathematics, Hong Kong Baptist University, Hong Kong. · Institute of Data Science and Artificial Intelligence, Faculty of Computer Science and Engineering, Innopolis University. · Department of Mathematics and Operational Research, Université de Mons, Rue de Houdain 9, 7000 Mons, Belgium.

Non-Negative Matrix Factorization Hyperspectral Unmixing

Open paper AskPDF arXiv

Nonnegative matrix factorization (NMF) is a linear dimensionality reduction technique for nonnegative data, with applications such as hyperspectral unmixing and topic modeling. NMF is a difficult problem in general (NP-hard), and its solutions are typically not unique. To address these two issues, additional constraints or assumptions are often used. In particular, separability assumes that the basis vectors in the NMF are equal to some columns of the input matrix. In that case, the problem is referred to as separable NMF (SNMF) and can be solved in polynomial-time with robustness guarantees, while identifying a unique solution. However, in real-world scenarios, due to noise or variability, multiple data points may lie near the basis vectors, which SNMF does not leverage. In this work, we rely on the smooth separability assumption, which assumes that each basis vector is close to multiple data points. We explore the properties of the corresponding problem, referred to as smooth SNMF (SSNMF), and examine how it relates to SNMF and orthogonal NMF. We then propose a convex model for SSNMF and show that it provably recovers the sought-after factors, even in the presence of noise. We finally adapt an existing fast gradient method to solve this convex model for SSNMF, and show that it compares favorably with state-of-the-art methods on both synthetic and hyperspectral datasets.

Abstract

Non-Negative Matrix Factorization

Explore similar work

A Provably-Correct and Robust Convex Model for Smooth Separable NMF

An Exterior Method for Nonnegative Matrix Factorization

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