Structural conditions for projection-cost preservation via randomized matrix multiplication

DOI10.1016/j.laa.2019.03.013OpenAlexW2963542512WikidataQ128199708 ScholiaQ128199708MaRDI QIDQ2419040

Jiasen Yang, Agniva Chowdhury, Petros Drineas

Publication date: 29 May 2019

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

matrix sketchingrandomized linear algebraleverage scoresprojection-cost preservation

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20) Numerical linear algebra (65Fxx)

Uses Software

• RandNLA

Cites Work

• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• CUR matrix decompositions for improved data analysis
• Faster least squares approximation
• Clustering large graphs via the singular value decomposition
• NP-hardness of Euclidean sum-of-squares clustering
• A trace inequality of John von Neumann
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Low-Rank Approximation and Regression in Input Sparsity Time
• Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
• Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

This page was built for publication: Structural conditions for projection-cost preservation via randomized matrix multiplication