ADAPTIVE LOW-NONNEGATIVE-RANK APPROXIMATION FOR STATE AGGREGATION OF MARKOV CHAINS
文献类型：期刊论文
| 作者 | Duan, Yaqi1; Wang, Mengdi1; Wen, Zaiwen2; Yuan, Yaxiang3 |
| 刊名 | SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
 |
| 出版日期 | 2020 |
| 卷号 | 41期号:1页码:244-278 |
| 关键词 | Markov chain state aggregation nonnegative matrix factorization atomic norm proximal alternating linearized minimization |
| ISSN号 | 0895-4798 |
| DOI | 10.1137/18M1220790 |
| 英文摘要 | This paper develops a low-nonnegative-rank approximation method to identify the state aggregation structure of a finite-state Markov chain under an assumption that the state space can be mapped into a handful of metastates. The number of metastates is characterized by the nonnegative rank of the Markov transition matrix. Motivated by the success of the nuclear norm relaxation in low-rank minimization problems, we propose an atomic regularizer as a convex surrogate for the nonnegative rank and formulate a convex optimization problem. Because the atomic regularizer itself is not computationally tractable, we instead solve a sequence of problems involving a nonnegative factorization of the Markov transition matrices by using the proximal alternating linearized minimization method. Two methods for adjusting the rank of factorization are developed so that local minima are escaped. One is to append an additional column to the factorized matrices, which can be interpreted as an approximation of a negative subgradient step. The other is to reduce redundant dimensions by means of linear combinations. Overall, the proposed algorithm very likely converges to the global solution. The efficiency and statistical properties of our approach are illustrated on synthetic data. We also apply our state aggregation algorithm on a Manhattan transportation data set and make extensive comparisons with an existing method. |
| 资助项目 | National Natural Science Foundation of China[11831002] ; National Natural Science Foundation of China[11421101] ; Beijing Academy of Artificial Intelligence (BAAI) |
| WOS研究方向 | Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000546980200011 |
| 出版者 | SIAM PUBLICATIONS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/51723]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Duan, Yaqi |
| 作者单位 | 1.Princeton Univ, Dept Elect Engn, Princeton, NJ 08544 USA 2.Peking Univ, Natl Engn Lab Big Data Anal & Applicat, Beijing Int Ctr Math Res, Ctr Data Sci, Beijing, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, State Key Lab Sci & Engn Comp, Beijing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Duan, Yaqi,Wang, Mengdi,Wen, Zaiwen,et al. ADAPTIVE LOW-NONNEGATIVE-RANK APPROXIMATION FOR STATE AGGREGATION OF MARKOV CHAINS[J]. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS,2020,41(1):244-278. |
| APA | Duan, Yaqi,Wang, Mengdi,Wen, Zaiwen,&Yuan, Yaxiang.(2020).ADAPTIVE LOW-NONNEGATIVE-RANK APPROXIMATION FOR STATE AGGREGATION OF MARKOV CHAINS.SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS,41(1),244-278. |
| MLA | Duan, Yaqi,et al."ADAPTIVE LOW-NONNEGATIVE-RANK APPROXIMATION FOR STATE AGGREGATION OF MARKOV CHAINS".SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 41.1(2020):244-278. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。