Search Mailing List Archives
[theory-seminar] Theory Lunch 5/26: Yeshwanth Cherapanamjeri (Berkeley)
junyaoz at stanford.edu
Sun May 22 20:04:43 PDT 2022
This week's theory lunch will take place Thursday at noon in the Engineering Quad<https://www.google.com/maps/place/Science+%26+Engineering+Quad+Courtyardemail@example.com,-122.1765394,17z/data=!3m1!4b1!4m5!3m4!1s0x808fbb8ce58bcc27:0x677c06a883bb7bb7!8m2!3d37.428484!4d-122.1743507>. We'll start with some socializing, followed by a talk at 12:30pm. Yeshwanth will tell us about: Uniform Approximations for Randomized Hadamard Transforms
Abstract: In this talk, I will present some recent work establishing concentration properties for a class of structured random linear transformations based on Hadamard matrices. This class of matrices has been adopted as a computationally efficient alternative to "fully" random linear transformations (for instance, a matrix of iid Gaussians) in applications ranging from dimensionality reduction and compressed sensing to various high dimensional machine learning scenarios. However, previous theoretical results only apply to the "low-dimensional" setting where a small number of rows are sampled from a full transformation matrix. I will present a full proof of our "high-dimensional" result where we show that as for as the distribution of the entries of the output are concerned, these structured transformations behave much the same as a fully random transformation. I will then describe an application of our inequality to the practically relevant setting of kernel approximation where we obtain guarantees competitive with those for fully random matrices by Rahimi and Recht.
Based on joint work with Jelani Nelson. Link to paper: https://arxiv.org/abs/2203.01599
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar