Computer Science/Discrete Mathematics Seminar I

The Johnson-Lindenstrauss lemma (also known as Random Projections) states that any set of n points in Euclidian space can be embedded almost isometrically into another Euclidian space of dimension O(log(n)). The talk will focus on the efficiency of generating, storing, and applying such mappings. I will present ideas used over the years as this problem received better and better solutions. I will also present a very recent and deep connection between this problem and the Restricted Isometry Property studied in the context of Compressed Sensing. This connection gives rise to the best known solution to date. However, it is still believed to be suboptimal. Thus, open problems will also be presented.