Sketching

Sketching is a probabilistic tool to summarize high-dimensional vectors into low-dimensional vectors, called sketches, while approximately preserving properties of interest. For example, we may sketch vectors in the Euclidean space such that their L2 norm is approximately preserved; or sketch points in an inner product space such that the inner product between any two points is maintained with high probability. This chapter reviews a few data-oblivious algorithms, cherry-picked from the vast literature on sketching, that are tailored to sparse vectors in an inner product space.