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

• Author / Creator

  Fedoruk, John P

• 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.

• Subjects / Keywords

  • Johnson Lindenstrauss
  • Dimensionality Reduction
  • High-dimensional data

• Graduation date

  Fall 2016

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R30K26K4H

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.