# Multi-way Monte Carlo Method for Linear Systems

arXiv: https://arxiv.org/abs/1608.04361 · HTML: https://mlsanity.com/paper/1608.04361/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2016.

## Built on by (most cited first, 3 of 3)

- [Revealing the Distributional Vulnerability of Discriminators by Implicit Generators](https://mlsanity.com/paper/2108.09976/) (2021)
- [Dual Representation Learning for Out-of-Distribution Detection](https://mlsanity.com/paper/2206.09387/) (2022)
- [Out-of-distribution Detection by Cross-class Vicinity Distribution of In-distribution Data](https://mlsanity.com/paper/2206.09385/) (2022)

## Abstract (arXiv)

We study the Monte Carlo method for solving a linear system of the form x = H x + b. A sufficient condition for the method to work is | H | < 1, which greatly limits the usability of this method. We improve this condition by proposing a new multi-way Markov random walk, which is a generalization of the standard Markov random walk. Under our new framework we prove that the necessary and sufficient condition for our method to work is the spectral radius ρ(H+) < 1, which is a weaker requirement than | H | < 1. In addition to solving more problems, our new method can work faster than the standard algorithm. In numerical experiments on both synthetic and real world matrices, we demonstrate the effectiveness of our new method.