(01/19/21) Householder Dice: a new matrix-free algorithm for simulating dynamics on random matrices

January 19, 2021

In many problems in statistical learning, random matrix theory, and statistical physics, one needs to simulate dynamics on random matrix ensembles. A classical example is to use iterative methods to compute the extremal eigenvalues/eigenvectors of a (spiked) random matrix. Other examples include approximate message passing on dense random graphs, and gradient descent algorithms for solving learning and estimation problems with random design. In our recent paper, we show that all of these algorithms can be simulated by an efficient matrix-free scheme, if the random matrix is drawn from an ensemble with translation-invariant properties. Examples of such ensembles include the i.i.d. Gaussian (i.e. the rectangular Ginibre) ensemble, the Haar-distributed random orthogonal ensemble, the Gaussian orthogonal ensemble, and their complex-valued counterparts.


In our recent paper, we propose a new alg