{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:21:02Z","timestamp":1760235662084,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T00:00:00Z","timestamp":1632096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100017530","name":"Major Scientific Project of Zhejiang Laboratory","doi-asserted-by":"publisher","award":["No.2019KB0AB01"],"award-info":[{"award-number":["No.2019KB0AB01"]}],"id":[{"id":"10.13039\/501100017530","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971430"],"award-info":[{"award-number":["11971430"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/sym13091757","type":"journal-article","created":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T22:35:20Z","timestamp":1632263720000},"page":"1757","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Two-Phase Algorithm for Robust Symmetric Non-Negative Matrix Factorization"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0294-4294","authenticated-orcid":false,"given":"Bingjie","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematics Science, Yuquan Campus, Zhejiang University, Hangzhou 310038, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xi","family":"Shi","sequence":"additional","affiliation":[{"name":"School of Mathematics Science, Yuquan Campus, Zhejiang University, Hangzhou 310038, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenyue","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Mathematics Science, Yuquan Campus, Zhejiang University, Hangzhou 310038, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1038\/44565","article-title":"Learning the parts of objects by non-negative matrix factorization","volume":"401","author":"Lee","year":"1999","journal-title":"Nature"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1016\/j.patrec.2004.02.002","article-title":"Non-negative matrix factorization based methods for object recognition","volume":"25","author":"Liu","year":"2004","journal-title":"Pattern Recognit. Lett."},{"key":"ref_3","unstructured":"David, G., and Jordi, V. (2002, January 24\u201325). Non-negative Matrix Factorization for Face Recognition. Proceedings of the 5th Catalonian Conference on AI: Topics in Artificial Intelligence, Castell\u00f3n, Spain."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Zdunek, R., and Cichocki, A. (2006, January 25\u201329). Non-negative Matrix Factorization with Quasi-Newton Optimization. Proceedings of the Artificial Intelligence and Soft Computing, Zakopane, Poland.","DOI":"10.1007\/11785231_91"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/JSTARS.2012.2194696","article-title":"Hyperspectral Unmixing Overview: Geometrical, Statistical, and Sparse Regression-Based Approaches","volume":"5","author":"Jose","year":"2012","journal-title":"IEEE J. Sel. Top. Appl. Earth Obs. Remote Sens."},{"key":"ref_6","first-page":"1457","article-title":"Non-Negative Matrix Factorization with Sparseness Constraints","volume":"5","author":"Hoyer","year":"2004","journal-title":"J. Mach. Learn. Res."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Ding, C., Li, T., Peng, W., and Park, H. (2006, January 20\u201323). Orthogonal nonnegative matrix t-factorizations for clustering. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA.","DOI":"10.1145\/1150402.1150420"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1109\/TPAMI.2010.231","article-title":"Graph Regularized Nonnegative Matrix Factorization for Data Representation","volume":"33","author":"Cai","year":"2011","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1336","DOI":"10.1109\/TKDE.2012.51","article-title":"Nonnegative Matrix Factorization: A Comprehensive Review","volume":"25","author":"Wang","year":"2013","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Esposito, F. (2021). A Review on Initialization Methods for Nonnegative Matrix Factorization: Towards Omics Data Experiments. Mathematics, 9.","DOI":"10.3390\/math9091006"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0895-7177(93)90202-A","article-title":"A survey of fuzzy clustering","volume":"18","author":"Yang","year":"1993","journal-title":"Math. Comput. Model."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Zass, R., and Shashua, A. (2005, January 17\u201321). A unifying approach to hard and probabilistic clustering. Proceedings of the IEEE International Conference on Computer Vision, Beijing, China.","DOI":"10.1109\/ICCV.2005.27"},{"key":"ref_13","unstructured":"Raviteja, V., Kim, \u00d8.R., Gopinath, C., and Boian, A. (2021, January 12). Determination of the number of clusters by symmetric non-negative matrix factorization. Proceedings of the Big Data III: Learning, Analytics, and Applications, Online."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s10898-014-0247-2","article-title":"SymNMF: Nonnegative low-rank approximation of a similarity matrix for graph clustering","volume":"62","author":"Kuang","year":"2015","journal-title":"J. Glob. Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.ymeth.2016.06.017","article-title":"Hessian Regularization Based Symmetric Nonnegative Matrix Factorization for Clustering Gene Expression and Microbiome Data","volume":"111","author":"Ma","year":"2016","journal-title":"Methods"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in PCM","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","first-page":"513","article-title":"Principal Component Analysis","volume":"87","author":"Jolliffe","year":"2002","journal-title":"J. Mark. Res."},{"key":"ref_18","unstructured":"Ng, A.Y., Jordan, M.I., and Weiss, Y. (2001, January 14). On Spectral Clustering: Analysis and an Algorithm. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2117","DOI":"10.1109\/TNN.2011.2172457","article-title":"Symmetric Nonnegative Matrix Factorization: Algorithms and Applications to Probabilistic Clustering","volume":"22","author":"He","year":"2011","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Wang, P., He, Z., Lu, J., Tan, B., Bai, Y., Tan, J., Liu, T., and Lin, Z. (2020). An Accelerated Symmetric Nonnegative Matrix Factorization Algorithm Using Extrapolation. Symmetry, 12.","DOI":"10.3390\/sym12071187"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","article-title":"Coordinate Descent Algorithms","volume":"151","author":"Wright","year":"2015","journal-title":"Math. Program."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"5571","DOI":"10.1109\/TSP.2016.2591510","article-title":"Efficient and Non-Convex Coordinate Descent for Symmetric Nonnegative Matrix Factorization","volume":"64","author":"Vandaele","year":"2016","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"5995","DOI":"10.1109\/TSP.2017.2731321","article-title":"Inexact Block Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization","volume":"65","author":"Shi","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_24","unstructured":"Zhu, Z., Li, X., Liu, K., and Li, Q. (2018). Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization. arXiv."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/0041-5553(69)90035-4","article-title":"The conjugate gradient method in extremal problems","volume":"9","author":"Polyak","year":"1969","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"ref_26","unstructured":"Nocedal, J., and Wright, S. (2006). Numerical Optimization, Springer Science & Business Media."},{"key":"ref_27","unstructured":"Zhang, Z., and Li, B. (2021). Exterior Point Method for Completely Positive Factorization. arXiv."},{"key":"ref_28","unstructured":"Sun, W., and Yuan, Y. (2006). Optimization Theory and Methods: Nonlinear Programming, Springer Science & Business Media."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kuang, D., Ding, C., and Park, H. (2012, January 26\u201328). Symmetric Nonnegative Matrix Factorization for Graph Clustering. Proceedings of the 2012 SIAM International Conference on Data Mining (SDM), Anaheim, CA, USA.","DOI":"10.1137\/1.9781611972825.10"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF02592073","article-title":"Projected gradient methods for linearly constrained problems","volume":"39","author":"Calamai","year":"1987","journal-title":"Math. Program."},{"key":"ref_31","unstructured":"Razaviyayn, M., Hong, M., Luo, Z.Q., and Pang, J.S. (2014, January 8\u201313). Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization. Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada."},{"key":"ref_32","unstructured":"Shaked-Monderer, N., and Berman, A. (2021). Copositive and Completely Positive Matrices, World Scienfic."},{"key":"ref_33","unstructured":"Nene, S., Nayar, S., and Murase, H. (1996). Columbia Object Image Library (COIL-20), Columbia University. Tech. Rep. CUCS-005-96."},{"key":"ref_34","unstructured":"Samaria, F., and Harter, A. (1994, January 5\u20137). Parameterisation of a stochastic model for human face identification. Proceedings of the Second IEEE Workshop on Applications of Computer Vision, Sarasota, FL, USA."},{"key":"ref_35","unstructured":"Sim, T., Baker, S., and Bsat, M. (2002, January 20\u201321). The CMU Pose, Illumination, and Expression (PIE) database. Proceedings of the Fifth IEEE International Conference on Automatic Face Gesture Recognition, Washinton, DC, USA."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Fiscus, J., Doddington, G., Garofolo, J., and Alvin, M. (March, January 28). NIST\u2019s 1998 Topic Detection and Tracking evaluation (TDT2). Proceedings of the 1999 DARPA Broadcast News Workshop, Herndon, VA, USA.","DOI":"10.21437\/Eurospeech.1999-65"},{"key":"ref_37","unstructured":"Zelnik-Manor, L., and Perona, P. (2004, January 13\u201318). Self-Tuning Spectral Clustering. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A Tutorial on Spectral Clustering","volume":"17","author":"Luxburg","year":"2004","journal-title":"Stat. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"6348","DOI":"10.1109\/TNNLS.2018.2830761","article-title":"Pairwise Constraint Propagation-Induced Symmetric Nonnegative Matrix Factorization","volume":"29","author":"Wu","year":"2018","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Eswar, S., Hayashi, K., Ballard, G., Kannan, R., Vuduc, R., and Park, H. (2020, January 9\u201319). Distributed-Memory Parallel Symmetric Nonnegative Matrix Factorization. Proceedings of the SC20: The International Conference for High Performance Computing, Networking, Storage and Analysis, Atlanta, GA, USA.","DOI":"10.1109\/SC41405.2020.00078"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/9\/1757\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:02:29Z","timestamp":1760166149000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/9\/1757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,20]]},"references-count":40,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2021,9]]}},"alternative-id":["sym13091757"],"URL":"https:\/\/doi.org\/10.3390\/sym13091757","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2021,9,20]]}}}