Back to search

Clemson University

Johnson-Lindenstrauss Transformations

Abstract

dc:description.abstract

With the quick progression of technology and the increasing need to process large data, there has been an increased interest in data-dependent and data-independent dimension reduction techniques such as principle component analysis (PCA) and Johnson\-Lindenstrauss (JL) transformations, respectively. In 1984, Johnson and Lindenstrauss proved that any finite set of data in a high-dimensional space can be projected into a low-dimensional space while preserving the pairwise Euclidean distance within any desired accuracy, provided the projected dimension is sufficiently large; however, if the desired projected dimension is too small, Woodruff and Jayram, and Kane, Nelson, and Meka in 2011 separately proved such a projection does not exist. In this thesis, we answer an open problem by providing a precise threshold for the projected dimension, above which, there exists a projection approximately preserving the Euclidean distance, but below which, there does not exist such a projection. We, also, give a brief survey of JL constructions, covering the initial constructions and those based on fast-Fourier transforms and codes, and discuss applications in which JL transformations have been implemented.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematical Sciences

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Knoll, Fiona
Contributors dc:contributor
  • Dr. Shuhong Gao, Committee Chair
  • Dr. Gretchen Matthews
  • Dr. Felice Manganiello
  • Dr. June Luo

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/1977

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Knoll, Fiona. Johnson-Lindenstrauss Transformations. Dissertation thesis, https://open.clemson.edu/all_dissertations/1977