EE Student Information

The Department of Electrical Engineering supports Black Lives Matter. Read more.

• • • • •

EE Student Information, Spring Quarter through Academic Year 2020-2021: FAQs and Updated EE Course List.

Updates will be posted on this page, as well as emailed to the EE student mail list.

Please see Stanford University Health Alerts for course and travel updates.

As always, use your best judgement and consider your own and others' well-being at all times.

Probability Seminar presents "Fast and memory-optimal dimension reduction using Kac's walk"

Topic: 
Fast and memory-optimal dimension reduction using Kac's walk
Monday, October 26, 2020 - 4:00pm
Venue: 
Zoom
Speaker: 
Vishesh Jain (MIT)
Abstract / Description: 

Introduced in the 1950s by Mark Kac as a toy model for a one-dimensional Boltzmann gas, the Kac walk is the following simple and well-studied Markov chain on the special orthogonal group: at every time step, sample two distinct uniform coordinates $i,j$ and a uniform angle $\theta$, and rotate in the $(i,j)$-plane by $\theta$. In this talk, I will discuss how the Kac walk can be used for the purpose of dimensionality reduction, specifically, for the design of linear transformations with optimal Johnson–Lindenstrauss and Restricted Isometry properties, and which support memory-optimal fast matrix-vector multiplication. I will also discuss the performance of a variant of the Kac walk, for which $\theta = \pi/4$ at every time step

This is joint work with Natesh S. Pillai (Harvard), Ashwin Sah (MIT), Mehtaab Sawhney (MIT), and Aaron Smith (U Ottawa).