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 and matrix .
