# Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization

arXiv: https://arxiv.org/abs/1410.7220 · HTML: https://mlsanity.com/paper/1410.7220/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2014.

## Built on by (most cited first, 9 of 9)

- [Archetypal SAE: Adaptive and Stable Dictionary Learning for Concept Extraction in Large Vision Models](https://mlsanity.com/paper/2502.12892/) (2025)
- [Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications](https://mlsanity.com/paper/2209.12638/) (2022)
- [Quadratic Matrix Factorization with Applications to Manifold Learning](https://mlsanity.com/paper/2301.12965/) (2023)
- [Dual Simplex Volume Maximization for Simplex-Structured Matrix Factorization](https://mlsanity.com/paper/2403.20197/) (2024)
- [Subspace-Constrained Quadratic Matrix Factorization: Algorithm and Applications](https://mlsanity.com/paper/2411.04717/) (2024)
- [Disentangling Latent Embeddings with Sparse Linear Concept Subspaces (SLiCS)](https://mlsanity.com/paper/2508.20322/) (2025)
- [Time series forecasting from partial observations via Non-negative Matrix Factorization](https://mlsanity.com/paper/2102.05314/) (2021)
- [Probabilistic semi-nonnegative matrix factorization: a Skellam-based framework](https://mlsanity.com/paper/2107.03317/) (2021)
- [Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Condition](https://mlsanity.com/paper/2511.04291/) (2025)

## Abstract (arXiv)

Given a matrix M (not necessarily nonnegative) and a factorization rank r, semi-nonnegative matrix factorization (semi-NMF) looks for a matrix U with r columns and a nonnegative matrix V with r rows such that UV is the best possible approximation of M according to some metric. In this paper, we study the properties of semi-NMF from which we develop exact and heuristic algorithms. Our contribution is threefold. First, we prove that the error of a semi-NMF of rank r has to be smaller than the best unconstrained approximation of rank r-1. This leads us to a new initialization procedure based on the singular value decomposition (SVD) with a guarantee on the quality of the approximation. Second, we propose an exact algorithm (that is, an algorithm that finds an optimal solution), also based on the SVD, for a certain class of matrices (including nonnegative irreducible matrices) from which we derive an initialization for matrices not belonging to that class. Numerical experiments illustrate that this second approach performs extremely well, and allows us to compute optimal semi-NMF decompositions in many situations. Finally, we analyze the computational complexity of semi-NMF proving its NP-hardness, already in the rank-one case (that is, for r = 1), and we show that semi-NMF is sometimes ill-posed (that is, an optimal solution does not exist).