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
b \in \real^n
or perhaps a tall matrix
A\in \real^{n\times k}
. A sketching matrix is a
d\times n
matrix
S \in \real^{d\times n}
where
d \ll n
. When multiplied into a high-dimensional vector
