Joint Dept. of Mathematics and CMSA Random Matrix & Probability Theory Seminar: Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Random Matrices

RANDOM MATRIX

Speaker:

Yue M. Lu - Harvard University

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 initialization. We will show that all such dynamics 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.

A “direct” approach to the simulation, where one first generates a dense n × n matrix from the ensemble, requires at least O(n^2) resource in space and time. The new algorithm, named Householder Dice (HD), overcomes this O(n^2) bottleneck by using the principle of deferred decisions: rather than fixing the entire random matrix in advance, it lets the randomness unfold with the dynamics. At the heart of this matrix-free algorithm is an adaptive and recursive construction of (random) Householder reflectors. These orthogonal transformations exploit the group symmetry of the matrix ensembles, while simultaneously maintaining the statistical correlations induced by the dynamics. The memory and computation costs of the HD algorithm are O(nT) and O(n T^2), respectively, with T being the number of iterations. When T ≪ n, which is nearly always the case in practice, the new algorithm leads to significant reductions in runtime and memory footprint.

Finally, the HD algorithm is not just a computational trick. I will show how its construction can serve as a simple proof technique for several problems in high-dimensional estimation.

Zoom: https://harvard.zoom.us/j/99333938108