Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds

DOI10.1137/130940116zbMath1330.65061arXiv1310.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)

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

zbMATH Keywords

coherencesingular value decompositionstable rankunbiased estimatormatrix concentration inequalitiesleverage scoresGram product

Mathematics Subject Classification ID

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)

Related Items

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

• LAPACK
• UCI-ml
• SparseMatrix
• Blendenpik
• kappa_SQ

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 l₂ 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