Low-rank spectral estimation algorithm of learning Markov model

Abstract

This paper proposes a low-rank spectral estimation algorithm of learning Markov model. First, an approximate projection algorithm for the rank-constrained frequency matrix set is proposed, and thereafter its local Lipschitzian error bound established. Then, we propose a low-rank spectral estimation algorithm for estimating the state transition frequency matrix and the probability matrix of Markov model by applying the approximate projection algorithm to correct the maximum likelihood estimation of the frequency matrix, and prove that there is only a multiplying constant difference in estimation errors between the low-rank spectral estimation and the maximum likelihood estimation under appropriate conditions. Finally, numerical comparisons with the prevailing maximum likelihood estimation, spectral estimation, and rank-constrained maximum likelihood estimation show that the low-rank spectral estimation algorithm is effective.

Key words： Markov model; low-rank spectral estimation; error bound; approximate projection

References

1 Anderson T W, Goodman L A. Statistical inference about Markov chains. Ann Math Statist 1957; 28(1): 89–110

2 BenczúrA ACsalogányKSarlósT. On the feasibility of low-rank approximation for personalized PageRank. In: Special Interest Tracks and Posters of the 14th International Conference on World Wide Web. New York: ACM, 2005, 972–973

3 Benson A R, Gleich D F, Lim L-H. The spacey random walk: a stochastic process for higher-order data. SIAM Rev 2017; 59(2): 321–345

4 Bi S J, Pan S H. Error bounds for rank constrained optimization problems and applications. Oper Res Lett 2016; 44(3): 336–341

5 HuangQ QKakadeS MKongW HValiantG. Recovering structured probability matrices. In: 9th Innovations in Theoretical Computer Science, LIPIcs Leibniz Int Proc Inform, Vol 94. Wadern: Schloss Dagstuhl Leibniz-Zent Inform, 2018, 46

6 JainPMekaRDhillonI. Guaranteed rank minimization via singular value projection. In: Advances in Neural Information Processing Systems 23 (24th Annual Conference on Neural Information Processing Systems 2010), Vol 1. La Jolla, CA: NIPS, 2010, 937–945

7 Li G Y, Mordukhovich B S, Nghia T T A, Pham T S. Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates. Math Program 2018; 168(1/2): Ser B, 313–346

8 Li Y H, Ren T Y, Shao P D, Song W P, Li Z Y, Gou Q Z. Development of driving cycle of bus in Xi’an City based on Markov chain. China Sciencepaper 2019; 14(2): 121–128

9 Liu Y, Kang C G, Gao S, Xiao Y, Tian Y. Understanding intra-urban trip patterns from taxi trajectory data. J Geographical Systems 2012; 14(4): 463–483

10 Negahban S, Oh S, Shah D. Rank centrality: ranking from pairwise comparisons. Oper Res 2017; 65(1): 266–287

11 Pang J-S. Error bounds in mathematical programming. Mathematical Programming 1997; 79(1/2/3): Ser B, 299–332

12 Sanders J, Proutière A, Yun S-Y. Clustering in block Markov chains. Ann Statist 2020; 48(6): 3488–3512

13 Tseng P. Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math Program 2010; 125(2): Ser. B, 263–295

14 Xu X B, Li Z P. Research progress and prospects for application of reinforcement learning in operations research. Operations Research and Management Science 2020; 29(5): 227–239

15 Zhai Y, Liu J, Chen J, Xing X C, Du J, Li H, Zhu J. Analysis of dockless bike-sharing fleet size based on Markov chain. J Beijing Jiaotong Univ 2019; 43(5): 27–36

16 Zhang A R, Wang M D. Spectral state compression of Markov processes. IEEE Trans Inform Theory 2020; 66(5): 3202–3231

17 Zhou Z R, So A M-C. A unified approach to error bounds for structured convex optimization problems. Math Program 2017; 165(2): Ser A, 689–728

18 Zhu Z W, Li X D, Wang M D, Zhang A R. Learning Markov models via low-rank optimization. Oper Res 2022; 70(4): 2384–2398