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

• URL: http://arxiv.org/abs/2603.29715v1
• Date: Tue, 31 Mar 2026 13:16:02 GMT
• Title: Nonnegative Matrix Factorization in the Component-Wise L1 Norm for Sparse Data
• Abstract summary: We consider nonnegative matrix factorization (NMF) using the component-wise L1 norm as the error measure (L1-NMF)<n>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.<n>Our third contribution is a new, more general, L1-NMF model for sparse data, dubbed weighted L1-NMF (wL1-NMF)
• Score: 9.842769671181276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 show that L1-NMF strongly enforces sparsity in the factors for sparse input matrices, thereby favoring interpretability. However, 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. To the best of our knowledge, sCD is 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 to show the effectiveness of our new proposed model (wL1-NMF) and algorithm (sCD).

Related papers

• An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence [1.1470070927586018]
  Nonnegative Matrix Factorization (NMF) approximates a nonnegative matrix by the product of two low-rank nonnegative factors.<n>Most KL-NMF algorithms minimize a separable majorant of the loss to find their next decomposed.<n>We argue that this method has reached its limits and propose to use instead the second-order Taylor expansion of the loss.<n>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.
  arXiv  Detail & Related papers  (2026-07-15T14:59:07Z)
• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) aims to classify both base and novel images using labeled base data. Current approaches inadequately address the intrinsic optimization of the co-occurrence matrix $barA$ based on cosine similarity. We propose a Non-Negative Generalized Category Discovery (NN-GCD) framework to address these deficiencies.
  arXiv  Detail & Related papers  (2024-10-29T07:24:11Z)
• DFedADMM: Dual Constraints Controlled Model Inconsistency for Decentralized Federated Learning [52.83811558753284]
  Decentralized learning (DFL) discards the central server and establishes a decentralized communication network. Existing DFL methods still suffer from two major challenges: local inconsistency and local overfitting.
  arXiv  Detail & Related papers  (2023-08-16T11:22:36Z)
• Log-based Sparse Nonnegative Matrix Factorization for Data Representation [55.72494900138061]
  Nonnegative matrix factorization (NMF) has been widely studied in recent years due to its effectiveness in representing nonnegative data with parts-based representations. We propose a new NMF method with log-norm imposed on the factor matrices to enhance the sparseness. A novel column-wisely sparse norm, named $ell_2,log$-(pseudo) norm, is proposed to enhance the robustness of the proposed method.
  arXiv  Detail & Related papers  (2022-04-22T11:38:10Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• An Entropy Weighted Nonnegative Matrix Factorization Algorithm for Feature Representation [6.156004893556576]
  We propose a new type of NMF called entropy weighted NMF (EWNMF) EWNMF uses an optimizable weight for each attribute of each data point to emphasize their importance. Experimental results with several data sets demonstrate the feasibility and effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2021-11-27T23:37:20Z)
• Structured Sparse Non-negative Matrix Factorization with L20-Norm for scRNA-seq Data Analysis [10.628932392896374]
  We introduce a row-s NMF with $ell_2,0$-norm constraint (ONMF_$ell_20$) to enhance clustering performance. We propose an efficient algorithm to solve matrixMF_$ell_20$ by transforming it into a series of penalized datasets.
  arXiv  Detail & Related papers  (2021-04-27T13:31:41Z)
• Entropy Minimizing Matrix Factorization [102.26446204624885]
  Nonnegative Matrix Factorization (NMF) is a widely-used data analysis technique, and has yielded impressive results in many real-world tasks. In this study, an Entropy Minimizing Matrix Factorization framework (EMMF) is developed to tackle the above problem. Considering that the outliers are usually much less than the normal samples, a new entropy loss function is established for matrix factorization.
  arXiv  Detail & Related papers  (2021-03-24T21:08:43Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  Symmetric nonnegative factor matrix (SNMF) has demonstrated to be a powerful method for data clustering. Inspired by ensemble clustering that aims to seek better clustering results, we propose self-supervised SNMF (S$3$NMF) We take advantage of the sensitivity to code characteristic of SNMF, without relying on any additional information.
  arXiv  Detail & Related papers  (2021-03-02T12:47:40Z)
• Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence [20.671178429005973]
  Kullback-Leibler (KL) divergence is one of the most widely used objective function for nonnegative matrix factorization (NMF) We propose three new algorithms that guarantee the non-increasingness of the objective function. We conduct extensive numerical experiments to provide a comprehensive picture of the performances of the KL NMF algorithms.
  arXiv  Detail & Related papers  (2020-10-05T11:51:39Z)
• Sparse Separable Nonnegative Matrix Factorization [22.679160149512377]
  We propose a new variant of nonnegative matrix factorization (NMF) Separability requires that the columns of the first NMF factor are equal to columns of the input matrix, while sparsity requires that the columns of the second NMF factor are sparse. We prove that, in noiseless settings and under mild assumptions, our algorithm recovers the true underlying sources.
  arXiv  Detail & Related papers  (2020-06-13T03:52:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.