  There is an increasing body of work exploring the integration of random
projection into algorithms for numerical linear algebra. The primary motivation
is to reduce the overall computational cost of processing large datasets. A
suitably chosen random projection can be used to embed the original dataset in
a lower-dimensional space such that key properties of the original dataset are
retained. These algorithms are often referred to as sketching algorithms, as
the projected dataset can be used as a compressed representation of the full
dataset. We show that random matrix theory, in particular the Tracy-Widom law,
is useful for describing the operating characteristics of sketching algorithms
in the tall-data regime when $n \gg d$. Asymptotic large sample results are of
particular interest as this is the regime where sketching is most useful for
data compression. In particular, we develop asymptotic approximations for the
success rate in generating random subspace embeddings and the convergence
probability of iterative sketching algorithms. We test a number of sketching
algorithms on real large high-dimensional datasets and find that the asymptotic
expressions give accurate predictions of the empirical performance.
