CMX Student/Postdoc Seminar

"Leave-one-out" is a powerful idea in statistics and machine learning in which one recomputes a quantity multiple times, each calculation omitting a different data point. This talk presents two algorithms which apply the leave-one-out idea to randomized matrix computations. The first algorithm, XTrace, uses the leave-one-out idea to compute highly accurate estimates of the trace of a matrix defined implicitly through matrix–vector products. The second algorithm, the matrix jackknife, uses a leave-one-out technique to assess the variability of the output of a randomized matrix computation from a single execution of the algorithm, providing a computationally cheap way to assess the reliability of the computed output. Both of these algorithms are made lightning-fast by efficient algorithms to perform the leave-one-out procedure on the randomized SVD, a core primitive in many randomized matrix algorithms.