Speaker
Description
Computing the diagonal entries of a large linear operator is a common computational primitive in numerical linear algebra, with applications in uncertainty quantification, cross-validation, perturbation analysis, electronic structure calculation and more. However, estimating the diagonals of a matrix given only implicit matrix-vector access is challenging, as randomized algorithms suffer from high variance. In many cases, these problems can be efficiently reduced to estimating the squared row norms of a suitable square root of the matrix, where randomized algorithms specialized to row norm estimation with considerably lower variance may be applied. In particular, when the matrix in question is a function of another matrix, that is, $A = f(B)$, and matrix vector products with $A$ are computed using a Krylov method, it is often the case that matrix vector products with $f^{1/2}(B)$ can be computed just as efficiently those with $f(B)$. We present algorithms for estimating squared row norms and approaches for incorporating them into other computational tasks.