Approximating a Single Component of the Solution to a Linear System
Wednesday, May 20, 2015 - 9:00am - 9:50am
Keller 3-180
Christina Lee (Massachusetts Institute of Technology)
We consider solving for a single component of the solution to a system of linear equations, Ax = b, where A is an n-by-n real-valued matrix, and b is a real-valued n dimensional vector. This equation can equivalently be written as x = Gx + z for an appropriate choice of G and z. We are interested in utilizing the sparsity of G (equivalently of A) to solve for a single component of the solution efficiently. In this talk, we focus on two scenarios. Scenario (a) considers when G is an n-by-n stochastic matrix and z is the zero vector, which is equivalent to estimating the stationary probability of a state in a Markov chain. Scenario (b) considers when the spectral radius of G is strictly less than 1 and b is not the zero vector, which is equivalent to solving Ax = b when A is positive definite.
For each of these scenarios, we will discuss known probabilistic approaches and iterative algebraic approaches. We will present a new variant of the Monte Carlo method for scenario (a), which uses the classical characterization of stationary probability as the reciprocal of the average return time of a random walk. We provide theoretical analysis of the performance guarantees of this algorithm, given as a function of the mixing time of the Markov chain. We follow by presenting a randomized asynchronous algorithm for scenario (b), which builds upon the Neumann series characterization for the solution. The computation cost is bounded as a function of the approximation error, the sparsity of G, and the spectral radius of G, which can be independent from the dimension n. Through these methods, we provide a discussion of the conditions in which local approximations can be efficient.
This is joint work with Asuman Ozdaglar and Devavrat Shah.
For each of these scenarios, we will discuss known probabilistic approaches and iterative algebraic approaches. We will present a new variant of the Monte Carlo method for scenario (a), which uses the classical characterization of stationary probability as the reciprocal of the average return time of a random walk. We provide theoretical analysis of the performance guarantees of this algorithm, given as a function of the mixing time of the Markov chain. We follow by presenting a randomized asynchronous algorithm for scenario (b), which builds upon the Neumann series characterization for the solution. The computation cost is bounded as a function of the approximation error, the sparsity of G, and the spectral radius of G, which can be independent from the dimension n. Through these methods, we provide a discussion of the conditions in which local approximations can be efficient.
This is joint work with Asuman Ozdaglar and Devavrat Shah.
MSC Code:
34A30
Keywords: