Date of Award

8-2017

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Mathematical Sciences

Committee Member

Dr. Shuhong Gao, Committee Chair

Committee Member

Dr. Gretchen Matthews

Committee Member

Dr. Felice Manganiello

Committee Member

Dr. June Luo

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.

Share

COinS