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

• URL: http://arxiv.org/abs/2511.07109v1
• Date: Mon, 10 Nov 2025 13:54:27 GMT
• Title: A Provably-Correct and Robust Convex Model for Smooth Separable NMF
• Authors: Junjun Pan, Valentin Leplat, Michael Ng, Nicolas Gillis,
• Abstract summary: Nonnegative matrix factorization (NMF) is a linear dimensionality technique for nonnegative data, with applications such as hyperspectral unmixing and topic modeling.<n>In particular, separability assumes that the basis vectors in the NMF are equal to some columns of the input matrix.<n>We propose a convex model for SSNMF and show that it provably recovers the sought-after factors, even in the presence of noise.
• Score: 16.819543808413716
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Nonnegative Matrix Factorization through Cone Collapse [0.9453554184019107]
  We propose Cone Collapse, an algorithm that starts from the full nonnegative orthant and iteratively shrinks it toward the minimal cone generated by the data.<n>Across 16 benchmark gene-expression, text, and image datasets, CC-NMF consistently matches or outperforms strong NMF baselines.<n>These results demonstrate that explicitly recovering the data cone can yield both theoretically grounded and empirically strong NMF-based clustering methods.
  arXiv  Detail & Related papers  (2025-11-27T13:22:37Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  This paper presents an algorithm to solve the Soft k-Means problem globally. A new model, named Minimal Volume Soft kMeans (MVSkM), is proposed to address solutions non-uniqueness issue.
  arXiv  Detail & Related papers  (2022-12-07T12:06:55Z)
• Adaptive Weighted Nonnegative Matrix Factorization for Robust Feature Representation [9.844796520630522]
  Nonnegative matrix factorization (NMF) has been widely used to dimensionality reduction in machine learning. Traditional NMF does not properly handle outliers, so that it is sensitive to noise. This paper proposes an adaptive weighted NMF, which introduces weights to emphasize the different importance of each data point.
  arXiv  Detail & Related papers  (2022-06-07T05:27:08Z)
• SymNMF-Net for The Symmetric NMF Problem [62.44067422984995]
  We propose a neural network called SymNMF-Net for the Symmetric NMF problem. We show that the inference of each block corresponds to a single iteration of the optimization. Empirical results on real-world datasets demonstrate the superiority of our SymNMF-Net.
  arXiv  Detail & Related papers  (2022-05-26T08:17:39Z)
• 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)
• Co-Separable Nonnegative Matrix Factorization [20.550794776914508]
  Nonnegative matrix factorization (NMF) is a popular model in the field of pattern recognition. We refer to this NMF as a Co-Separable NMF (CoS-NMF) An optimization model for CoS-NMF is proposed and alternated fast gradient method is employed to solve the model.
  arXiv  Detail & Related papers  (2021-09-02T07:05:04Z)
• Feature Weighted Non-negative Matrix Factorization [92.45013716097753]
  We propose the Feature weighted Non-negative Matrix Factorization (FNMF) in this paper. FNMF learns the weights of features adaptively according to their importances. It can be solved efficiently with the suggested optimization algorithm.
  arXiv  Detail & Related papers  (2021-03-24T21:17:17Z)
• 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)
• Fast and Secure Distributed Nonnegative Matrix Factorization [13.672004396034856]
  Nonnegative matrix factorization (NMF) has been successfully applied in several data mining tasks. We study the acceleration and security problems of distributed NMF.
  arXiv  Detail & Related papers  (2020-09-07T01:12:20Z)
• Dense Non-Rigid Structure from Motion: A Manifold Viewpoint [162.88686222340962]
  Non-Rigid Structure-from-Motion (NRSfM) problem aims to recover 3D geometry of a deforming object from its 2D feature correspondences across multiple frames. We show that our approach significantly improves accuracy, scalability, and robustness against noise.
  arXiv  Detail & Related papers  (2020-06-15T09:15:54Z)
• 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.