Perturbing a deterministic n-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms. The idea of adding the noise to a given deterministic matrix was introduced by Spielman and Teng in 2004. This noise reduces the condition number of the input matrix to O(n), and with it the complexity of many matrix algorithms. Moreover, it is oblivious to the input as it does not require any prior knowledge of the matrix besides a crude bound on its norm.

However, when deployed algorithmically, this method is expensive due to the cost of generating and storing n^2 Gaussian random variables. We will describe a random matrix construction which requires generating O(n) independent random variables and reduces the condition number of any deterministic matrix to O(n), thus matching Gaussian perturbations. Using so few independent variables requires generating a random matrix with dependent entries thus making the condition number analysis more involved.

Among practical implications of this result is a better complexity bound for the perturbed conjugate gradient algorithm, showing that we can solve an n by n linear system within an arbitrarily small constant backward error using O(n) matrix-vector products.

Joint work with Shabarish Cenakkod, Michal Derezinski, and Xiaoyu Dong.

Meeting Id: 938 9436 7616 Password : 268545