A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization
As a special class of non-negative matrix factorization, symmetric non-negative matrix factorization (SymNMF) has been widely used in the machine learning field to mine the hidden non-linear structure of data. Due to the non-negative constraint and non-convexity of SymNMF, the efficiency of existing...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-09-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/13/9/1757 |
| _version_ | 1797517040350658560 |
|---|---|
| author | Bingjie Li Xi Shi Zhenyue Zhang |
| author_facet | Bingjie Li Xi Shi Zhenyue Zhang |
| author_sort | Bingjie Li |
| collection | DOAJ |
| description | As a special class of non-negative matrix factorization, symmetric non-negative matrix factorization (SymNMF) has been widely used in the machine learning field to mine the hidden non-linear structure of data. Due to the non-negative constraint and non-convexity of SymNMF, the efficiency of existing methods is generally unsatisfactory. To tackle this issue, we propose a two-phase algorithm to solve the SymNMF problem efficiently. In the first phase, we drop the non-negative constraint of SymNMF and propose a new model with penalty terms, in order to control the negative component of the factor. Unlike previous methods, the factor sequence in this phase is not required to be non-negative, allowing fast unconstrained optimization algorithms, such as the conjugate gradient method, to be used. In the second phase, we revisit the SymNMF problem, taking the non-negative part of the solution in the first phase as the initial point. To achieve faster convergence, we propose an interpolation projected gradient (IPG) method for SymNMF, which is much more efficient than the classical projected gradient method. Our two-phase algorithm is easy to implement, with convergence guaranteed for both phases. Numerical experiments show that our algorithm performs better than others on synthetic data and unsupervised clustering tasks. |
| first_indexed | 2024-03-10T07:10:14Z |
| format | Article |
| id | doaj.art-0b93a14d932a4d6ea8c6dfa4dfbd5e96 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T07:10:14Z |
| publishDate | 2021-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-0b93a14d932a4d6ea8c6dfa4dfbd5e962023-11-22T15:29:34ZengMDPI AGSymmetry2073-89942021-09-01139175710.3390/sym13091757A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix FactorizationBingjie Li0Xi Shi1Zhenyue Zhang2School of Mathematics Science, Yuquan Campus, Zhejiang University, Hangzhou 310038, ChinaSchool of Mathematics Science, Yuquan Campus, Zhejiang University, Hangzhou 310038, ChinaSchool of Mathematics Science, Yuquan Campus, Zhejiang University, Hangzhou 310038, ChinaAs a special class of non-negative matrix factorization, symmetric non-negative matrix factorization (SymNMF) has been widely used in the machine learning field to mine the hidden non-linear structure of data. Due to the non-negative constraint and non-convexity of SymNMF, the efficiency of existing methods is generally unsatisfactory. To tackle this issue, we propose a two-phase algorithm to solve the SymNMF problem efficiently. In the first phase, we drop the non-negative constraint of SymNMF and propose a new model with penalty terms, in order to control the negative component of the factor. Unlike previous methods, the factor sequence in this phase is not required to be non-negative, allowing fast unconstrained optimization algorithms, such as the conjugate gradient method, to be used. In the second phase, we revisit the SymNMF problem, taking the non-negative part of the solution in the first phase as the initial point. To achieve faster convergence, we propose an interpolation projected gradient (IPG) method for SymNMF, which is much more efficient than the classical projected gradient method. Our two-phase algorithm is easy to implement, with convergence guaranteed for both phases. Numerical experiments show that our algorithm performs better than others on synthetic data and unsupervised clustering tasks.https://www.mdpi.com/2073-8994/13/9/1757symmetric non-negative matrix factorizationlow-rank approximationnon-linear conjugate gradient methodprojected gradient methoddata clustering |
| spellingShingle | Bingjie Li Xi Shi Zhenyue Zhang A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization Symmetry symmetric non-negative matrix factorization low-rank approximation non-linear conjugate gradient method projected gradient method data clustering |
| title | A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization |
| title_full | A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization |
| title_fullStr | A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization |
| title_full_unstemmed | A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization |
| title_short | A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization |
| title_sort | two phase algorithm for robust symmetric non negative matrix factorization |
| topic | symmetric non-negative matrix factorization low-rank approximation non-linear conjugate gradient method projected gradient method data clustering |
| url | https://www.mdpi.com/2073-8994/13/9/1757 |
| work_keys_str_mv | AT bingjieli atwophasealgorithmforrobustsymmetricnonnegativematrixfactorization AT xishi atwophasealgorithmforrobustsymmetricnonnegativematrixfactorization AT zhenyuezhang atwophasealgorithmforrobustsymmetricnonnegativematrixfactorization AT bingjieli twophasealgorithmforrobustsymmetricnonnegativematrixfactorization AT xishi twophasealgorithmforrobustsymmetricnonnegativematrixfactorization AT zhenyuezhang twophasealgorithmforrobustsymmetricnonnegativematrixfactorization |