Primal-dual algorithms for non-negative matrix factorization with the Kullback-Leibler divergence
By Felipe Yanez, Francis R. Bach. 2014
22 citations recorded by the source corpus.
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.
Subfields: Computational Mechanics, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
- Federico Monti
- Michael M. Bronstein
- Xavier Bresson
- Thomas Pock
- Vassilis Kalofolias
- Antonin Chambolle
- Pierre Vandergheynst
- Kirell Benzi
In Signal Processing
- Vassilis Kalofolias
- Federico Monti
- Xavier Bresson
- Michael M. Bronstein
- Antonin Chambolle
- Pierre Vandergheynst
- Thomas Pock
- Kirell Benzi
Citations in the corpus
- Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks (2017, methodology): “…problem thus boils down to minimizing A solution is to use a factorized representation (Srebro et al., 2004; Koren et al., 2009; Ma et al., 2011; Yanez & Bach, 2012; Rao et al., 2015; Benzi et al., 2016) X = WH (cid:62) , where W , H are m × r and n × r matrices, respectively, with r min( m, n…”
- An introduction to continuous optimization for imaging (2016, methodology): “For the form (5.6), it can be found in Hohage and Homann (2014) and is also implemented in Yanez and Bach (2014) to solve a matrix factorization problem.”
- Song recommendation with non-negative matrix factorization and graph total variation (2016, methodology): “Index Terms— Recommender system, graphs, NMF, total variation, audio features 1.”