A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality

Songtao Lu; Mingyi Hong; Zhengdao Wang

doi:10.1109/ICASSP.2017.7952621

A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality

Songtao Lu
, Mingyi Hong
, Zhengdao Wang

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

Symmetric non-negative matrix factorization (SymNMF) has important applications in data analytics problems such as document clustering, community detection and image segmentation. In this paper, we propose a novel nonconvex variable splitting method for solving SymNMF. Different from the existing works, we prove that the algorithm converges to the set of Karush-Kuhn-Tucker (KKT) points of the nonconvex SymNMF problem with a global sublinear convergence rate. We also show that the algorithm can be efficiently implemented in a distributed manner. Further, we provide sufficient conditions that guarantee the global and local optimality of the obtained solutions. Extensive numerical results performed on both synthetic and real data sets suggest that the proposed algorithm yields high quality of the solutions and converges quickly to the set of local minimum solutions compared with other algorithms.

Original language	English (US)
Title of host publication	2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2572-2576
Number of pages	5
ISBN (Electronic)	9781509041176
DOIs	https://doi.org/10.1109/ICASSP.2017.7952621
State	Published - Jun 16 2017
Event	2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - New Orleans, United States Duration: Mar 5 2017 → Mar 9 2017

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)	1520-6149

Other

Other	2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017
Country/Territory	United States
City	New Orleans
Period	3/5/17 → 3/9/17

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Keywords

Karush-Kuhn-Tucker points
Symmetric Nonnegative Matrix Factorization
clustering
global and local optimality
variable splitting

Publisher link

10.1109/ICASSP.2017.7952621

https://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1159&context=ece_pubs

Find It

Find It at U of M Libraries

Cite this

Lu, S., Hong, M., & Wang, Z. (2017). A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality. In 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings (pp. 2572-2576). Article 7952621 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2017.7952621

A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality. / Lu, Songtao; Hong, Mingyi; Wang, Zhengdao.
2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. p. 2572-2576 7952621 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lu, S, Hong, M & Wang, Z 2017, A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality. in 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings., 7952621, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 2572-2576, 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017, New Orleans, United States, 3/5/17. https://doi.org/10.1109/ICASSP.2017.7952621

Lu S, Hong M, Wang Z. A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality. In 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2017. p. 2572-2576. 7952621. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2017.7952621

Lu, Songtao ; Hong, Mingyi ; Wang, Zhengdao. / A nonconvex splitting method for symmetric nonnegative matrix factorization : Convergence analysis and optimality. 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 2572-2576 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{108e7b3a5bbe405b9544c22353391745,

title = "A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality",

abstract = "Symmetric non-negative matrix factorization (SymNMF) has important applications in data analytics problems such as document clustering, community detection and image segmentation. In this paper, we propose a novel nonconvex variable splitting method for solving SymNMF. Different from the existing works, we prove that the algorithm converges to the set of Karush-Kuhn-Tucker (KKT) points of the nonconvex SymNMF problem with a global sublinear convergence rate. We also show that the algorithm can be efficiently implemented in a distributed manner. Further, we provide sufficient conditions that guarantee the global and local optimality of the obtained solutions. Extensive numerical results performed on both synthetic and real data sets suggest that the proposed algorithm yields high quality of the solutions and converges quickly to the set of local minimum solutions compared with other algorithms.",

keywords = "Karush-Kuhn-Tucker points, Symmetric Nonnegative Matrix Factorization, clustering, global and local optimality, variable splitting",

author = "Songtao Lu and Mingyi Hong and Zhengdao Wang",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 ; Conference date: 05-03-2017 Through 09-03-2017",

year = "2017",

month = jun,

day = "16",

doi = "10.1109/ICASSP.2017.7952621",

language = "English (US)",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2572--2576",

booktitle = "2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings",

}

TY - GEN

T1 - A nonconvex splitting method for symmetric nonnegative matrix factorization

T2 - 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017

AU - Lu, Songtao

AU - Hong, Mingyi

AU - Wang, Zhengdao

PY - 2017/6/16

Y1 - 2017/6/16

N2 - Symmetric non-negative matrix factorization (SymNMF) has important applications in data analytics problems such as document clustering, community detection and image segmentation. In this paper, we propose a novel nonconvex variable splitting method for solving SymNMF. Different from the existing works, we prove that the algorithm converges to the set of Karush-Kuhn-Tucker (KKT) points of the nonconvex SymNMF problem with a global sublinear convergence rate. We also show that the algorithm can be efficiently implemented in a distributed manner. Further, we provide sufficient conditions that guarantee the global and local optimality of the obtained solutions. Extensive numerical results performed on both synthetic and real data sets suggest that the proposed algorithm yields high quality of the solutions and converges quickly to the set of local minimum solutions compared with other algorithms.

AB - Symmetric non-negative matrix factorization (SymNMF) has important applications in data analytics problems such as document clustering, community detection and image segmentation. In this paper, we propose a novel nonconvex variable splitting method for solving SymNMF. Different from the existing works, we prove that the algorithm converges to the set of Karush-Kuhn-Tucker (KKT) points of the nonconvex SymNMF problem with a global sublinear convergence rate. We also show that the algorithm can be efficiently implemented in a distributed manner. Further, we provide sufficient conditions that guarantee the global and local optimality of the obtained solutions. Extensive numerical results performed on both synthetic and real data sets suggest that the proposed algorithm yields high quality of the solutions and converges quickly to the set of local minimum solutions compared with other algorithms.

KW - Karush-Kuhn-Tucker points

KW - Symmetric Nonnegative Matrix Factorization

KW - clustering

KW - global and local optimality

KW - variable splitting

UR - https://www.scopus.com/pages/publications/85023773751

UR - https://www.scopus.com/pages/publications/85023773751#tab=citedBy

U2 - 10.1109/ICASSP.2017.7952621

DO - 10.1109/ICASSP.2017.7952621

M3 - Conference contribution

AN - SCOPUS:85023773751

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 2572

EP - 2576

BT - 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 5 March 2017 through 9 March 2017

ER -

A nonconvex splitting method for symmetric nonnegative matrix factorization: Convergence analysis and optimality

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this