Matrix computations lie at the core of a broad range of methods in data analysis and machine learning, and certain numerical linear algebra primitives (e.g. linear least-squares regression and principal component analysis) are widely and routinely used. Devising scalable algorithms that enable large scale computation of the aforementioned primitives is crucial for meeting the challenges of Big Data applications. Sketching has recently emerged as a powerful dimensionality reduction technique for scaling-up these primitives in the presence of massive data, for an extensive class of applications. This course will give an introduction to sketching theory and practice. Applications of the techniques for data analysis and machine learning applications will also be discussed.

The course will cover the following subjects, time permitting:

1. Random projections, Johnson-Lindenstrauss lemmas and subspace embeddings

2. Approximating matrix multiplication; scalar and matrix concentration inequalities

3. Faster least squares linear regression

4. Low rank matrix approximations, approximate PCA and CCA

5. Sketching methods for kernel-based learnin

6. Streaming algorithms