Randomized Low-Rank Approximation of Monotone Matrix Functions

DOI10.1137/22M1523923MaRDI QIDQ6166056zbMATH OpenFDO

Authors David Persson, Daniel Kressner

Publication date 6 July 2023

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.11023

zbMATH Keywords

low-rank approximationmatrix functionsrandomized numerical linear algebra

Mathematics Subject Classification ID

Numerical computation of matrix exponential and similar matrix functions (65F60) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

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"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.

Recommendations

• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
• Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
• Randomized methods for matrix computations

Cites work

• scientific article; zbMATH DE number 1953444 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 967931 (Why is no real title available?)
• A numerical study of large sparse matrix exponentials arising in Markov chains.
• A-optimal design of experiments for infinite-dimensional Bayesian linear inverse problems with regularized _0-sparsification
• An estimator for the diagonal of a matrix
• Assessing stochastic algorithms for large scale nonlinear least squares problems using extremal probabilities of linear combinations of gamma random variables
• Block Krylov subspace methods for functions of matrices. II: Modified block FOM
• Comparison of norms \(|||f(A)-f(B)|||\) and \(|||f(|A-B|)|||\)
• Extension of Rotfel'd Theorem
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• Faster kernel ridge regression using sketching and preconditioning
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Functions of Matrices
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• Improved bounds on sample size for implicit matrix trace estimators
• Inverse problems: a Bayesian perspective
• Linear model reduction and solution of the algebraic Riccati equation by use of the sign function†
• Monte Carlo Methods for Estimating the Diagonal of a Real Symmetric Matrix
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices
• Network properties revealed through matrix functions
• Numerical methods for large eigenvalue problems
• On randomized trace estimates for indefinite matrices with an application to determinants
• Practical sketching algorithms for low-rank matrix approximation
• Quantitative risk management. Concepts, techniques and tools
• Randomization and reweighted _1-minimization for A-optimal design of linear inverse problems
• Randomized block Krylov subspace methods for trace and log-determinant estimators
• Randomized matrix-free trace and log-determinant estimators
• Randomized methods for matrix computations
• Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
• Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection
• Revisiting the Nyström method for improved large-scale machine learning
• Sharper bounds for regularized data fitting
• The scaling and squaring method for the matrix exponential revisited

Cited in

(12)

• Randomized Nyström approximation of non-negative self-adjoint operators
• Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions
• Algorithm-agnostic low-rank approximation of operator monotone matrix functions
• Krylov-Aware Stochastic Trace Estimation
• Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
• Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
• Faster randomized partial trace estimation
• Preorderings, monotone functions, and best rank \(r\) approximations with applications to classical MDS
• Norm and trace estimation with random rank-one vectors
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices

This page was built for publication: Randomized Low-Rank Approximation of Monotone Matrix Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166056)