Date of Award
Doctor of Philosophy (PhD)
Dr. Shuhong Gao, Committee Chair
Dr. Gretchen Matthews
Dr. Felice Manganiello
Dr. June Luo
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.
Knoll, Fiona, "Johnson-Lindenstrauss Transformations" (2017). All Dissertations. 1977.