Supercharging trace estimation for concave matrix functions

We propose the _accelerated funNystr\"om++_ method for computing spectral sums $tr(f(\mathbf{A}))$ for positive increasing concave functions $f$, like the log determinant. Our methods requires asymptotically fewer matrix–vector products (matvecs) with \(\mathbf A\) than all prior methods. In particular, despite Hutch++ and Lanczos-FA each having optimal matvec complexity for their respective tasks, their composition does not provide the optimal complexity matvec for computing spectral sums. Our method is especially efficient when $\mathbf{A}$ has large condition number. We pair our algorithm with a high-quality implementation, provided as part of the open-source RandLAPACK library. We demonstrate the effectiveness of our algorithm and our implementation on a variety of real-world ML tasks, including evaluating Vendi scores and log-determinants. Compared to existing methods, we achieve an order of magnitude improvement in matvec complexity and wall-clock runtime.