A Low-rank Spectral Estimation of Markov Process

BI Shujun; WENG Yihong

doi:10.6054/j.jscnun.2022063

Journal of South China Normal University (Natural Science Edition) > 2022 > 54(4): 101-108. > DOI: 10.6054/j.jscnun.2022063

BI Shujun, WENG Yihong. A Low-rank Spectral Estimation of Markov Process[J]. Journal of South China Normal University (Natural Science Edition), 2022, 54(4): 101-108. DOI: 10.6054/j.jscnun.2022063

Citation:

BI Shujun, WENG Yihong. A Low-rank Spectral Estimation of Markov Process[J]. Journal of South China Normal University (Natural Science Edition), 2022, 54(4): 101-108. DOI: 10.6054/j.jscnun.2022063

Citation:

BI Shujun, WENG Yihong. A Low-rank Spectral Estimation of Markov Process[J]. Journal of South China Normal University (Natural Science Edition), 2022, 54(4): 101-108. DOI: 10.6054/j.jscnun.2022063

PDF (1863 KB)

A Low-rank Spectral Estimation of Markov Process

BI Shujun^,,
WENG Yihong

School of Mathematics, South China University of Technology, Guangzhou 510641, China

More Information

Received Date: June 04, 2021
Available Online: September 21, 2022

Graphical Abstract

Abstract

Abstract

As the method for spectral estimation of Markov process makes use of nonnegativity-preserving step, the spectral estimator does not necessarily satisfy low-rank condition. Motivated by this, a low-rank spectral estimation algorithm (LRSEA) is proposed. First of all, the local Lipschitzian type error bound of the rank-constrained state transition matrix set is established, and an approximate projection matrix that satisfies the error bound inequality is given. Then, using the approximate projection matrix to modify the spectral estimation method, the LRSEA is proposed, and the statistical error bound for the proposed estimation method is provided. Numerical comparisons on the synthetic data with empirical estimator and spectral estimator show that the LRSEA has the lowest estimation error. Finally, the LRSEA together with k-means algorithm is used to analyze the dataset of Manhattan taxi trips.
- Markov process,
- low-rank,
- spectral estimation,
- error bound

FullText(HTML)

References (17)

References

[1]	ZHANG A, WANG M D. Spectral state compression of Markov processes[J]. IEEE Transactions on Information Theory, 2020, 66(5): 3202-3231. doi: 10.1109/TIT.2019.2956737
[2]	BENCZÚR A A, CSALOGÁNY K, SARLS T. On the feasibility of low-rank approximation for personalized Page-Rank[C]//Proceedings of Special Interest Tracks and Posters of the 14th International Conference on World Wide Web. New York: Association for Computing Machi-nery, 2005: 972-973.
[3]	NEGAHBAN S, OH S, SHAH D. Rank centrality: ranking from pairwise comparisons[J]. Operations Research, 2017, 65(1): 266-287. doi: 10.1287/opre.2016.1534
[4]	LIU Y, KANG C, GAO S, et al. Understanding intra-urban trip patterns from taxi trajectory data[J]. Journal of Geographical Systems, 2012, 14(4): 463-483. doi: 10.1007/s10109-012-0166-z
[5]	李耀华, 任田园, 邵攀登, 等. 基于马尔可夫链的西安市城市公交工况构建[J]. 中国科技论文, 2019, 14(2): 121-128. https://www.cnki.com.cn/Article/CJFDTOTAL-ZKZX201902001.htm LI Y H, REN T Y, SHAO P D, et al. Development of dri-ving cycle of bus in Xi'an city based on Markov chain[J]. China Sciencepaper, 2019, 14(2): 121-128. https://www.cnki.com.cn/Article/CJFDTOTAL-ZKZX201902001.htm
[6]	BENSON A R, GLEICH D F, LIM L H. The spacey random walk: a stochastic process for higher-order data[J]. SIAM Review, 2017, 59(2): 321-345. doi: 10.1137/16M1074023
[7]	SANDERS J, PROUTIERE A, YUN S Y. Clustering in block Markov chains[J]. Annals of Statistics, 2020, 48(10): 3488-3512.
[8]	ZHU Z W, LI X D, WANG M D, et al. Learning Markov models via low-rank optimization[J]. arXiv, (2020-11-26)[2021-05-15]. https://arxiv.org/abs/1907.00113v2.
[9]	徐翔斌, 李志鹏. 强化学习在运筹学的应用: 研究进展与展望[J]. 运筹与管理, 2020, 29(5): 227-239. https://www.cnki.com.cn/Article/CJFDTOTAL-YCGL202005027.htm XU X B, LI Z P. Research progress and prospects for application of reinforcement learning in operations research[J]. Operations Research and Management Science, 2020, 29(5): 227-239. https://www.cnki.com.cn/Article/CJFDTOTAL-YCGL202005027.htm
[10]	翟永, 刘津, 陈杰, 等. 基于马尔可夫链的无桩共享单车车辆投放规模分析[J]. 北京交通大学学报, 2019(5): 27-36. https://www.cnki.com.cn/Article/CJFDTOTAL-BFJT201905004.htm ZHAI Y, LIU J, CHEN J, et al. Analysis of dockless bike-sharing fleet size based on Markov chain[J]. Journal of Beijing Jiaotong University, 2019(5): 27-36. https://www.cnki.com.cn/Article/CJFDTOTAL-BFJT201905004.htm
[11]	PANG J S. Error bounds in mathematical programming[J]. Mathematical Programming, 1997, 79: 299-332.
[12]	TSENG P. Approximation accuracy, gradient methods, and error bound for structured convex optimization[J]. Mathematical Programming, 2010, 125(2): 263-295. doi: 10.1007/s10107-010-0394-2
[13]	ZHOU Z R, SO A M. A unified approach to error bounds for structured convex optimization problems[J]. Mathematical Programming, 2017, 165(2): 689-728. doi: 10.1007/s10107-016-1100-9
[14]	LI G, MORDUKHOVICH B S, NGHIA T T A, et al. Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates[J]. Mathematical Programming, 2018, 168: 313-346. doi: 10.1007/s10107-016-1014-6
[15]	BI S J, PAN S H. Error bounds for rank constrained optimization problems and applications[J]. Operations Research Letters, 2016, 44(3): 336-341.
[16]	LEVIN D A, PERES Y, WILMER E L. Markov chains and mixing times[M]. Rhode Island: American Mathematical Society, 2009.
[17]	ANDERSON T W, GOODMAN L A. Statistical inference about Markov chains[J]. The Annals of Mathematical Statistics, 1957, 28(1): 89-110.

Cited By

Get Citation

PDF

XML

Article views (283) PDF downloads (55)

Turn off MathJax

Article Contents

Abstract

References

A Low-rank Spectral Estimation of Markov Process

Abstract

References

Catalog

Export File

Citation

Format

Content