Linear algebra at exponential scale via tensor network dimension reduction

Abstract: 

Randomization has become a standard tool for accelerating large-scale numerical linear algebra. A common theme among many of the randomized algorithms developed over the last decade is dimension reduction, where a large problem is compressed to a much smaller subspace using a random matrix. 

This talk introduces random tensor networks as a dimension reduction tool for exponentially large, tensor-structured data. Under suitable assumptions, tensor networks populated with independent Gaussian entries can emulate the behavior of exponentially large Gaussian random vectors, while using only a vanishing fraction of the storage. These results lead to tensor network analogs of core randomized linear algebra algorithms for low-rank approximation and trace estimation. Examples from quantum many-body physics illustrate how these algorithms scale well past the limits of conventional dimension reduction techniques.