Fetching the paper…

Reading the bibliography…

2020

Projection-Cost-Preserving Sketches: Proof Strategies and Constructions

Musco, Cameron, Musco, Christopher

Original
PDF
Post on X

Understand

In this note we illustrate how common matrix approximation methods, such as random projection and random sampling, yield projection-cost-preserving sketches, as introduced in [FSS13, CEM+15].

A projection-cost-preserving sketch is a matrix approximation which, for a given parameter $k$, approximately preserves the distance of the target matrix to all $k$-dimensional subspaces.
Such sketches have applications to scalable algorithms for linear algebra, data science, and machine learning.
Our goal is to simplify the presentation of proof techniques introduced in [CEM+15] and [CMM17] so that they can serve as a guide for future work.

Projection-Cost-Preserving Sketches: Proof Strategies and Constructions · Around

Built on

Improved approximation algorithms for large matrices via random projections
Tamas Sarlos · 2006
Earlier work this paper cites.
Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
Dan Feldman, Melanie Schmidt, and Christian Sohler · 2013
Earlier work this paper cites.
Sparser Johnson-Lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2014
Earlier work this paper cites.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Earlier work this paper cites.

Similar

Dimensionality reduction for k-means clustering and low rank approximation
Original
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 2015
Cited alongside, same era.
Dimensionality reduction for k-means clustering
Cameron Musco · 2015
Cited alongside, same era.
Optimal approximate matrix product in terms of stable rank
Original
Michael B. Cohen, Jelani Nelson, and David P. Woodruff · 2016
Cited alongside, same era.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B. Cohen, Cameron Musco, and Christopher Musco · 2017
Cited alongside, same era.

Then

Sublinear time low-rank approximation of positive semidefinite matrices
Original
Cameron Musco and David P. Woodruff · 2017
Later among the works it cites.
High-Dimensional Probability: An Introduction with Applications in Data Science
Roman Vershynin · 2018
Later among the works it cites.
Structural conditions for projection-cost preservation via randomized matrix multiplication
Agniva Chowdhury, Jiasen Yang, and Petros Drineas · 2019
Later among the works it cites.
High-Dimensional Statistics: A Non-Asymptotic Viewpoint
Martin J. Wainwright · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…