Efficient and Non-Convex Coordinate Descent for Symmetric Nonnegative Matrix Factorization
| Autor: | Inderjit S. Dhillon, Qi Lei, Kai Zhong, Nicolas Gillis, Arnaud Vandaele |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Series (mathematics)
MathematicsofComputing_NUMERICALANALYSIS 020206 networking & telecommunications 02 engineering and technology Matrix decomposition Non-negative matrix factorization Combinatorics Quadratic equation Signal Processing 0202 electrical engineering electronic engineering information engineering Symmetric matrix 020201 artificial intelligence & image processing Nonnegative matrix Electrical and Electronic Engineering Coordinate descent Mathematics Sparse matrix |
| Zdroj: | IEEE Transactions on Signal Processing. 64:5571-5584 |
| ISSN: | 1941-0476 1053-587X |
| DOI: | 10.1109/tsp.2016.2591510 |
| Popis: | Given a symmetric nonnegative matrix $A$ , symmetric nonnegative matrix factorization (symNMF) is the problem of finding a nonnegative matrix $H$ , usually with much fewer columns than $A$ , such that $A \approx HH^T$ . SymNMF can be used for data analysis and in particular for various clustering tasks. Unlike standard NMF, which is traditionally solved by a series of quadratic (convex) subproblems, we propose to solve symNMF by directly solving the nonconvex problem, namely, minimize $\Vert A-HH^T\Vert ^2$ , which is a fourth-order nonconvex problem. In this paper, we propose simple and very efficient coordinate descent schemes, which solve a series of fourth-order univariate subproblems exactly. We also derive convergence guarantees for our methods and show that they perform favorably compared to recent state-of-the-art methods on synthetic and real-world datasets, especially on large and sparse input matrices. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|