Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Sketching methods are remarkably effective at solving large-scale data science problems, sidestepping the curse of dimensionality. Classic results, like the Johnson-Lindenstrauss lemma, show that randomly projecting data from a high dimension d into a much smaller subspace of dimension k ≪ d preserves important information about the data.

However, modern data often exhibits tensor structure, particularly in machine learning and scientific computing applications. To handle this, practitioners rely on tensor-structured sketching methods — most notably, Khatri-Rao sketching. Yet, when applied to these structured sketches, the classical theory of random projections falters. Existing upper bounds suggest that achieving even basic Johnson-Lindenstrauss guarantees suddenly requires a subspace dimension k that is exponentially large in the tensor order.

This talk will discuss three key ideas about tensor-structured sketching:

1. Upper Bounds: What sketching dimension k suffices to solve classic linear algebra problems like low-rank approximation and trace estimation?

2. Lower Bounds: What is "The Curse of Overwhelming Orthogonality", and why does it mean that k must be exponentially large?

3. Beyond the Worst-Case: When is the existing theory too pessimistic, failing to reflect empirical success? What are the associated open problems?

This talk covers joint work with Haim Avron, Chris Camano, Ethan Epperly, Will Swartworth, Joel Tropp, and David Woodruff.