Speaker: Alice Cortinovis Affiliation: EPFL Time: Friday, 19/03/2021, 16:00
Title: Randomized trace estimates for indefinite matrices with an application to determinants
Randomized trace estimation is a popular technique to approximate the trace of a large-scale matrix A by computing the average of quadratic forms x^T * A * x for many samples of a random vector X. We show new tail bounds for randomized trace estimates in the case of Rademacher and Gaussian random vectors, which significantly improve existing results for indefinite matrices. Then we focus on the approximation of the determinant of a symmetric positive definite matrix B, which can be done via the relation log(det(B)) = trace(log(B)), where the matrix log(B) is usually indefinite. We analyze the convergence of the Lanczos method to approximate quadratic forms x^T * log(B) * x by exploiting its connection to Gauss quadrature. Finally, we combine our tail bounds on randomized trace estimates with the analysis of the Lanczos method to improve and extend an existing result on log determinant approximation to not only cover Rademacher but also Gaussian random vectors.
https://www.dm.unipi.it/webnew/it/seminari/randomized-trace-estimates-indefi...
Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4