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

DOI10.1137/18M1220790zbMATH Open1461.65145arXiv1810.06032OpenAlexW3007318355MaRDI QIDQ5222093FDOQ5222093

Authors: Yaqi Duan, Mengdi Wang, Zaiwen Wen, Yaxiang Yuan 

Publication date: 30 March 2020

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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 meta-states. The number of meta-states 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.

Full work available at URL: https://arxiv.org/abs/1810.06032

Recommendations

• Learning Markov models via low-rank optimization
• A low-rank spectral method for learning Markov models
• Optimal Kullback-Leibler approximation of Markov chains via nuclear norm regularisation
• A probabilistic algorithm for aggregating vastly undersampled large Markov chains
• Structured nonnegative matrix factorization with applications to hidden Markov realization and clustering

zbMATH Keywords

Markov chainnonnegative matrix factorizationstate aggregationproximal alternating linearized minimizationatomic norm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Markov and semi-Markov decision processes (90C40)

Cites Work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Title not available (Why is that?)
• Exact matrix completion via convex optimization
• Statistical Inference about Markov Chains
• On the complexity of nonnegative matrix factorization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Projected Gradient Methods for Nonnegative Matrix Factorization
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• The convex geometry of linear inverse problems
• Fast nonnegative matrix factorization: an active-set-like method and comparisons
• Reinforcement learning. An introduction
• Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
• Low-rank optimization on the cone of positive semidefinite matrices
• Optimal partition and effective dynamics of complex networks
• Low-rank optimization with trace norm penalty
• Title not available (Why is that?)

Cited In (6)

• Optimal Kullback-Leibler approximation of Markov chains via nuclear norm regularisation
• A probabilistic algorithm for aggregating vastly undersampled large Markov chains
• A low-rank approximation for MDPs via moment coupling
• A low-rank spectral method for learning Markov models
• Learning Markov models via low-rank optimization
• Spectral thresholding for the estimation of Markov chain transition operators

Uses Software

• SDPLR

This page was built for publication: Adaptive low-nonnegative-rank approximation for state aggregation of Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222093)