论文标题
投影加权草图：证明策略和构造
Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
论文作者
论文摘要
在本说明中，我们说明了[FSS13，CEM+15]中介绍的常见矩阵近似方法（例如随机投影和随机抽样）如何产生投影成本的草图。投影成本的草图是矩阵近似值，对于给定参数$ k $，大约保留了目标矩阵与所有$ k $维二维子空间的距离。此类草图将用于线性代数，数据科学和机器学习的可扩展算法应用。我们的目标是简化[CEM+15]和[CMM17]中引入的证明技术的介绍，以便它们可以作为未来工作的指南。我们还将读者推荐给[CYD19]，该[CYD19]对第2节中涵盖的证明进行了类似的简化说明。
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.
