Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE

Abstract: 

Non-negative matrix factorization (NMF) approximates a given matrix as a product of two non-negative matrix factors. Multiplicative algorithms deliver reliable results, but they show slow convergence for high-dimensional data and may be stuck away from local minima. Gradient descent methods have better behavior, but only apply to smooth losses. For non-smooth losses such as the Kullback-Leibler (KL) loss, surprisingly, these methods are lacking. In this paper, we propose a first-order primal-dual algorithm for non-negative decomposition problems (one of the two factors is fixed) with the KL distance. All required computations may be obtained in closed form and we provide an efficient heuristic way to select step-sizes. By using alternating optimization, our algorithm readily extends to NMF and, on synthetic or real world data, it is either faster than existing algorithms, or leads to improved local optima, or both.

up
0 users have voted:

Paper Details

Authors:
Felipe Yanez, Francis Bach
Submitted On:
8 March 2017 - 8:23pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Felipe Yanez
Paper Code:
MLSP-L2.5
Document Year:
2017
Cite

Document Files

First-order method for non-negative matrix factorization with the Kullback-Leibler loss.

(110 downloads)

Subscribe

[1] Felipe Yanez, Francis Bach, "PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE", IEEE SigPort, 2017. [Online]. Available: http://sigport.org/1714. Accessed: Aug. 24, 2017.
@article{1714-17,
url = {http://sigport.org/1714},
author = {Felipe Yanez; Francis Bach },
publisher = {IEEE SigPort},
title = {PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE},
year = {2017} }
TY - EJOUR
T1 - PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE
AU - Felipe Yanez; Francis Bach
PY - 2017
PB - IEEE SigPort
UR - http://sigport.org/1714
ER -
Felipe Yanez, Francis Bach. (2017). PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE. IEEE SigPort. http://sigport.org/1714
Felipe Yanez, Francis Bach, 2017. PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE. Available at: http://sigport.org/1714.
Felipe Yanez, Francis Bach. (2017). "PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE." Web.
1. Felipe Yanez, Francis Bach. PRIMAL-DUAL ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION WITH THE KULLBACK-LEIBLER DIVERGENCE [Internet]. IEEE SigPort; 2017. Available from : http://sigport.org/1714