Identification of NMF by choosing maximum-volume basis vectors

Qianqian Qi; Zhongming Chen; Peter G. M. van der Heijden

cs.LGMar 25, 2026

Identification of NMF by choosing maximum-volume basis vectors

Authors: Qianqian Qi, Zhongming Chen, Peter G. M. van der Heijden

Organizations: Hangzhou Dianzi University, China · Utrecht University, the Netherlands and University of Southampton, UK

Abstract

In nonnegative matrix factorization (NMF), minimum-volume-constrained NMF is a widely used framework for identifying the solution of NMF by making basis vectors as similar as possible. This typically induces sparsity in the coefficient matrix, with each row containing zero entries. Consequently, minimum-volume-constrained NMF may fail for highly mixed data, where such sparsity does not hold. Moreover, the estimated basis vectors in minimum-volume-constrained NMF may be difficult to interpret as they may be mixtures of the ground truth basis vectors. To address these limitations, in this paper we propose a new NMF framework, called maximum-volume-constrained NMF, which makes the basis vectors as distinct as possible. We further establish an identifiability theorem for maximum-volume-constrained NMF and provide an algorithm to estimate it. Experimental results demonstrate the effectiveness of the proposed method.

Figures & tables

Panel of Figure 1 — Figure 1: A graphical view of columns of the matrix $\bm{X}$ (blue dots) and $\text{cone}(\bm{M})$ (dashed triangle), sliced by the unit-sum hyperplane $\bm{y}^{T}\bm{1}=1$ : (a) nonuniqueness; (b) minimum-volume-constrained NMF; (c) maximum-volume-constrained NMF.

Panel of Figure 2 — Figure 2: (a, b): A graphical representation of rows of the estimated basis matrix $\bm{MS}$ (blue dots), $\text{cone}(\bm{e}_{1},\bm{e}_{2},\bm{e}_{3})$ (solid triangle) with $\bm{e}_{1}=(1,0,0)^{T}$ , $\bm{e}_{2}=(0,1,0)^{T}$ , and $\bm{e}_{3}=(0,0,1)^{T}$ , and $\text{cone}((\bm{MS})^{T})$ (dashed polygon), sliced by the unit-sum hyperplane $\bm{y}^{T}\bm{1}=1$ ; (c, d): A graphical representation of columns of the estimated coefficient matrix $\bm{S}^{-1}\bm{H}$ (blue dots), $\text{cone}(\bm{e}_{1},\bm{e}_{2},\bm{e}_{3})$ (solid triangle), and $\text{cone}(\bm{S}^{-1}\bm{H})$ (dashed polygon), sliced by the unit-sum hyperplane $\bm{y}^{T}\bm{1}=1$ .

Panel of Figure 3 — Figure 3: Artificial grain-size distributions (GSDs) datasets from [ 17 ] (a) The four ground truth basis vectors used from [ 17 ] , which were from the calculated EMs from the grain-size data of the surface sediment in the South Yellow Sea by [ 19 ] ; (b) Test Dataset 1; (c) Test Dataset 2.

Methods	Test Dataset 1	Test Dataset 2
MVC-NMF	-5.7100	-4.9230
MAV-NMF	-5.6270	-4.4340

Table 1: Artificial grain size distributions datasets;

\text{logdet}(\bm{M}^{T}\bm{M}+\delta\bm{I})

Panel of Figure 4 — Figure 4: CBCL face data set: (a) MVC-NMF; (b) MAV-NMF.

Methods	CBCL
MVC-NMF	-107.7660
MAV-NMF	-90.4210

Table 2: Real-world CBCL dataset;

\text{logdet}(\bm{M}^{T}\bm{M}+\delta\bm{I})

Model	/	MVC-NMF			MAV-NMF
$\bm{M}$	$k=1$	$k=1$	$k=2$	$k=3$	$k=1$	$k=2$	$k=3$
paidwork	0.0803	0.0000	0.2180	0.0630	0.0000	0.2499	0.0000
dom.work	0.0779	0.1471	0.0171	0.0042	0.1460	0.0000	0.0000
caring	0.0167	0.0241	0.0162	0.0000	0.0237	0.0133	0.0000
shopping	0.0253	0.0360	0.0165	0.0131	0.0360	0.0137	0.0104
per.need	0.0347	0.0371	0.0318	0.0332	0.0371	0.0310	0.0336

Table 3: Time allocation dataset for dimensionality

K=3

using MVC-NMF and MAV-NMF, where M3580 denotes males aged 35-49 in the 1980 survey and F5075 denotes females aged 50-64 in the 1975 survey, and similarly for the other group labels.

Methods	Time allocation
MVC-NMF	-4.6060
MAV-NMF	-4.2750

Table 4: Real-world time allocation dataset;

