Low-rank spectral estimation algorithm of learning Markov model

doi:10.3868/s140-DDD-024-0009-x

Front. Math. China

2024, Vol. 19

Issue (3) : 137-155 https://doi.org/10.3868/s140-DDD-024-0009-x

Low-rank spectral estimation algorithm of learning Markov model

Yongye ZHAO¹(

), Shujun BI²(

)

¹. Department of Basic Courses, Guangzhou Maritime University, Guangzhou 510725, China
². Department of Mathematics, South China University of Technology, Guangzhou 510640, China

Download: PDF(5820 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords Markov model low-rank spectral estimation error bound approximate projection

Corresponding Author(s): Yongye ZHAO,Shujun BI

Online First Date: 18 June 2024 Issue Date: 01 July 2024

Cite this article:

Yongye ZHAO,Shujun BI. Low-rank spectral estimation algorithm of learning Markov model[J]. Front. Math. China, 2024, 19(3): 137-155.

URL:

https://academic.hep.com.cn/fmc/EN/10.3868/s140-DDD-024-0009-x
https://academic.hep.com.cn/fmc/EN/Y2024/V19/I3/137

Fig.1 Numerical results comparison of Example 3.1 (Type I) (d = 1000, r = 10, n = round(krd log(d)))

Fig.2 Numerical results comparison of Example 3.1 (Type II) (d = 1000, r = 10, n = round(krd log(d)))

Fig.3 Numerical results comparison of Example 3.2 (Type I) (d = 1000, r = 10, n = round(krd log(d)))

Fig.4 Numerical results comparison of Example 3.2 (Type II) (d = 1000, r = 10, n = round(krd log(d)))

Fig.5 Different γ numerical results comparison of Example 3.2 (Type II) (d = 200, r = 5, n = round(3rd log(d)))

Fig.6 Partitioning result of Manhattan Island (k = r = 5)

Fig.7 Partitioning result of Manhattan Island (k = r = 6)

Fig.8 Partitioning result of Manhattan Island (k = r = 7)

Fig.9 Partitioning result of Manhattan Island in the morning (k = r = 5)

Fig.10 Partitioning result of Manhattan Island in the afternoon (k = r = 5)

Fig.11 Partitioning result of Manhattan Island in the evening (k = r = 5)

1	T W Anderson, L A Goodman. Statistical inference about Markov chains. Ann Math Statist 1957; 28(1): 89–110
2	A A BenczúrK CsalogányT Sarlós. 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	A R Benson, D F Gleich, L-H Lim. The spacey random walk: a stochastic process for higher-order data. SIAM Rev 2017; 59(2): 321–345
4	S J Bi, S H Pan. Error bounds for rank constrained optimization problems and applications. Oper Res Lett 2016; 44(3): 336–341
5	Q Q HuangS M KakadeW H KongG Valiant. 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	P JainR MekaI Dhillon. 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	G Y Li, B S Mordukhovich, T T A Nghia, T S Pham. 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	Y H Li, T Y Ren, P D Shao, W P Song, Z Y Li, Q Z Gou. Development of driving cycle of bus in Xi’an City based on Markov chain. China Sciencepaper 2019; 14(2): 121–128
9	Y Liu, C G Kang, S Gao, Y Xiao, Y Tian. Understanding intra-urban trip patterns from taxi trajectory data. J Geographical Systems 2012; 14(4): 463–483
10	S Negahban, S Oh, D Shah. Rank centrality: ranking from pairwise comparisons. Oper Res 2017; 65(1): 266–287
11	J-S Pang. Error bounds in mathematical programming. Mathematical Programming 1997; 79(1/2/3): Ser B, 299–332
12	J Sanders, A Proutière, S-Y Yun. Clustering in block Markov chains. Ann Statist 2020; 48(6): 3488–3512
13	P Tseng. Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math Program 2010; 125(2): Ser. B, 263–295
14	X B Xu, Z P Li. Research progress and prospects for application of reinforcement learning in operations research. Operations Research and Management Science 2020; 29(5): 227–239
15	Y Zhai, J Liu, J Chen, X C Xing, J Du, H Li, J Zhu. Analysis of dockless bike-sharing fleet size based on Markov chain. J Beijing Jiaotong Univ 2019; 43(5): 27–36
16	A R Zhang, M D Wang. Spectral state compression of Markov processes. IEEE Trans Inform Theory 2020; 66(5): 3202–3231
17	Z R Zhou, A M-C So. A unified approach to error bounds for structured convex optimization problems. Math Program 2017; 165(2): Ser A, 689–728
18	Z W Zhu, X D Li, M D Wang, A R Zhang. Learning Markov models via low-rank optimization. Oper Res 2022; 70(4): 2384–2398

[1]	Changli LIU, Ren-Cang LI. Structured backward error for palindromic polynomial eigenvalue problems, II: Approximate eigentriplets[J]. Front. Math. China, 2018, 13(6): 1397-1426.
[2]	Leihong ZHANG, Weihong YANG, Chungen SHEN, Jiang FENG. Error bounds of Lanczos approach for trust-region subproblem[J]. Front. Math. China, 2018, 13(2): 459-481.

Viewed

Full text

Abstract

Cited

Shared

Discussed