Structural Conditions for Projection-Cost Preservation via Randomized Matrix Multiplication

Agniva Chowdhury, Jiasen Yang, Petros Drineas

Projection-cost preservation is a low-rank approximation guarantee which ensures that the cost of any rank-$k$ projection can be preserved using a smaller sketch of the original da…