\text{logdet}(\bm{M}^{T}\bm{M}+\delta\bm{I})

Panel of Figure 9 — Figure B.1 : Data with no zero entries in all rows of the ground truth coefficient matrix $\bm{H}$ : (a) one row without zero entries; (b) two rows without zero entries; (c) all three rows without zero entries.

Methods	one row without zero entries	two rows without zero entries	three rows without zero entries
MVC-NMF	1.3720	1.1760	1.1030
MAV-NMF	1.4990	1.5040	1.5030

Table B.1 : The volume of basis matrix for data where not all rows of

\bm{H}

contains zero entries;

\text{logdet}(\bm{M}^{T}\bm{M}+\delta\bm{I})

Activities	Male															Female
	12–24			25–34			35–49			50–64			65+			12–24			25–34			35–49			50–64			65+
	1975	1980	1985	1975	1980	1985	1975	1980	1985	1975	1980	1985	1975	1980	1985	1975	1980	1985	1975	1980	1985	1975	1980	1985	1975	1980	1985	1975	1980	1985
paidwork	901	769	707	2180	1992	1899	1901	2008	2093	1708	1357	1206	176	71	95	723	665	564	439	471	704	299	375	412	151	153	233	11	6	19
dom.work	87	157	155	250	269	341	249	289	331	244	337	450	617	563	636	494	460	397	1342	1338	1147	1567	1605	1529	1600	1558	1487	1319	1409	1318
caring	33	28	15	194	206	184	99	128	136	51	54	25	124	27	38	135	99	86	635	673	651	296	309	308	83	84	82	78	154	44
shopping	120	138	127	152	157	183	173	157	185	227	221	230	273	251	264	208	200	223	347	336	336	372	347	373	376	335	352	384	292	320

Table C.1 : Time-allocation dataset [ 25 , 26 ] .

Non-Negative Matrix Factorization

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

See all 34 papers

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
Nonnegative Matrix Factorization in the Component-Wise L1 Norm for Sparse Data
Mar 31, 2026Giovanni Seraghiti, Kévin Dubrulle, Arnaud Vandaele +1Non-Negative Matrix Factorization Matrix Factorization
University of Mons, Rue de Houdain 9, 7000 Mons, Belgium, and Dipartimento di Ingegneria Industriale, Università degli Studi di Firenze, Viale Morgagni 40/44, 50134 Firenze, Italia. Member of the INdAM Research Group GNCS. · University of Mons, Rue de Houdain 9, 7000 Mons, Belgium.
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.

May 19, 2026J/K move · Enter open · S save

An Exterior Method for Nonnegative Matrix Factorization

Qiujing Lu, Tonmoy Monsoor, Ehsan Ebrahimzadeh, Kartik Sharma+1

1ECE, UCLA · 2eBay Search Science Team

Non-Negative Matrix Factorization Low-Rank Matrix Decomposition Nonconvex Optimization Low-Rank Approximation Constrained Optimization Matrix Optimization

Open paper AskPDF arXiv

Nonnegative matrix factorization (NMF) seeks a low-rank approximation

X \approx UV^T

with nonnegative factors and is commonly solved using interior methods that enforce feasibility throughout optimization. We show that such constraint-driven approaches can impede progress in the nonconvex landscape, leading to slow convergence or convergence to suboptimal stationary points. We propose an exterior framework for NMF (eNMF) that separates low-rank approximation from nonnegativity enforcement. Our method initializes from the optimal unconstrained factorization and introduces a rotation procedure that maps unconstrained factors to an exterior point closest to the nonnegative orthant. This viewpoint yields an algorithmic framework in which simple iterative updates converge to KKT-satisfying stationary points on the boundary of the positive orthant. The exterior formulation also enables a geometric interpretation of NMF solutions, clarifying equivalence classes of factorizations under permutation and orthogonal transformations. An intriguing numerical result, involving 400 NMF experiments across both real and synthetic datasets, show that in 99% of the cases, different algorithms tend to converge towards equivalent factor matrices. We benchmark eNMF against 9 state-of-the-art NMF algorithms with 9 initialization schemes across 3 real-world and 2 synthetic datasets. eNMF consistently outperforms all 81 competitors, achieving up to 30% lower reconstruction error under equal-time settings and up to 150% speedup under equal-error settings. The downstream experiments further demonstrate substantial performance gains in audio processing and recommendation tasks, corroborating the practical benefits of the proposed exterior optimization framework. Code is available at https://github.com/roychowdhuryresearch/eNMF

Abstract

Non-Negative Matrix Factorization

Explore similar work

An Exterior Method for Nonnegative Matrix Factorization

Nonnegative Matrix Factorization in the Component-Wise L1 Norm for Sparse Data

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