{"id":"arxiv/2603.29715","url":"https://arxiv.org/abs/2603.29715","tags":["cs.LG","eess.SP","math.OC","stat.ML"],"score":0,"title":"Nonnegative Matrix Factorization in the Component-Wise L1 Norm for Sparse Data","domain":"cs.LG","source":"arxiv","authors":["Giovanni Seraghiti","Kévin Dubrulle","Arnaud Vandaele","Nicolas Gillis"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-31","reactions":{}}