Identifying Sparse Low-Dimensional Structures in Markov Chains: A
  Nonnegative Matrix Factorization Approach
  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.
