A low-rank spectral method for learning Markov models

作者：Bi, Shujun^*; Yin, Zhen; Weng, Yihong

来源：Optimization Letters, 2023, 17(1): 143-162.

DOI：10.1007/s11590-022-01882-w

• Low-rank Markov chain
• Low-rank spectral estimator
• Lipschitzian error bound
• Statistical upper bound

This paper concerns with the problem of estimating the transition matrix of a low-rank discrete-state Markov model from its state-transition trajectories. We propose a low-rank spectral method via the best rank-r approximation of the spectral estimator based on the matrix elementwise l(q) (q >= 1) norm distance. Specifically, we establishing the Lipschitzian type error bound for the rank-constrained transition matrix set. Then, we prove a statistical upper bound for the estimation error of the proposed estimator. Numerical comparisons with the rank-constrained maximum likelihood estimator which computed by DC (difference of convex function) programming algorithm (Zhu et al. in Oper Res, 2021. https://doi.org/10.1287/opre.2021.2115) illustrate the merits of the proposed estimator in terms of the recoverability and the required computing time.