Papers › Randomized low-rank approximation of monotone matrix functions
Randomized low-rank approximation of monotone matrix functions
David Persson, Daniel Kressner
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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). It is sensible to use funNystr\"om whenever f is monotone and satisfies f(0) = 0. Under the stronger assumption that f is operator monotone, which includes the matrix square root A^(1/2) and the matrix logarithm log(I+A), we derive probabilistic bounds for the error in the Frobenius, nuclear, and operator norms. These bounds confirm the numerical observation that funNystr\"om tends to return an approximation that compares well with the best low-rank approximation of f(A). Furthermore, compared to existing methods, funNystr\"om requires significantly fewer matrix-vector products with A to obtain a low-rank approximation of f(A), without sacrificing accuracy or reliability. Our method is also of interest when estimating quantities associated with f(A), such as the trace or the diagonal entries of f(A). In particular, we propose and analyze funNystr\"om++, a combination of funNystr\"om with the recently developed Hutch++ method for trace estimation.
In Syntology View this paper on Syntology: its repositories, every harvested function with whether it ran, its licence and the call to fetch it.
Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections