2Sketching

The workhorse of RandNLA is a technique called sketching.^[1] Sketching is a way to take a large matrix and create a smaller matrix (called a sketch) that approximates key properties of the original matrix. Which properties are approximated depends on the specific sketching method used, and the application at hand.

An example of sketching is illustrated above. Here a sketching matrix $\vec{S}$ with sketching/embedding dimension $k$ is applied to a $n\times d$ input matrix $\vec{A}$. The resulting $k\times d$ sketch $\vec{S}\vec{A}$ is much smaller than the original matrix.

When choosing a sketching distribution, two important considerations are:

• How fast the sketching matrix can be generated and applied to $\vec{A}$, and

• How well the sketch $\vec{S}\vec{A}$ approximates the original matrix $\vec{A}$.

While these two considerations are often at odds with each other, by choosing the sketch at random from a suitable distribution, we can often achieve a good balance between the two. In fact, in many algorithms in RandNLA, the randomness in the sketching matrix is the only source of randomness in the entire problem, and is only needed to ensure the above two considerations.

In this book, we treat sketches that mix the rows of $\vec{A}$ and sketches that subsample the rows of $\vec{A}$ as conceptually different. We primarily focus on algorithms based on mixing-based sketches, since these tend to be most suitable as a default choice algorithm in many settings. We discuss subsampling-based methods, which can provide substantial speedups in certain contexts, in Chapter 7.