Approximating a Single Component of the Solution to a Linear System

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.