Many important problems are characterized by the eigenvalues of a large
matrix. For example, the difficulty of many optimization problems, such as
those arising from the fitting of large models in statistics and machine
learning, can be investigated via the spectrum of the Hessian of the empirical
loss function. Network data can be understood via the eigenstructure of a graph
Laplacian matrix using spectral graph theory. Quantum simulations and other
many-body problems are often characterized via the eigenvalues of the solution
space, as are various dynamic systems. However, naive eigenvalue estimation is
computationally expensive even when the matrix can be represented; in many of
these situations the matrix is so large as to only be available implicitly via
products with vectors. Even worse, one may only have noisy estimates of such
matrix vector products. In this work, we combine several different techniques
for randomized estimation and show that it is possible to construct unbiased
estimators to answer a broad class of questions about the spectra of such
implicit matrices, even in the presence of noise. We validate these methods on
large-scale problems in which graph theory and random matrix theory provide
ground truth.

本研究结合多种不同的随机估计技术，展示了在存在噪声的情况下，构建偏差估计器以回答有关隐式矩阵光谱的广泛问题是可能的。