In matrix computations, sketching is really a synonym for (linear) dimensionality reduction. Suppose we are solving a problem involving one or more high-dimensional vectors
or perhaps a tall matrix
. A sketching matrix is a
matrix
where
. When multiplied into a high-dimensional vector
or tall matrix
, the sketching matrix
produces compressed or “sketched” versions
and
that are much smaller than the original vector
