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

Giovanni Seraghiti; Kévin Dubrulle; Arnaud Vandaele; Nicolas Gillis

cs.LGMar 31, 2026

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

Authors: Giovanni Seraghiti, Kévin Dubrulle, Arnaud Vandaele, Nicolas Gillis

Organizations: 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.

Abstract

Nonnegative matrix factorization (NMF) approximates a nonnegative matrix, X, by the product of two nonnegative factors, WH, where W has r columns and H has r rows. In this paper, we consider NMF using the component-wise L1 norm as the error measure (L1-NMF), which is suited for data corrupted by heavy-tailed noise, such as Laplace noise or salt and pepper noise, or in the presence of outliers. Our first contribution is an NP-hardness proof for L1-NMF, even when r=1, in contrast to the standard NMF that uses least squares. Our second contribution is to analyze, under simplified probabilistic assumptions, how the sparsity in the data enforces zero solution in the optimal scalar update in the factors of L1-NMF when all the other entries are kept fixed. This provides an intuition of the connection between the sparsity of the L1-NMF factors with the sparsity of the input. Even though sparsity favors interpretability, if the data is affected by false zeros, too sparse solutions might degrade the model. Our third contribution is a new, more general, L1-NMF model for sparse data, dubbed weighted L1-NMF (wL1-NMF), where the sparsity of the factorization is controlled by adding a penalization parameter to the entries of WH associated with zeros in the data. The fourth contribution is a new coordinate descent (CD) approach for wL1-NMF, denoted as sparse CD (sCD), where each subproblem is solved by a weighted median algorithm. Although it lacks convergence guarantees to a stationary point, sCD is, to the best of our knowledge, the first algorithm for L1-NMF whose complexity scales with the number of nonzero entries in the data, making it efficient in handling large-scale, sparse data. We perform extensive numerical experiments on synthetic and real-world data, including imaging mass spectrometry and topic modeling, to show the effectiveness of our new proposed model (wL1-NMF) and algorithm (sCD).

Figures & tables

Panel of Figure 1 — Figure 1: Example of a one-dimensional nonnegative least absolute deviation (LAD) problem in ( 5 ).

Panel of Figure 2 — Figure 2: Probability of the least squares solution (on the left) and LAD solution (on the right) in ( 7 ) to be greater than zero when each component of the inputs is randomly sampled from a Bernoulli distribution in $\{0,1\}$ with probability $p$ to be 1.

$m\times n$	sparsity	sCD	CD	$\sigma$	gain
$100\times 200$	$25\%$	0.31	0.40	1.37	1.29
	$50\%$	0.20	0.40	2.15	2.0
	$80\%$	0.08	0.39	5.97	4.88
$300\times 400$	$25\%$	2.20	2.94	1.37	1.33
	$50\%$	1.59	3.05	2.13	1.92
	$80\%$	0.61	2.67	5.80	4.38

Table 1: Comparison between sCD and the original CD for L1-NMF on randomly generated data for different dimensions (

m\times n

) and sparsity of the input matrix. The third and fourth columns report the average CPU time per iteration for sCD and CD, respectively, in seconds. The fifth and sixth column report the theoretical gain,

\sigma

in ( 21 ), and the practical gain, resp.

Panel of Figure 3 — Figure 3: Comparison of the robustness of various NMF models on the MNIST dataset depending on the noise level. Relative error w.r.t. ground truth. Noisy data reports $\lVert X-\bar{X}\rVert_{F}/\lVert X\rVert_{F}$ .

Panel of Figure 4 — Figure 4: Examples of the low-rank representations of digits using different NMF models on the MNIST dataset.

Noise		NS [ 4 ]	SUB [ 40 ]	sCD (Alg. 3 )	CD [ 23 ]	sparsity	$\sigma$	gain
$0\%$	res	0.453	0.448	0.428	0.437	81 $\%$	6.2	5.8
$0\%$	iter	183	$7.0\cdot 10^{3}$	29	5
$4\%$	res	0.60	0.593	0.572	0.581	79 $\%$	5.4	4.8
$4\%$	iter	177	$6.8\cdot 10^{3}$	24	5
$8\%$	res	0.710	0.703	0.675	0.685	76 $\%$	4.8	4.4
$8\%$	iter	178	$7.0\cdot 10^{3}$	22	5

Table 2: Comparison of L1-NMF algorithms on the MNIST data with different levels of noise. We report the sparsity of the noisy data (sparsity), the theoretical factor of compression of sCD over CD (

\sigma

defined in ( 21 )), the practical gain (gain) of sCD over CD, the final relative residual (res), and number of iterations performed (iter).

Panel of Figure 5 — Figure 5: Relative error averaged over 10 runs between the noiseless data matrix and the wL1-NMFs for different values of $\lambda$ . Each plot corresponds to different percentages $q_{1}$ of zeros, and each line represents a percentage $q_{2}$ of false zeros among the missing values.

Figure 6: Optical scan (left) of the pig206 dataset from the Cardinal R/Bioconductor package highlighting main tissues in the pig fetus such as brain (left), heart (center), and liver (below the heart). The middle and right images are total ion current images of the pig206 dataset, obtained by summing all columns of $X$ , before (middle) and after (right) injection of 30 localized artifacts (yellow regions).

Figure 7: Spatial abundance maps obtained from the columns of the factor $W$ of $\rank$ -8 wL1-NMF (first and third rows) and FroNMF (second and last rows) on the uncorrupted (no outliers) and corrupted (outliers) pig206 dataset. Interpretation of the factors: general background/tissue (factor 1), mixed brain/liver (factor 2), subcutaneous adipose layer (factor 3), connective tissue (factor 4), liver (factor 5), skin (factor 6), heart (factor 7), brain and spinal cord (factor 8).

	L1 error	Fro error	$\rho_{\max}$	$\rho_{\text{mean}}$
