Linear algebra at exponential scale via tensor network dimension reduction
It provides a general framework for solving high-dimensional linear algebra problems that are otherwise intractable due to the curse of dimensionality, with provable guarantees.
The paper develops randomized dimension reduction techniques for tensor networks, enabling provably efficient algorithms for exponential-scale linear algebra problems like trace estimation and eigenvalue approximation, demonstrated on quantum many-body systems with dimension up to 2^200.
Many problems in modern scientific computing are challenging because of a \emph{curse of dimension}, where their mathematical formulation involves objects whose dimension is \emph{exponential} in the nominal "size" of the problem. Tensor networks can provide a compact representation for exponentially large vectors and matrices that arise in applications, but these representations do not always lead to reliable algorithms. This paper develops and analyzes techniques for randomized dimension reduction of tensor network data. These techniques support a suite of efficient algorithms for provably solving exponential-scale linear algebra problems, including trace estimation and eigenvalue approximation. The paper includes several stylized illustrations from quantum many-body physics with ambient dimension up to $2^{200}$.