Non-Negative Matrix Factorization Revisited: Uniqueness and Algorithm for Symmetric Decomposition
Top Cited Papers
- 11 October 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 62 (1), 211-224
- https://doi.org/10.1109/tsp.2013.2285514
Abstract
Non-negative matrix factorization (NMF) has found numerous applications, due to its ability to provide interpretable decompositions. Perhaps surprisingly, existing results regarding its uniqueness properties are rather limited, and there is much room for improvement in terms of algorithms as well. Uniqueness aspects of NMF are revisited here from a geometrical point of view. Both symmetric and asymmetric NMF are considered, the former being tantamount to element-wise non-negative square-root factorization of positive semidefinite matrices. New uniqueness results are derived, e.g., it is shown that a sufficient condition for uniqueness is that the conic hull of the latent factors is a superset of a particular second-order cone. Checking this condition is shown to be NP-complete; yet this and other results offer insights on the role of latent sparsity in this context. On the computational side, a new algorithm for symmetric NMF is proposed, which is very different from existing ones. It alternates between Procrustes rotation and projection onto the non-negative orthant to find a non-negative matrix close to the span of the dominant subspace. Simulation results show promising performance with respect to the state-of-art. Finally, the new algorithm is applied to a clustering problem for co-authorship data, yielding meaningful and interpretable results.Keywords
This publication has 35 references indexed in Scilit:
- Fast Nonnegative Matrix Factorization: An Active-Set-Like Method and ComparisonsSIAM Journal on Scientific Computing, 2011
- Generating All Vertices of a Polyhedron Is HardDiscrete & Computational Geometry, 2008
- Projected Gradient Methods for Nonnegative Matrix FactorizationNeural Computation, 2007
- Nonnegative matrix factorization with constrained second-order optimizationSignal Processing, 2007
- On the Equivalence of Nonnegative Matrix Factorization and Spectral ClusteringPublished by Society for Industrial & Applied Mathematics (SIAM) ,2005
- On reduced rank nonnegative matrix factorization for symmetric nonnegative matricesLinear Algebra and its Applications, 2004
- Convex OptimizationPublished by Cambridge University Press (CUP) ,2004
- On the convergence of the block nonlinear Gauss–Seidel method under convex constraintsOperations Research Letters, 2000
- On the complexity of four polyhedral set containment problemsMathematical Programming, 1985
- A generalized solution of the orthogonal procrustes problemPsychometrika, 1966