One sketch for all: Theory and Application of Conditional Random Sampling

Conditional Random Sampling (CRS) was originally proposed for efficiently computing pairwise ( l_2, l_1) distances, in static, large-scale, and sparse data sets such as text and Web data. It was previously presented using a heuristic argument. This study extends CRS to handle dynamic or streaming data, which much better reflect the real-world situation than assuming static data. Compared with other known sketching algorithms for dimension reductions such as stable random projections, CRS exhibits a significant advantage in that it is one-sketch-for-all.'' In particular, we demonstrate that CRS can be applied to efficiently compute the l_p distance and the Hilbertian metrics, both are popular in machine learning.