Agenda

Speaker: Thomas Vecchiato, Ca' Foscari

Abstract: 
I will cover the Johnson-Lindenstrauss Lemma, which is a very powerful result, concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The following theorem is having a big impact in several fields, especially in dimensionality reduction. For this reason, in the first part of the seminar, we will briefly see what dimensionality reduction is, in which applications it is used, and why it plays a vital role nowadays. Secondly, we will state the Johnson-Lindenstrauss Lemma (JL Lemma), that is actually a theorem but for historical reasons it is still called lemma, where the main idea is that a set of points n in a high dimensional space can be projected into a much lower dimension space in such a way that the distance between the points are nearly preserved, having a mapping that preserve all the n points simultaneously with a multiplicative epsilon-factor. Next, we will see the proof of the JL Lemma, leaving nothing to chance and clarifying every single point.

In conclusion, we will see some recent advances, studies and extensions of the JL Lemma, where I intend to give a general idea of what they are about. In particular, we will focus on the 'Fast Johnson-Lindenstrauss Transformation' and the 'Database-friendly random projections: JL with binary coins', hot topics and of huge effect in the days that we are living.