Source-linked AI summary
Two Algorithms for Orthogonal Nonnegative Matrix Factorization with Application to Clustering
Filippo Pompili, Nicolas Gillis, P. -A. Absil, François Glineur
TL;DR
ONMF requires methods that handle nonnegativity and orthogonality while supporting clustering applications. This paper derives an EM-like algorithm from a weighted spherical k-means equivalence and proposes ONP-MF, which reverses the usual constraint-enforcement strategy; experiments report strong robustness and performance, especially for image data.
Problem
ONMF combines nonnegativity and orthogonality for clustering, but existing methods enforce nonnegativity iteratively while only approaching orthogonality at the limit.
Method
The paper introduces EM-ONMF from an equivalence with weighted spherical k-means and ONP-MF, an augmented-Lagrangian method enforcing orthogonality at each step while relaxing nonnegativity.
Results
ONP-MF was the most robust tested Euclidean ONMF algorithm, giving very good results with one initialization and outperforming other algorithms in all image experiments.
Takeaways & Limitations
ONP-MF's orthogonality-first strategy permits initialization with unaltered right singular vectors, which the paper links to its observed clustering performance.
Takeaways & Limitations
The evaluation focuses on Frobenius-norm ONMF; comparisons with other divergences and topic models such as LDA remain future work.
Abstract
from arXiv · showhide
Approximate matrix factorization techniques with both nonnegativity and orthogonality constraints, referred to as orthogonal nonnegative matrix factorization (ONMF), have been recently introduced and shown to work remarkably well for clustering tasks such as document classification. In this paper, we introduce two new methods to solve ONMF. First, we show athematical equivalence between ONMF and a weighted variant of spherical k-means, from which we derive our first method, a simple EM-like algorithm. This also allows us to determine when ONMF should be preferred to k-means and spherical k-means. Our second method is based on an augmented Lagrangian approach. Standard ONMF algorithms typically enforce nonnegativity for their iterates while trying to achieve orthogonality at the limit (e.g., using a proper penalization term or a suitably chosen search direction). Our method works the opposite way: orthogonality is strictly imposed at each step while nonnegativity is asymptotically obtained, using a quadratic penalty. Finally, we show that the two proposed approaches compare favorably with standard ONMF algorithms on synthetic, text and image data sets.
1 Introduction
ONMF combines nonnegative matrix factorization with orthogonality, yielding a clustering interpretation in which data columns are assigned to factor directions. The paper introduces an EM-like method from its equivalence to weighted spherical k-means and an augmented-Lagrangian method that reverses how the constraints are enforced.
- Problem formulation: ONMF factors a nonnegative data matrix under nonnegativity and orthogonality constraints, extending standard NMF.The orthogonality constraint considerably changes the problem's nature.
- Clustering interpretation: Orthogonality makes each column of V have at most one nonzero entry, assigning each data column to a factor direction.The corresponding column of U minimizes its angle with the data column, while the nonzero entry in V provides Euclidean scaling.
- Clustering interpretation: This structure connects ONMF to data clustering, with empirical evidence that orthogonality can improve clustering over standard NMF or k-means.
- Prior methods: Existing ONMF methods maintain nonnegativity during iterations but only approach orthogonality at the limit, and different runs can return different local solutions.The problem may have multiple local minima, so methods differ in both computational cost and clustering quality.
- Contributions: The paper derives an EM-like algorithm from equivalence with weighted spherical k-means and proposes ONP-MF, which enforces orthogonality during iterations while obtaining nonnegativity at the limit.The paper also analyzes when ONMF should be preferred to k-means and spherical k-means.
2 Equivalence of ONMF with a Weighted Variant of Spherical k-means
ONMF is equivalent to a weighted variant of spherical k-means, clarifying how its orthogonality and nonnegativity constraints determine clustering behavior. This equivalence motivates an EM-like solver and identifies settings where ONMF is preferable to k-means or standard spherical k-means.
- ONMF is equivalent to a weighted variant of spherical k-means in a particular metric.
- ONMF differs from spherical k-means because it weights points by their norms, whereas spherical k-means depends only on direction.Even with normalized points, ONMF maximizes a sum of squared cosines rather than the sum of cosines.
- ONMF should be preferred when scaling should not change assignments and larger-norm points are more reliable or deserve greater importance.Spherical k-means is invariant to normalization, while ONMF gives more importance to larger-norm data points.
- On synthetic data sets, ONMF outperforms k-means and spherical k-means in average clustering accuracy.The comparison uses ten synthetic data sets per noise level and ten random initializations, while ONMF is solved with ONP-MF without random initialization.
- The proposed EM-ONMF algorithm alternates between assigning points to clusters and computing optimal nonnegative cluster centroids.Its centroid-update subproblems are nonnegative rank-one approximation problems, and the method is based on the weighted spherical k-means equivalence.
3 Augmented Lagrangian Method for ONMF
The augmented-Lagrangian approach reverses the usual ONMF strategy: it enforces orthogonality during the iterations while driving V toward nonnegativity through a quadratic penalty. ONP-MF alternates constrained updates and exhibits decreasing constraint violations, although rigorous convergence remains open.
- ONP-MF enforces orthogonality of V at every iteration while obtaining nonnegativity asymptotically.This reverses standard methods, which enforce nonnegativity throughout and seek orthogonality only at the limit.
- The augmented Lagrangian handles nonnegativity violations through a quadratic penalty on the negative entries of V.The penalty parameter is ρ, and the formulation uses min(V, 0) to measure violations.
- The alternating scheme updates U by nonnegative least squares, V by projected gradient on the Stiefel manifold, and Λ by a gradient step.The V projection is computed from the unitary factor of a polar decomposition, while Λ uses α = α0/t.
- ONP-MF initializes Λ at zero, uses the first k right singular vectors of M for V, and increases ρ geometrically.The algorithm takes a nonnegative data matrix, cluster count k, and positive parameters α0, ρ0, and C as inputs.
- The negative-part residual decreases linearly to zero while the approximation error converges to a fixed value on the Hubble data set.Figure 3 reports constraint residual on the left and approximation error on the right.
- A rigorous convergence proof is left open because the augmented-Lagrangian subproblems are solved inexactly.The implementation uses a single loop of block coordinate descent rather than solving each subproblem exactly.
4 Numerical Experiments
The experiments compare ONMF algorithms on synthetic, text, and image data, using accuracy, computational time, and factorization quality. The proposed methods often perform competitively, with performance varying by dataset and method.
- Synthetic Data Sets: ONP-MF and O-P(SVD) perform best on synthetic data and perfectly identify all clusters at noise level ǫ = 0.01.CHNMF, O-PNMF, and CH(SVD) generally achieve lower accuracies, while EM-ONMF is faster but clusters poorly.
- Synthetic Data Sets: ONP-MF is slightly slower but typically obtains one of the best synthetic-data factorizations with a single deterministic execution.Its deterministic behavior follows from SVD initialization.
- Text Clustering: Across twelve text data sets, the proposed algorithms achieve the best performance among ONMF methods on ten data sets and obtain the best average result on more than half.EM-ONMF is very fast, whereas ONP-MF is generally slower and typically requires more iterations to converge.
- Scope: The study focuses on ONMF algorithms using the Frobenius norm and leaves comparisons with other divergences and topic models for future research.The paper notes that this metric assumes Gaussian noise and that documents may contain mixtures of topics.
- Hyperspectral Unmixing: On the clean Hubble hyperspectral data, ONP-MF is the only tested algorithm reported to recover all eight materials almost perfectly without mixing.On Urban data, ONP-MF extracts grass, trees, roofs, and metal, but mixes road and dirt, whose spectral signatures are similar.
- Experimental Protocol: The reported experiments retain the best solution among repeated random initializations, while ONP-MF uses deterministic SVD initialization.Image experiments display the lowest-error solution, and synthetic experiments use ten repetitions for the relevant comparisons.
5 Conclusion
The paper proposes EM-ONMF and ONP-MF for orthogonal nonnegative matrix factorization, while noting important limitations of Euclidean ONMF for document classification. Experiments on synthetic, text, and image data indicate that ONP-MF is especially robust and effective in image experiments.
- The paper formulates ONMF as equivalent to a weighted variant of spherical k-means and proposes EM-ONMF.
- ONP-MF uses an augmented Lagrangian method that imposes orthogonality at each step while relaxing nonnegativity.
- Euclidean ONMF is not particularly suited for document classification because Frobenius-norm Gaussian-noise assumptions and single-topic documents are unrealistic limitations.
- ONP-MF was the most robust tested algorithm, producing very good results with only one initialization and the best results in many cases.
- Across all image experiments, one deterministic ONP-MF run outperformed other tested algorithms despite their access to 30 random initializations.