Randomized Low-Rank Approximation of Monotone Matrix Functions

David Persson, Daniel Kressner

TL;DR

This paper introduces funNyström, a novel and efficient algorithm for approximating matrix functions of large, symmetric positive semi-definite matrices. Unlike existing methods that require expensive matrix-vector products with the function itself, funNyström leverages a Nyström approximation of the original matrix, significantly reducing computational cost while maintaining accuracy, especially for monotone functions.

What Problem Does This Paper Address?

Computing matrix functions, such as the square root or logarithm, of large matrices is a common but computationally intensive task in fields like statistical learning and inverse problems. Standard approaches often rely on randomized low-rank approximation techniques, which typically require performing matrix-vector products (MVPs) with the matrix function itself. However, these MVPs can be significantly more expensive than MVPs with the original matrix, even when approximated using methods like Lanczos. This paper addresses the challenge of efficiently computing low-rank approximations of matrix functions by developing a method that avoids direct computation with the function, instead relying on approximations of the base matrix.

Methods

The core contribution is the funNyström algorithm. It works by first obtaining a Nyström approximation of the input matrix $A$, denoted as $\hat{A}$. Then, instead of applying the function $f$ to $A$ and then approximating its low-rank structure, funNyström applies the function $f$ to the Nyström approximation $\hat{A}$ to obtain an approximation of $f(A)$. This approach is particularly effective when the function $f$ is monotone and $f(0)=0$. The paper also introduces funNyström++, which combines funNyström with the Hutch++ algorithm for improved trace estimation. The theoretical analysis provides probabilistic error bounds for the approximation in various norms (Frobenius, nuclear, and operator norms), demonstrating that funNyström achieves comparable accuracy to more expensive methods with fewer MVPs.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments using synthetic matrices and matrices derived from Gaussian process covariance kernels and Bayesian inverse problems.

Key Insights and Ideas

  • Bypassing Expensive MVPs: The most significant insight is that for monotone functions $f$ with $f(0)=0$, one can approximate $f(A)$ by applying $f$ to a low-rank approximation of $A$, completely avoiding the need for costly MVPs with $f(A)$.
  • Leveraging Nyström Approximation: The Nyström approximation of $A$ serves as a crucial stepping stone, providing a low-rank representation that can be efficiently transformed by the function $f$.
  • Theoretical Guarantees for Monotone Functions: The paper provides rigorous probabilistic error bounds for funNyström, showing its effectiveness for a broad class of monotone functions, including the matrix square root and logarithm.
  • Efficiency Gains: The method offers substantial computational savings, requiring significantly fewer MVPs with the original matrix $A$ compared to methods that approximate $f(A)$ directly.

Key Results

  • Theoretical Bounds: The paper derives probabilistic error bounds for funNyström in Frobenius, nuclear, and operator norms. These bounds show that funNyström achieves accuracy comparable to more expensive methods.
  • Computational Efficiency: Numerical experiments demonstrate that funNyström requires substantially fewer matrix-vector products with $A$ to achieve a desired accuracy compared to existing methods, sometimes by orders of magnitude.
  • Improved Trace Estimation: The funNyström++ method, combining funNyström with Hutch++, offers a more efficient way to estimate the trace of matrix functions.
  • Performance on Various Functions: The method is shown to perform well for functions like the matrix square root and logarithm across different types of test matrices.

Limitations and Future Work

  • Monotone Function Requirement: The theoretical guarantees and the core method are primarily developed for monotone functions satisfying $f(0)=0$. While the paper suggests extensions and discusses applications, the primary focus is on this class of functions.
  • Oversampling Parameter: The performance and error bounds depend on an oversampling parameter $p$. While the paper provides guidance, optimal selection might require tuning.
  • Future Work: The authors suggest that their bounds can be further tightened, particularly for cases with small $q$. They also mention that the method is of interest for estimating quantities associated with $f(A)$, such as traces and diagonal entries, and propose funNyström++ as a step in this direction. The paper also hints at extensions for non-monotone functions or different matrix properties, though these are not the main focus.

Summary updated

Abstract

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öm 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öm, a simple and inexpensive method that constructs a low-rank approximation of $f(A)$ directly from a Nyström approximation of $A$, completely bypassing the need for matrix-vector products with $f(A)$. It is sensible to use funNyström 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öm tends to return an approximation that compares well with the best low-rank approximation of $f(A)$. Furthermore, compared to existing methods, funNyström 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öm++, a combination of funNyström with the recently developed Hutch++ method for trace estimation.
BibTeX
@article{persson2023randomized,
  author = {David Persson and Daniel Kressner},
  title = {{Randomized Low-Rank Approximation of Monotone Matrix Functions}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2023},
  doi = {10.1137/22m1523923},
}
Figure