Seminar, Hosted by Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University
Closing the Theory-Practice Gap in Oblivious Subspace Embeddings
Abstract
Michal Dereziński discusses oblivious subspace embeddings, random dimension-reduction maps that approximately preserve all vector norms in a low-dimensional subspace. Such maps support least-squares regression and low-rank approximation, yet efficient optimal embedding dimensions have left a gap between theory and practice. Analyzing universality in sparse random matrices leads to a resolution of the Nelson–Nguyen conjecture up to sub-polylogarithmic factors in SODA 2026. Joint work with Shabarish Chenakkod, Xiaoyu Dong, and Mark Rudelson.
Topics
- oblivious subspace embeddings, broader topic: embeddings
- random dimension-reduction maps, search World Wide
- vector norms, search World Wide
- low dimensional subspace
- least-squares regression
- low-rank approximation
- sparse random matrices, broader topic: random matrices
- universality
- Nelson–Nguyen conjecture, search World Wide
- sub-polylogarithmic factors, search World Wide