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 34 papers

An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence
Jul 15, 2026Damien Lesens, Jérémy E. Cohen, Bora UçarNon-Negative Matrix Factorization Low-Rank Matrix Decomposition
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.
Identification of NMF by choosing maximum-volume basis vectors
Mar 25, 2026Qianqian Qi, Zhongming Chen, Peter G. M. van der HeijdenNon-Negative Matrix Factorization Representation Identifiability
Hangzhou Dianzi University, China · Utrecht University, the Netherlands and University of Southampton, UK
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.

Jul 15, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

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