A Row-Wise Update Algorithm for Sparse Stochastic Matrix Factorization

Nonnegative matrix factorization arises widely in machine learning and data analysis. In this paper, for a given factorization of rank r, we consider the sparse stochastic matrix factorization (SSMF) of decomposing a prescribed m-by-n stochastic matrix V into a product of an m-by-r stochastic matrix W and a sparse r-by-n stochastic matrix H. With the prescribed sparsity level, we reformulate the SSMF as an unconstrained nonvonvex-nonsmooth minimization problem and introduce a row-wise update algorithm for solving the minimization problem. We show that the proposed algorithm converges globally and the generated sequence converges to a special critical point of the cost function, which is a global minimizer over the W-factor as a whole and is nearly a global minimizer over each row vector of the H-factor. Numerical experiments on both synthetic and real data sets are given to demonstrate the effectiveness of our proposed algorithm.