Adaptive low-nonnegative-rank approximation for state aggregation of markov chains

Yaqi Duan, Mengdi Wang, Zaiwen Wen, Yaxiang Yuan

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)244-278
Number of pages35
JournalSIAM Journal on Matrix Analysis and Applications
Volume41
Issue number1
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Analysis

Keywords

  • Atomic norm
  • Markov chain
  • Nonnegative matrix factorization
  • Proximal alternating linearized minimization
  • State aggregation

Fingerprint

Dive into the research topics of 'Adaptive low-nonnegative-rank approximation for state aggregation of markov chains'. Together they form a unique fingerprint.

Cite this