Identifying Sparse Low-Dimensional Structures in Markov Chains: A Nonnegative Matrix Factorization Approach
This work addresses representation learning for Markov chains, which is incremental as it builds on existing nonnegative matrix factorization techniques with sparsity constraints.
The paper tackles the problem of learning low-dimensional representations for large-scale Markov chains by mapping the state space to a kernel space with sparse meta states, using a constrained nonnegative matrix factorization approach. They propose an efficient block coordinate gradient descent method and analyze its convergence properties.
We consider the problem of learning low-dimensional representations for large-scale Markov chains. We formulate the task of representation learning as that of mapping the state space of the model to a low-dimensional state space, called the kernel space. The kernel space contains a set of meta states which are desired to be representative of only a small subset of original states. To promote this structural property, we constrain the number of nonzero entries of the mappings between the state space and the kernel space. By imposing the desired characteristics of the representation, we cast the problem as a constrained nonnegative matrix factorization. To compute the solution, we propose an efficient block coordinate gradient descent and theoretically analyze its convergence properties.