Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds
From MaRDI portal
Publication:5251753
DOI10.1137/130940116zbMath1330.65061DBLPjournals/siammax/HolodnakI15arXiv1310.1502OpenAlexW2964214436WikidataQ57439746 ScholiaQ57439746MaRDI QIDQ5251753
John T. Holodnak, Ilse C. F. Ipsen
Publication date: 21 May 2015
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1310.1502
coherencesingular value decompositionstable rankunbiased estimatormatrix concentration inequalitiesleverage scoresGram product
Numerical solutions to overdetermined systems, pseudoinverses (65F20) Monte Carlo methods (65C05) Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of matrix norms, conditioning, scaling (65F35) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- Tail inequalities for sums of random matrices that depend on the intrinsic dimension
- Faster least squares approximation
- User-friendly tail bounds for sums of random matrices
- Influential observations, high leverage points, and outliers in linear regression
- Numerical methods for solving linear least squares problems
- Exact matrix completion via convex optimization
- Singular Values of Differences of Positive Semidefinite Matrices
- Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
- The university of Florida sparse matrix collection
- IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
- Importance Sampling for a Monte Carlo Matrix Multiplication Algorithm, with Application to Information Retrieval
- Randomized Algorithms for Matrices and Data
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Sampling from large matrices
- Sampling algorithms for l2 regression and applications
- Relative-Error $CUR$ Matrix Decompositions
- Efficient Computing of Regression Diagnostics
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- The Hat Matrix in Regression and ANOVA
- Approximating Matrix Multiplication for Pattern Recognition Tasks
- On Rank-Revealing Factorisations
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Twice-Ramanujan Sparsifiers
- Twice-ramanujan sparsifiers
- The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems
- Generalized Rank-Constrained Matrix Approximations
- Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Near Optimal Column-Based Matrix Reconstruction
- Compressed matrix multiplication
Related Items (12)
Algorithms that satisfy a stopping criterion, probably ⋮ Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning ⋮ Far-field compression for fast kernel summation methods in high dimensions ⋮ A Probabilistic Subspace Bound with Application to Active Subspaces ⋮ Structural conditions for projection-cost preservation via randomized matrix multiplication ⋮ Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction ⋮ A Multilevel Monte Carlo Estimator for Matrix Multiplication ⋮ Sub-sampled Newton methods ⋮ Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems ⋮ Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems ⋮ Low-Rank Matrix Approximations Do Not Need a Singular Value Gap ⋮ Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
Uses Software
This page was built for publication: Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds
