In this thesis we investigate 3 variations of the classical Johnson-Lindenstrauss (JL) maps. In one direction we build on the earlier work of Wakin and Eftekhari (2015), by considering generalizations to manifolds with boundary. In a second direction we extend the work of Noga Alon (2003) for lower bounds for the final embedding dimension in JL maps. In the third direction, we consider matrices with fast matrix-vector multiply and improve the run-time in the earlier work of Oymak, Recht and Soltanolkotabi (2018), and Ailon and Liberty (2009).This thesis is organized into 6 chapters. The three variations are discussed in chapters 4, 5 and 6. The variation for manifolds with boundary is presented in chapter 4. The lower bound problem is discussed in chapter 5, and chapter 6 is regarding the run-time improvements. The first chapter is an introduction to Johnson-Lindenstrauss maps. The second chapter is about a regularity parameter called reach and geometrical estimates for manifolds. The third chapter is regarding two geometry questions about reach that arise from the discussions in chapter 2.
Read
