Structural Conditions for Projection-Cost Preservation via Randomized Matrix Multiplication
This work provides a theoretical framework for improving efficiency in data analysis, but it is incremental as it builds on known methods without introducing new algorithms.
The paper tackles the problem of ensuring projection-cost preservation in low-rank approximations by presenting a general structural result with four sufficient conditions, which can be satisfied using existing randomized linear algebra tools.
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 data matrix. We present a general structural result outlining four sufficient conditions to achieve projection-cost preservation. These conditions can be satisfied using tools from the Randomized Linear Algebra literature.