Skip to contentSkip to filters

We use cookies for analytics.

Sketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I

David Woodruff

Carnegie Mellon University

Recording

59 min

Abstract

This tutorial surveys nearly optimal algorithms for regression, low-rank approximation and related numerical problems. The central approach is sketch and solve: compress a large problem into a smaller representation, then apply an algorithm to that reduced problem. These techniques provide fast methods for fundamental machine-learning and numerical-linear-algebra tasks, with running times proportional to the number of nonzero entries in the input.

Topics