A Columnwise 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 , we consider the sparse stochastic matrix factorization (SSMF) of decomposing a prescribed -by- stochastic matrix into a product of an -by- stochastic matrix and an -by- stochastic matrix , where both and are required to be sparse. With the prescribed sparsity level, we reformulate the SSMF as an unconstrained nonconvex-nonsmooth minimization problem and introduce a columnwise update algorithm for solving the minimization problem. We show that our algorithm converges globally. The main advantage of our algorithm is that the generated sequence converges to a special critical point of the cost function, which is nearly a global minimizer over each column vector of the -factor and is a global minimizer over the -factor as a whole if there is no sparsity requirement on . Numerical experiments on both synthetic and real data sets are given to demonstrate the effectiveness of our proposed algorithm.