4.3 Article

RANDOMIZED LOW-RANK APPROXIMATION OF MONOTONE MATRIX FUNCTIONS

期刊

出版社

SIAM PUBLICATIONS
DOI: 10.1137/22M1523923

关键词

low-rank approximation; randomized numerical linear algebra; matrix functions

向作者/读者索取更多资源

This work presents a method called funNystrom for computing low-rank approximations of a matrix function f(A) for a large symmetric positive semidefinite matrix A. Compared to other randomized methods, funNystrom avoids matrix-vector products with f(A) and achieves comparable results to the best low-rank approximation with lower computational cost.
This work is concerned with computing low-rank approximations of a matrix function f(A) for a large symmetric positive semidefinite 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 Nystrom 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 funNystrom, a simple and inexpensive method that constructs a low-rank approximation of f(A) directly from a Nystrom approximation of A, completely bypassing the need for matrix-vector products with f(A). It is sensible to use funNystrom 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 funNystrom tends to return an approximation that compares well with the best low-rank approximation of f(A). Furthermore, compared to existing methods, funNystrom 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 funNystrom++, a combination of funNystrom with the recently developed Hutch++ method for trace estimation.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据