  This paper develops a low-nonnegative-rank approximation method to identify
the state aggregation structure of a finite-state Markov chain under an
assumption that the state space can be mapped into a handful of meta-states.
The number of meta-states is characterized by the nonnegative rank of the
Markov transition matrix. Motivated by the success of the nuclear norm
relaxation in low rank minimization problems, we propose an atomic regularizer
as a convex surrogate for the nonnegative rank and formulate a convex
optimization problem. Because the atomic regularizer itself is not
computationally tractable, we instead solve a sequence of problems involving a
nonnegative factorization of the Markov transition matrices by using the
proximal alternating linearized minimization method. Two methods for adjusting
the rank of factorization are developed so that local minima are escaped. One
is to append an additional column to the factorized matrices, which can be
interpreted as an approximation of a negative subgradient step. The other is to
reduce redundant dimensions by means of linear combinations. Overall, the
proposed algorithm very likely converges to the global solution. The efficiency
and statistical properties of our approach are illustrated on synthetic data.
We also apply our state aggregation algorithm on a Manhattan transportation
data set and make extensive comparisons with an existing method.
