Hutch++: Optimal Stochastic Trace Estimation.

We study the problem of estimating the trace of a matrix that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a (1 ± ) approximation to tr( ) for any positive semidefinite (PSD) using just (1) matrix-vector products. This improves on the ubiquitous , which requires (1 ) matrix-vector products.

Near Optimal Linear Algebra in the Online and Sliding Window Models.

We initiate the study of numerical linear algebra in the sliding window model, where only the most recent updates in a stream form the underlying data set. Although many existing algorithms in the sliding window model use or borrow elements from the smooth histogram framework (Braverman and Ostrovsky, FOCS 2007), we show that many interesting linear-algebraic problems, including spectral and vector induced matrix norms, generalized regression, and lowrank approximation, are not amenable to this approach in the row-arrival model. To overcome this challenge, we first introduce a unified row-sampling based framework that gives algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and -subspace embeddings in the sliding window model, which often use nearly optimal space and achieve nearly input sparsity runtime.