Faculty Recruiting Support CICS

Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform

29 Oct
Tuesday, 10/29/2019 4:00pm to 5:00pm
Computer Science Building Room 140
Theory Seminar
Speaker: Ishan Khatri

The Johnson-Lindenstrauss lemma states that n points in Euclidean space can be projected down to k dimensions while also preserving pairwise distances with error at most 1+e. This process usually requires a large dense random matrix. The Fast JL Transform is a method which takes advantage of a Fast Fourier Transform to lower the complexity of computing the random projection. This resulting transformation can be used to speed up any algorithm that relies on low distortion random projections. We will discuss in detail the fast JL transformation as well as its applications such as the fastfood transform which can be used to speed up convolutional neural networks.