Estimation of Markov Chain via Rank-constrained Likelihood

04/03/2018
by   Xudong Li, et al.
0

This paper studies the recovery and state compression of low-rank Markov chains from empirical trajectories. We propose a non-convex estimator based on rank-constrained likelihood maximization. Statistical upper bounds are provided for the Kullback-Leiber divergence and the ℓ_2 risk between the estimator and the true transition matrix. The estimator reveals a compressed state space of the Markov chain. We also develop a novel DC (difference of convex function) programming algorithm to tackle the rank-constrained non-smooth optimization problem. Convergence results are established. Experiments with taxi trip data show that the estimator is able to identify the zoning of Manhattan city.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset