An Exterior Method for Nonnegative Matrix Factorization

• URL: http://arxiv.org/abs/2605.19325v1
• Date: Tue, 19 May 2026 04:03:11 GMT
• Title: An Exterior Method for Nonnegative Matrix Factorization
• Abstract summary: Nonconstrained matrix factorization seeks a low-rank $X approx UVT$ with non-negative approximations.<n>eNMF outperforms in equal-time settings up to 150% under speedup.
• Score: 6.9058663395582345
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonnegative matrix factorization (NMF) seeks a low-rank approximation $X \approx UV^T$ with nonnegative factors and is commonly solved using interior methods that enforce feasibility throughout optimization. We show that such constraint-driven approaches can impede progress in the nonconvex landscape, leading to slow convergence or convergence to suboptimal stationary points. We propose an exterior framework for NMF (eNMF) that separates low-rank approximation from nonnegativity enforcement. Our method initializes from the optimal unconstrained factorization and introduces a rotation procedure that maps unconstrained factors to an exterior point closest to the nonnegative orthant. This viewpoint yields an algorithmic framework in which simple iterative updates converge to KKT-satisfying stationary points on the boundary of the positive orthant. The exterior formulation also enables a geometric interpretation of NMF solutions, clarifying equivalence classes of factorizations under permutation and orthogonal transformations. An intriguing numerical result, involving 400 NMF experiments across both real and synthetic datasets, show that in 99% of the cases, different algorithms tend to converge towards equivalent factor matrices. We benchmark eNMF against 9 state-of-the-art NMF algorithms with 9 initialization schemes across 3 real-world and 2 synthetic datasets. eNMF consistently outperforms all 81 competitors, achieving up to 30% lower reconstruction error under equal-time settings and up to 150% speedup under equal-error settings. The downstream experiments further demonstrate substantial performance gains in audio processing and recommendation tasks, corroborating the practical benefits of the proposed exterior optimization framework. Code is available at https://github.com/roychowdhuryresearch/eNMF

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)
• A Globally Optimal Analytic Solution for Semi-Nonnegative Matrix Factorization with Nonnegative or Mixed Inputs [0.0]
  We develop a new type of matrix factorization called Semi-Nonnegative Factorization (semi-NMF)<n>We prove that our method attains the global decomposition of the reconstruction error.<n>Our method offers both theoretical and empirical advantages.
  arXiv  Detail & Related papers  (2025-08-10T01:15:29Z)
• Robust Orthogonal NMF with Label Propagation for Image Clustering [11.353489417171588]
  Non-negative clustering factorization (artNFMF) is a popular unsupervised learning approach widely used in image clustering.<n>We develop an alternating direction method which (AD)-based solutions to solve noise corruption.
  arXiv  Detail & Related papers  (2025-04-30T09:49:55Z)
• 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)
• An optimal pairwise merge algorithm improves the quality and consistency of nonnegative matrix factorization [0.0]
  Non-negative matrix factorization (NMF) is a key technique for feature extraction and widely used in source separation. Here we show that some of these weaknesses may be mitigated by performing NMF in a higher-dimensional feature space. Experimental results demonstrate our method helps non-ideal NMF solutions escape to better local optima.
  arXiv  Detail & Related papers  (2024-08-16T20:43:42Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization [2.646309221150203]
  We introduce a general second-order optimization framework for NMF under both quadratic and $beta$-divergence loss functions.<n>Second-Order Majorant (SOM) constructs a local quadratic majorization of the loss function by majorizing its Hessian matrix.<n>We show that mSOM consistently outperforms state-of-the-art algorithms across multiple loss functions.
  arXiv  Detail & Related papers  (2023-03-31T12:09:36Z)
• FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
  Many contemporary ML problems fall under nested bilevel programming that subsumes minimax and compositional optimization. We propose FedNest: A federated alternating gradient method to address general nested problems.
  arXiv  Detail & Related papers  (2022-05-04T17:48:55Z)
• 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)
• 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)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  Although model-agnostic metalearning (MAML) is a very successful algorithm meta-learning practice, it can have high computational complexity. Our paper shows that such complexity can significantly affect the overall convergence performance of ANIL.
  arXiv  Detail & Related papers  (2020-06-16T19:57:48Z)
• Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently [18.89597524771988]
  Non-negative matrix factorization (NMF) is a fundamental non-modification optimization problem with numerous applications in Machine Learning. This paper defines a multiplicative weight update type dynamics (Seung algorithm) that runs concurrently and provably avoids saddle points. An important advantage is the use concurrent implementations in parallel computing environments.
  arXiv  Detail & Related papers  (2020-02-26T06:40:23Z)

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.