wL1-NMF (uncorrupted)	$\mathbf{0.489\pm 0.002}$	$\mathbf{0.359\pm 0.006}$	/	/
FroNMF (uncorrupted)	$0.546\pm 0.0005$	$0.374\pm 0.0005$	/	/
wL1-NMF (corrupted)	$\mathbf{0.507\pm 0.018}$	$0.533\pm 0.161$	$\mathbf{0.210\pm 0.122}$	$\mathbf{0.064\pm 0.03}$
FroNMF (corrupted)	$0.580\pm 0.005$	$\mathbf{0.466\pm 0.019}$	$0.298\pm 0.037$	$0.112\pm 0.014$

Table 3: Comparison of wL1-NMF (

\lambda=0.1

) and FroNMF applied to the pig206 dataset without corruptions and with high intensity injected outliers. The results are averaged over 10 runs and show two metrics for assessing the quality of the reconstruction (L1 and Fro error) and the max (

\rho_{\max}

) and mean (

\rho_{\text{mean}}

) correlation computed from ( 22 ). Higher values of the quality metrics and lower values of the correlations correspond to the best performance and are highlighted in bold.

	wL1-NMF						FroNMF
$\lambda$	0	0.01	0.04	0.08	0.1	1.0	/
Average words per topic	12898	1780	417	170	123	4	5275
topics less than 5 words	0	0	0	0	1	24	0

Table 4: Impact of the parameter

\lambda

on the wL1-NMF solution on the TDT2 data.

wL1-NMF		FroNMF	wL1-NMF		FroNMF
0.01	0.08	/	0.01	0.08	/
kaczynski	gov.	gov.	european	court	super
algerian	party	party	martin	supreme	bowl
algeria	india	algeria	tour	bowl	game
abacha	bjp	election	documents	super	denver
srinagar	election	elections	algeria	bulls	broncos

Table 5: Ten most important words for two extracted topics (Topic 6 and Topic 17) by FroNMF and wL1-NMF on the TDT2 dataset. In red, we highlight the words that do not have a clear connection with the topic that the majority of the other words refer to.

wL1	Fro	wL1	Fro	wL1	Fro
spkr	saddam	iraq	weapons	spkr	president
president	secretary	iraqi	iraq	president	clinton
clinton	hussein	team	inspectors	clinton	house
saddam	albright	baghdad	iraqi	china	white
iraq	iraqi	sanctions	baghdad	says	clintons
hussein	president	weapons	butler	chinese	allegations

Table 6: Ten most relevant words for the remaining of the extracted topics by the FroNMF and wL1-NMF (

\lambda=0.08

) on the TDT2 dataset.

Figure 8: Spatial abundance maps obtained from the columns of the factor $W$ of rank-8 wL1-NMF with four different regularization parameter $\lambda$ on the corrupted pig206 dataset. Interpretation of the factors: general background/tissue (factor 1), mixed brain/liver (factor 2), subcutaneous adipose layer (factor 3), connective tissue (factor 4), liver (factor 5), skin (factor 6), heart (factor 7), brain and spinal cord (factor 8).

$\lambda$	L1 error	Fro error	$\rho_{\max}$	$\rho_{\text{mean}}$
$0.01$	$0.877$	$2.58$	$0.344$	0.102
$0.05$	$0.507$	$0.727$	$0.234$	$0.065$
$0.1$	$\mathbf{0.506}$	$0.527$	$0.203$	$\mathbf{0.062}$
$0.5$	$0.582$	$\mathbf{0.0478}$	$\mathbf{0.202}$	$0.066$

Table 7: Comparison of wL1-NMF for different values of

\lambda

applied to pig206 dataset with high intensity injected outliers. The results are averaged over 10 runs and show two metric for assessing the quality of the reconstruction (L1 and Fro error) and the max and mean correlation (

\rho_{\max}

and

\rho_{\text{mean}}

) between NMF factors and binary signal of the outliers.

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

Jul 15, 2026

An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence

Nonnegative Matrix Factorization (NMF) is a fundamental tool in unsupervised learning, which approximates a nonnegative matrix by the product of two low-rank nonnegative factors. The Kullback-Leibler (KL) divergence is best suited to measure the data to model discrepancy when the decomposed data sample follows a Poisson distribution, which is the case for count datasets such as term-document matrices or images. Most KL-NMF algorithms in the literature minimize a separable majorant of the loss to find their next iterate. We argue that this method has reached its limits and propose to use instead the second-order Taylor expansion of the loss, leading to a Newton-type method. We minimize this non-separable surrogate by proposing a generalization of the well-known HALS algorithm. This yields an efficient KL-NMF algorithm which provably converges and which competes favorably with state-of-the-art algorithms on a large variety of datasets.

Damien Lesens, Jérémy E. Cohen, Bora Uçar

ENS de Lyon · Univ. Lyon, INSA-Lyon, UCBL, UJM, CNRS, Inserm, CREATIS UMR 5220, U1294, F-69621, Lyon, France. · CNRS and LIP (UMR5668, Université de Lyon - ENS de Lyon - UCBL - CNRS - Inria), 46 allée d'Italie, Lyon, France.

Non-Negative Matrix Factorization Low-Rank Matrix Decomposition Second-Order Optimization

Ask PDF

Mar 25, 2026

Identification of NMF by choosing maximum-volume basis vectors

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.

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

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

Non-Negative Matrix Factorization Representation Identifiability

Ask PDF

Nov 10, 2025

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

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.

Junjun Pan, Valentin Leplat, Michael Ng +1

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

Ask PDF

Abstract

Non-Negative Matrix Factorization

Explore similar work

An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence

Identification of NMF by choosing maximum-volume basis vectors

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