Dimensionality Reduction via the Johnson and Lindenstrauss Lemma: Mathematical and Computational Improvements

Abstract

In an increasingly data-driven society, there is a growing need to simplify high-dimensional data sets. Over the course of the past three decades, the Johnson and Lindenstrauss (JL) lemma has evolved from a highly abstract mathematical result into a useful tool for dealing with data sets of immense dimensionality. The lemma asserts that a set of high-dimensional points can be projected into lower dimensions while approximately preserving the pairwise distance structure. The JL lemma has been revisited many times, with improvements to both its sharpness (i.e., bound on the reduced dimensionality) and its simplicity (i.e., mathematical derivation). In 2008 Matousek provided generalizations of the JL lemma that lacked the sharpness of earlier approaches. The current investigation seeks to strengthen Matousek's results by maintaining generality while improving sharpness. First, Matousek's results are reproved with more detailed mathematics and, second, computational solutions are obtained on simulated data in Matlab. The reproofs result in a more specific bound than suggested by Matousek while maintaining his level of generality. However, the reproofs lack the sharpness suggested by earlier, less general approaches to the JL lemma. The computational solutions suggest the existence of a result that maintains Matousek's generality while attaining the sharpness suggested by his predecessors. The collective results of the current investigation support the notion that computational solutions play a critical role in the development of mathematical theory.