# Projection-Cost-Preserving Sketches: Proof Strategies and Constructions

arXiv: https://arxiv.org/abs/2004.08434 · HTML: https://mlsanity.com/paper/2004.08434/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2020.

## Built on by (most cited first, 6 of 6)

- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms](https://mlsanity.com/paper/2408.08494/) (2024)
- [Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation](https://mlsanity.com/paper/2508.04444/) (2025)

## Abstract (arXiv)

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. We also refer the reader to [CYD19], which gives a similar simplified exposition of the proof covered in Section 2.