Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis

Davood Hajinezhad; Tsung Hui Chang; Xiangfeng Wang; Qingjiang Shi; Mingyi Hong

doi:10.1109/ICASSP.2016.7472577

Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis

Davood Hajinezhad, Tsung Hui Chang, Xiangfeng Wang, Qingjiang Shi, Mingyi Hong

Electrical and Computer Engineering

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

25 Scopus citations

Abstract

The nonnegative matrix factorization (NMF) has been a popular model for a wide range of signal processing and machine learning problems. It is usually formulated as a nonconvex cost minimization problem. This work settles the convergence issue of a popular algorithm based on the alternating direction method of multipliers proposed in Boyd et al 2011. We show that the algorithm converges globally to the set of KKT solutions whenever certain penalty parameter ρ satisfies ρ > 1. We further extend the algorithm and its analysis to the problem where the observation matrix contains missing values. Numerical experiments on real and synthetic data sets demonstrate the effectiveness of the algorithms under investigation.

Original language	English (US)
Title of host publication	2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4742-4746
Number of pages	5
ISBN (Electronic)	9781479999880
DOIs	https://doi.org/10.1109/ICASSP.2016.7472577
State	Published - May 18 2016
Event	41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Shanghai, China Duration: Mar 20 2016 → Mar 25 2016

Publication series

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

Other

Other	41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016
Country	China
City	Shanghai
Period	3/20/16 → 3/25/16

Keywords

ADMM
Convergence Analysis
Nonconvex Optimization
Nonnegative Matrix Factorization

Access

10.1109/ICASSP.2016.7472577

Fingerprint Dive into the research topics of 'Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis'. Together they form a unique fingerprint.

Cite this

Hajinezhad, D., Chang, T. H., Wang, X., Shi, Q., & Hong, M. (2016). Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings (pp. 4742-4746). [7472577] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2016-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2016.7472577

Nonnegative matrix factorization using ADMM : Algorithm and convergence analysis. / Hajinezhad, Davood; Chang, Tsung Hui; Wang, Xiangfeng; Shi, Qingjiang; Hong, Mingyi.

2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2016. p. 4742-4746 7472577 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2016-May).

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

Hajinezhad, D, Chang, TH, Wang, X, Shi, Q & Hong, M 2016, Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis. in 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings., 7472577, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2016-May, Institute of Electrical and Electronics Engineers Inc., pp. 4742-4746, 41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016, Shanghai, China, 3/20/16. https://doi.org/10.1109/ICASSP.2016.7472577

Hajinezhad D, Chang TH, Wang X, Shi Q, Hong M. Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2016. p. 4742-4746. 7472577. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2016.7472577

Hajinezhad, Davood ; Chang, Tsung Hui ; Wang, Xiangfeng ; Shi, Qingjiang ; Hong, Mingyi. / Nonnegative matrix factorization using ADMM : Algorithm and convergence analysis. 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 4742-4746 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{9d4ffe46b6dc4d4db4a7c916d2032c2b,

title = "Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis",

abstract = "The nonnegative matrix factorization (NMF) has been a popular model for a wide range of signal processing and machine learning problems. It is usually formulated as a nonconvex cost minimization problem. This work settles the convergence issue of a popular algorithm based on the alternating direction method of multipliers proposed in Boyd et al 2011. We show that the algorithm converges globally to the set of KKT solutions whenever certain penalty parameter ρ satisfies ρ > 1. We further extend the algorithm and its analysis to the problem where the observation matrix contains missing values. Numerical experiments on real and synthetic data sets demonstrate the effectiveness of the algorithms under investigation.",

keywords = "ADMM, Convergence Analysis, Nonconvex Optimization, Nonnegative Matrix Factorization",

author = "Davood Hajinezhad and Chang, {Tsung Hui} and Xiangfeng Wang and Qingjiang Shi and Mingyi Hong",

year = "2016",

month = may,

day = "18",

doi = "10.1109/ICASSP.2016.7472577",

language = "English (US)",

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

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

pages = "4742--4746",

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

note = "41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016 ; Conference date: 20-03-2016 Through 25-03-2016",

}

TY - GEN

T1 - Nonnegative matrix factorization using ADMM

T2 - 41st IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2016

AU - Hajinezhad, Davood

AU - Chang, Tsung Hui

AU - Wang, Xiangfeng

AU - Shi, Qingjiang

AU - Hong, Mingyi

PY - 2016/5/18

Y1 - 2016/5/18

N2 - The nonnegative matrix factorization (NMF) has been a popular model for a wide range of signal processing and machine learning problems. It is usually formulated as a nonconvex cost minimization problem. This work settles the convergence issue of a popular algorithm based on the alternating direction method of multipliers proposed in Boyd et al 2011. We show that the algorithm converges globally to the set of KKT solutions whenever certain penalty parameter ρ satisfies ρ > 1. We further extend the algorithm and its analysis to the problem where the observation matrix contains missing values. Numerical experiments on real and synthetic data sets demonstrate the effectiveness of the algorithms under investigation.

AB - The nonnegative matrix factorization (NMF) has been a popular model for a wide range of signal processing and machine learning problems. It is usually formulated as a nonconvex cost minimization problem. This work settles the convergence issue of a popular algorithm based on the alternating direction method of multipliers proposed in Boyd et al 2011. We show that the algorithm converges globally to the set of KKT solutions whenever certain penalty parameter ρ satisfies ρ > 1. We further extend the algorithm and its analysis to the problem where the observation matrix contains missing values. Numerical experiments on real and synthetic data sets demonstrate the effectiveness of the algorithms under investigation.

KW - ADMM

KW - Convergence Analysis

KW - Nonconvex Optimization

KW - Nonnegative Matrix Factorization

UR - http://www.scopus.com/inward/record.url?scp=84973322922&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84973322922&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2016.7472577

DO - 10.1109/ICASSP.2016.7472577

M3 - Conference contribution

AN - SCOPUS:84973322922

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

SP - 4742

EP - 4746

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

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 20 March 2016 through 25 March 2016

ER -