On August 8^th, 2019, Professor David Woodruff from Carnegie Mellon University visited Center on Frontiers of Computing Studies (CFCS) and gave a lecture titled "Tight Bounds for L1 Oblivious Subspace Embeddings". Professor Xiaotie Deng from CFCS hosted the lecture.

In the lecture

Professor Xiaotie Deng presents Professor David Woodruff the souvenir

Abstract:

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.

Biography:

David Woodruff is an associate professor at Carnegie Mellon University, where he has been since 2017. Prior to that he was a reearcher at the IBM Almaden Research Center from August, 2007- August, 2017, which he joined after completing his Ph.D. at MIT in theoretical computer science.  His research interests include communication complexity, data stream algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery. He is the recipient of the 2014 Presburger Award and Best Paper Awards at STOC 2013 and PODS 2010. At IBM he was a member of the Academy of Technology and a Master Inventor.