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 b or tall matrix A, the sketching matrix S produces compressed or “sketched” versions Sb and SA that are much smaller than the original vector b and matrix A. | Does Sketching Work?