Stochastic reformulations of linear systems and efficient randomized algorithms

We propose a new paradigm for solving linear systems with a very large number of equations. In our paradigm, the system is first reformulated into a stochastic problem, and then solved with a suitable (typically randomized) algorithm. Our stochastic reformulation is flexible as it depends on a userdefined parameter in the form of a distribution defining an ensemble of random matrices. The choice of the distribution directly influences the “condition number” of the reformulation, which leads to the novel concept of “randomized preconditioning”. We give necessary and sufficient conditions for the reformulation to be exact, i.e., for the solution set of the stochastic problem to be identical to the solution set of the linear system. We also show that the reformulation can be equivalently seen as a stochastic optimization problem, stochastically preconditioned linear system, stochastic fixed-point problem and as a probabilistic intersection problem. For instance, the condition number of the reformulation is equal to the condition number of the stochastically preconditioned linear system, and to the condition number of associated with the Hessian of the objective function appearing the stochastic optimization reformulation.