Paper Info
Title
Sublinear estimation of a single element in sparse linear systems.
Abstract
We present a fast bidirectional algorithm for estimating a single element of the product of a matrix power and vector. This is an important primitive in many applications; in particular, we describe how it can be used to estimate a single element in the solution of a linear system Ax = b, with sublinear average-case running time guarantees for sparse systems. Our work combines the von Neumann-Ulam MCMC scheme for matrix multiplication with recent developments in bidirectional algorithms for estimating random-walk metrics. In particular, given a target additive-error threshold, we show how to combine a reverse local-variational technique with forward MCMC sampling, such that the resulting algorithm is order-wise faster than each individual approach.
Year
Venue
Field
2016
2016 54TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON)
Sublinear function,Mathematical optimization,Markov chain Monte Carlo,Linear system,Computer science,Matrix (mathematics),Algorithm,Sampling (statistics),Matrix multiplication
DocType
ISSN
Citations 
Conference
2474-0195
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Nitin Shyamkumar100.34
Siddhartha Banerjee218522.85
Peter Lofgren32139.30