Abstract
Symmetric nonnegative matrix factorization (NMF), a special but important class of the general NMF, is demonstrated to be useful for data analysis and in particular for various clustering tasks. Unfortunately, designing fast algorithms for Symmetric NMF is not as easy as for the nonsymmetric counterpart, the latter admitting the splitting property that allows efficient alternating-type algorithms. To overcome this issue, we transfer the symmetric NMF to a nonsymmetric one, then we can adopt the idea from the state-of-the-art algorithms for nonsymmetric NMF to design fast algorithms solving symmetric NMF. We rigorously establish that solving nonsymmetric reformulation returns a solution for symmetric NMF and then apply fast alternating based algorithms for the corresponding reformulated problem. Furthermore, we show these fast algorithms admit strong convergence guarantee in the sense that the generated sequence is convergent at least at a sublinear rate and it converges globally to a critical point of the symmetric NMF. We conduct experiments on both synthetic data and image clustering to support our result.
Introduction
Nonnegative Matrix Factorization (NMF) is a staple in data science for tasks like topic modeling and face recognition. While standard NMF factorizes a matrix $Y$ into two different matrices $U$ and $V$, Symmetric NMF (SymNMF) deals with square, similarity matrices where we want $X \approx UU^T$. This is particularly powerful for graph clustering and kernel K-means.
The challenge is computational. Standard NMF is easy to solve because it has a "splitting property": if you fix $V$, the problem becomes a simple convex optimization for $U$, and vice versa. SymNMF lacks this because $U$ appears on both sides of the product. Consequently, researchers have been stuck using slow first-order methods (like gradient descent) or computationally heavy second-order methods that don't scale well to large datasets.
Methods
The authors propose a "symmetry-dropping" reformulation. Instead of forcing the factors to be identical from the start, they introduce two separate factors, $U$ and $V$, and solve:
$$\min_{U,V \ge 0} \frac{1}{2}\|X - UV^T\|_F^2 + \frac{\lambda}{2}\|U - V\|_F^2$$
Here, $\lambda$ is a balancing factor that encourages $U$ and $V$ to be the same. This simple change restores the "splitting property," allowing the authors to adapt two state-of-the-art NMF algorithms:
- SymANLS (Alternating Nonnegative Least Squares): Updates $U$ and $V$ by solving a sequence of nonnegative least squares problems.
- SymHALS (Hierarchical Alternating Least Squares): Updates the factors column-by-column with efficient closed-form solutions.
Crucially, the paper provides a theoretical proof that if $\lambda$ is large enough, any critical point of this new problem where $U$ and $V$ are "close" is actually a valid solution to the original symmetric problem ($U=V$).
Datasets and Evaluation
The authors evaluated their approach on five diverse datasets for image and text clustering:
- Synthetic Data: Randomly generated PSD matrices to verify convergence.
- ORL: 400 facial images of 40 different people.
- COIL-20: 1,440 images of 20 different objects.
- TDT2: A subset of 3,147 news articles across 30 categories.
- MNIST: The classic handwritten digits dataset (using subsets for training and testing).
- CBCL: A face image dataset used for convergence speed benchmarks.
Key Results
- Massive Speedup: In head-to-head tests against standard Projected Gradient Descent (PGD), the proposed methods converged orders of magnitude faster. As shown in Figure 1, the reformulated approach reaches an error of $10^{-15}$ while standard PGD remains stalled near $10^0$.
- Superior Efficiency: Compared to second-order methods (SymNewton) and ADMM, SymANLS and SymHALS reached high clustering accuracy much faster in terms of actual clock time, especially as the dataset size increased.
- Clustering Accuracy: The proposed methods achieved the highest accuracy on the ORL (80.75%) and COIL-20 (79.79%) datasets, outperforming traditional SymNMF solvers.
Key Insights and Ideas
- The Power of Relaxation: The core innovation is that by temporarily ignoring the symmetry constraint and penalizing the difference between $U$ and $V$, you gain access to a much faster class of algorithms.
- Theoretical Bridge: The authors proved that the reformulated problem's landscape preserves the critical points of the original SymNMF. This ensures that "dropping symmetry" doesn't lead the algorithm to a meaningless solution.
- Implicit Boundedness: Unlike previous attempts to use ADMM for SymNMF, which required adding artificial constraints to keep the variables from blowing up, the authors show that their formulation naturally keeps the iterates bounded.
Limitations and Future Work
The main limitation identified is the choice of the penalty parameter $\lambda$. While the paper provides a theoretical lower bound for $\lambda$ to guarantee $U=V$, experiments showed that the algorithms often work perfectly with much smaller values of $\lambda$ than the theory suggests. The authors suggest that their current theoretical bound is "stronger than necessary" and leave the task of finding a tighter, more practical bound for future research.
Summary updated