Randomized low-rank approximation of monotone matrix functions

Understand

This work is concerned with computing low-rank approximations of a matrix function $f(A)$ for a large symmetric positive semi-definite matrix $A$, a task that arises in, e.g., statistical learning and inverse problems.

• The application of popular randomized methods, such as the randomized singular value decomposition or the Nystr\"om approximation, to $f(A)$ requires multiplying $f(A)$ with a few random vectors.
• A significant disadvantage of such an approach, matrix-vector products with $f(A)$ are considerably more expensive than matrix-vector products with $A$, even when carried out only approximately via, e.g., the Lanczos method.
• In this work, we present and analyze funNystr\"om, a simple and inexpensive method that constructs a low-rank approximation of $f(A)$ directly from a Nystr\"om approximation of $A$, completely bypassing the need for matrix-vector products with $f(A)$.