An Exterior Method for Nonnegative Matrix Factorization

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

Many machine learning tasks require finding structured and interpretable patterns in large datasets, such as images, text, audio, and recommendation data. Nonnegative matrix factorization is a common method for finding these patterns, but existing methods can be slow and may not always find the best solution. This paper introduces eNMF, a new method that first finds the dominant patterns in the data and then adjusts them so that all values are nonnegative. This approach makes the search process easier and more effective. Across synthetic and real-world datasets, eNMF finds better summaries of the original data and does so faster than several standard methods. These improved patterns also help with practical tasks such as face recognition, audio digit classification, and recommendation. Overall, eNMF provides a faster and more reliable way to find interpretable patterns in nonnegative data.