Technical Program

Paper Detail

Paper Title Non-Negative Matrix Factorization via Low-Rank Stochastic Manifold Optimization
Paper IdentifierMO4.R1.1
Authors Ahmed Douik, Babak Hassibi, California Institute of Technology, United States
Session Information Theory and Learning I
Location Le Théatre (Parterre), Level -1
Session Time Monday, 08 July, 16:40 - 18:00
Presentation Time Monday, 08 July, 16:40 - 17:00
Manuscript  Click here to download the manuscript
Abstract Several real-world applications, notably in non-negative matrix factorization, graph-based clustering, and machine learning, require solving a convex optimization problem over the set of stochastic and doubly stochastic matrices. A common feature of these problems is that the optimal solution is generally a low-rank matrix. This paper suggests reformulating the problem by taking advantage of the low-rank factorization $\mathbf{X}=\mathbf{U}\mathbf{V}^T$ and develops a Riemannian optimization framework for solving optimization problems on the set of low-rank stochastic and doubly stochastic matrices. In particular, this paper introduces and studies the geometry of the low-rank stochastic multinomial and the doubly stochastic manifold in order to derive first-order optimization algorithms. Being carefully designed and of lower dimension than the original problem, the proposed Riemannian optimization framework presents a clear complexity advantage. The claim is attested through numerical experiments on real-world and synthetic data for Non-negative Matrix Factorization (NFM) applications. The proposed algorithm is shown to outperform, in terms of running time, state-of-the-art methods for NFM.