Stability analysis of multiplicative update algorithms for non-negative matrix factorization

Roland Badeau; Nancy Bertin; Emmanuel Vincent

doi:10.1109/ICASSP.2011.5946752

Stability analysis of multiplicative update algorithms for non-negative matrix factorization

Roland Badeau, Nancy Bertin, Emmanuel Vincent

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

Abstract

Multiplicative update algorithms have encountered a great success to solve optimization problems with non-negativity constraints, such as the famous non-negative matrix factorization (NMF) and its many variants. However, despite several years of research on the topic, the understanding of their convergence properties is still to be improved. In this paper, we show that Lyapunov's stability theory provides a very enlightening viewpoint on the problem. We prove the stability of supervised NMF and study the more difficult case of unsupervised NMF. Numerical simulations illustrate those theoretical results, and the convergence speed of NMF multiplicative updates is analyzed.

Original language	English
Title of host publication	2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings
Pages	2148-2151
Number of pages	4
DOIs	https://doi.org/10.1109/ICASSP.2011.5946752
Publication status	Published - 18 Aug 2011
Externally published	Yes
Event	36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Prague, Czech Republic Duration: 22 May 2011 → 27 May 2011

Publication series

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

Conference

Conference	36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011
Country/Territory	Czech Republic
City	Prague
Period	22/05/11 → 27/05/11

Keywords

Lyapunov methods
Optimization methods
multiplicative update algorithms
non-negative matrix factorization
stability

Access to Document

10.1109/ICASSP.2011.5946752

Cite this

Badeau, R., Bertin, N., & Vincent, E. (2011). Stability analysis of multiplicative update algorithms for non-negative matrix factorization. In 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings (pp. 2148-2151). Article 5946752 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2011.5946752

Badeau, Roland ; Bertin, Nancy ; Vincent, Emmanuel. / Stability analysis of multiplicative update algorithms for non-negative matrix factorization. 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings. 2011. pp. 2148-2151 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{f899124791064467ad4f0c781e1b10f0,

title = "Stability analysis of multiplicative update algorithms for non-negative matrix factorization",

abstract = "Multiplicative update algorithms have encountered a great success to solve optimization problems with non-negativity constraints, such as the famous non-negative matrix factorization (NMF) and its many variants. However, despite several years of research on the topic, the understanding of their convergence properties is still to be improved. In this paper, we show that Lyapunov's stability theory provides a very enlightening viewpoint on the problem. We prove the stability of supervised NMF and study the more difficult case of unsupervised NMF. Numerical simulations illustrate those theoretical results, and the convergence speed of NMF multiplicative updates is analyzed.",

keywords = "Lyapunov methods, Optimization methods, multiplicative update algorithms, non-negative matrix factorization, stability",

author = "Roland Badeau and Nancy Bertin and Emmanuel Vincent",

year = "2011",

month = aug,

day = "18",

doi = "10.1109/ICASSP.2011.5946752",

language = "English",

isbn = "9781457705397",

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

pages = "2148--2151",

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

note = "36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 ; Conference date: 22-05-2011 Through 27-05-2011",

}

Badeau, R, Bertin, N & Vincent, E 2011, Stability analysis of multiplicative update algorithms for non-negative matrix factorization. in 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings., 5946752, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, pp. 2148-2151, 36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011, Prague, Czech Republic, 22/05/11. https://doi.org/10.1109/ICASSP.2011.5946752

Stability analysis of multiplicative update algorithms for non-negative matrix factorization. / Badeau, Roland; Bertin, Nancy; Vincent, Emmanuel.
2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings. 2011. p. 2148-2151 5946752 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

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

TY - GEN

T1 - Stability analysis of multiplicative update algorithms for non-negative matrix factorization

AU - Badeau, Roland

AU - Bertin, Nancy

AU - Vincent, Emmanuel

PY - 2011/8/18

Y1 - 2011/8/18

N2 - Multiplicative update algorithms have encountered a great success to solve optimization problems with non-negativity constraints, such as the famous non-negative matrix factorization (NMF) and its many variants. However, despite several years of research on the topic, the understanding of their convergence properties is still to be improved. In this paper, we show that Lyapunov's stability theory provides a very enlightening viewpoint on the problem. We prove the stability of supervised NMF and study the more difficult case of unsupervised NMF. Numerical simulations illustrate those theoretical results, and the convergence speed of NMF multiplicative updates is analyzed.

AB - Multiplicative update algorithms have encountered a great success to solve optimization problems with non-negativity constraints, such as the famous non-negative matrix factorization (NMF) and its many variants. However, despite several years of research on the topic, the understanding of their convergence properties is still to be improved. In this paper, we show that Lyapunov's stability theory provides a very enlightening viewpoint on the problem. We prove the stability of supervised NMF and study the more difficult case of unsupervised NMF. Numerical simulations illustrate those theoretical results, and the convergence speed of NMF multiplicative updates is analyzed.

KW - Lyapunov methods

KW - Optimization methods

KW - multiplicative update algorithms

KW - non-negative matrix factorization

KW - stability

U2 - 10.1109/ICASSP.2011.5946752

DO - 10.1109/ICASSP.2011.5946752

M3 - Conference contribution

AN - SCOPUS:80051655034

SN - 9781457705397

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

SP - 2148

EP - 2151

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

T2 - 36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011

Y2 - 22 May 2011 through 27 May 2011

ER -

Badeau R, Bertin N, Vincent E. Stability analysis of multiplicative update algorithms for non-negative matrix factorization. In 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings. 2011. p. 2148-2151. 5946752. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2011.5946752

Stability analysis of multiplicative update algorithms for non-negative matrix factorization

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this