Separable Nonnegative Matrix Factorization Using Powered Ratio-of-Norms Regularization
Machine Learning
Summary
The authors focus on improving a method called separable nonnegative matrix factorization (SNMF), which helps break down data into easy-to-understand parts and is useful for tasks like clustering. They introduce a new way to make the factors sparser and easier to identify by using a special type of regularization. Because their new model is mathematically tricky to solve, they design efficient algorithms to handle it and prove these algorithms work well. Testing on synthetic data and hand gesture recognition shows their approach performs as well or better than existing methods while being computationally efficient.
Authors
Matthew McCarver, Jing Qin
Abstract
Separable nonnegative matrix factorization (SNMF) has been widely used for low-rank representation and clustering of nonnegative data, owing to its ability to produce part-based and interpretable decompositions. In particular, SNMF is closely related to graph clustering and community detection. To enhance sparsity and identifiability of the learned factors, we propose an $\ell_1^p/\ell_2$-regularized SNMF model based on a powered ratio-of-norms regularizer. The resulting formulation is nonconvex and nonsmooth, which poses significant challenges for optimization. To address this, we develop efficient algorithms based on the difference-of-convex function algorithm (DCA) and the alternating direction method of multipliers (ADMM). The proposed methods decompose the original problem into tractable subproblems, leveraging closed-form proximal operators associated with the powered norm terms. We establish descent and limiting criticality properties for the DCA scheme and convergence under standard assumptions for the ADMM scheme. Extensive numerical experiments on synthetic datasets and hand gesture classification tasks demonstrate that the proposed approach achieves competitive or improved performance in anchor identification and classification accuracy compared with existing SNMF methods, while maintaining competitive computational efficiency.