Tight Bounds for L1 Oblivious Subspace Embeddings

September 17, 2019, 5:10 PM - 5:50 PM


Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

David P. Woodruff, Carnegie Mellon University

Oblivious subspace embeddings have proven to be an essential ingredient for approximately solving numerical linear algebra problems, such as regression and low-rank approximation.

While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of p = 1, much less was known. In this talk I will present our results on l1 oblivious subspace embeddings, including (i) nearly optimal lower bounds and (ii) new constructions for sparse l1 oblivious subspace embeddings.

Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise lp low rank approximation. Our results give improved algorithms for these applications.

Based on joint work with Ruosong Wang.