Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
From MaRDI portal
Abstract: Given a real matrix A with n columns, the problem is to approximate the Gram product AA^T by c << n weighted outer products of columns of A. Necessary and sufficient conditions for the exact computation of AA^T (in exact arithmetic) from c >= rank(A) columns depend on the right singular vector matrix of A. For a Monte-Carlo matrix multiplication algorithm by Drineas et al. that samples outer products, we present probabilistic bounds for the 2-norm relative error due to randomization. The bounds depend on the stable rank or the rank of A, but not on the matrix dimensions. Numerical experiments illustrate that the bounds are informative, even for stringent success probabilities and matrices of small dimension. We also derive bounds for the smallest singular value and the condition number of matrices obtained by sampling rows from orthonormal matrices.
Recommendations
- A fast randomized algorithm for the approximation of matrices
- Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
- A randomized algorithm for the decomposition of matrices
- Learning Theory
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
Cites work
- An improved approximation algorithm for the column subset selection problem
- Approximating Matrix Multiplication for Pattern Recognition Tasks
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Compressed matrix multiplication
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient Computing of Regression Diagnostics
- Exact matrix completion via convex optimization
- Fast approximation of matrix coherence and statistical leverage
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Fast monte-carlo algorithms for finding low-rank approximations
- Faster least squares approximation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Generalized Rank-Constrained Matrix Approximations
- 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 6472646 (Why is no real title available?)
- Importance sampling for a Monte Carlo matrix multiplication algorithm, with application to information retrieval
- Improved analysis of the subsampled randomized Hadamard transform
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Influential observations, high leverage points, and outliers in linear regression
- Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
- Near Optimal Column-Based Matrix Reconstruction
- Numerical methods for solving linear least squares problems
- On Rank-Revealing Factorisations
- Randomized Algorithms for Matrices and Data
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- Relative-Error CUR Matrix Decompositions
- Sampling algorithms for l₂ regression and applications
- Sampling from large matrices
- Singular values of differences of positive semidefinite matrices
- Tail inequalities for sums of random matrices that depend on the intrinsic dimension
- The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems
- The Hat Matrix in Regression and ANOVA
- The University of Florida sparse matrix collection
- Twice-Ramanujan sparsifiers
- Twice-Ramanujan sparsifiers
- User-friendly tail bounds for sums of random matrices
Cited in
(16)- Sub-sampled Newton methods
- Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
- Far-field compression for fast kernel summation methods in high dimensions
- Structural conditions for projection-cost preservation via randomized matrix multiplication
- Algorithms that satisfy a stopping criterion, probably
- Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
- A probabilistic subspace bound with application to active subspaces
- Perturbation bounds for procrustes, classical scaling, and trilateration, with applications to manifold learning
- Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems
- Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
- A multilevel Monte Carlo estimator for matrix multiplication
- Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems
- The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems
- Stable rank and intrinsic dimension of real and complex matrices
- Bayesian D-optimal experimental designs via column subset selection
- On randomized power methods for computing dominant eigenpairs of symmetric matrices
This page was built for publication: Randomized approximation of the Gram matrix: exact computation and probabilistic bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5251753)
