Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
This work is incremental, providing a clearer guide for researchers in computational mathematics and machine learning.
The paper simplifies proof techniques for projection-cost-preserving sketches, which are matrix approximations preserving distances to k-dimensional subspaces, used in scalable algorithms for linear algebra, data science, and machine learning.
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.