Allerton 2015 Paper Abstract


Paper ThD5.3

Pavez, Eduardo (University of Southern California), Michelusi, Nicolo (University of Southern California), Anis, Aamir (University of Southern California), Mitra, Urbashi (University of Southern California), Ortega, Antonio (University of Southern California)

Markov Chain Sparsification with Independent Sets for Approximate Value Iteration

Scheduled for presentation during the Invited Session "Graph Signal Processing" (ThD5), Thursday, October 1, 2015, 16:10−16:30, Lower Level

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Wireless Communication Systems, Sparse Data Analysis, Optimization


The ever-increasing size of wireless networks poses a significant computational challenge for policy optimization schemes. In this paper, we propose a technique to considerably reduce the dimensionality of the value iteration problem, and thereby reduce computational complexity, by exploiting certain structural properties of the logical state transition network. Specifically, our method involves approximating the original Markov chain, in terms of KL distance, by a simplified one whose state transition graph contains an independent set of a prespecified size. As a result, value iteration needs to be performed only on the vertex cover of the network, from which the value function on the independent set can be obtained in a one-step process. The Markov chain approximation process presented in this paper involves minimizing matrix distance in an iterative greedy algorithm to find an approximately optimal independent set. Our method provides a tradeoff between accuracy and complexity that one can decide by choosing the size of the independent set. We implement our greedy algorithm using a KL divergence based distance and the Frobenius norm between stochastic matrices. Numerical results show that for a class of random networks the Markov chain approximation is accurate, even with large independent sets.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  09:04:48 PST  Terms of use