Randomized Dimensionality Reduction Methods for Machine Learning
Abstract
Statement of Work: The PI will investigate and develop randomized methods that preserve the structure of the data for dimensionality reduction. In particular, they will investigate the fundamental Johnson-Lindenstrauss (JL) transform. They will develop fast algorithms, performance proofs, and construction recipes; and extend JL to nonlinear cases. They will apply these transforms to a host of practical applications that include numerical linear algebra, clustering, compressive sensing, machine learning, image and video analysis. Objective: Investigate properties of structure-preserving randomized methods for dimensionality reduction for use in machine learning, linear algebra, and compressed sensing. Also develop performance bounds and efficient algorithms for these methods. Approach: The goal of Nelson’s proposed research is to drive fundamental new progress in dimensionality reduction; more specifically to investigate the Johnson-Lindenstrauss (JL) transform. JL is a linear transform that projects high-D data into low-D subspaces, while approximately preserving pairwise distances. This low-distortion transform is superior to methods that preserve the average pairwise distance (e.g. the often-used Sammons mapping with uncontrollable distortions), because JL has the desirable property of preserving the structure of the data. Nelson will investigate a number of important open questions including time complexity of JL transform, achievable projected dimension when data is dense or well separated or sparse, tradeoffs between sparsity of the transform matrix and distortion error, extensions to nonlinear JL, and more. Dimensionality reduction is a critical step in making computations scalable and tractable and plays an important role in a host of practical applications that include numerical linear algebra (such as approximate regression), clustering, compressive sensing, machine learning, image and video analysis. Overall Merit and ONR Mission/Relevance: This research addresses Information Dominance and Autonomy focus areas. This work is expected to develop effective methods for reducing the dimensionality of the data while preserving the structure of the data, for use in machine learning and other areas. This research will investigate properties of the fundamental Johnson-Lindenstrauss transform for mapping data to lower dimensional spaces while preserving (approximately) the structure of the data. They will develop bounds for the JL transform as well as efficient algorithms.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512388
Entities
People
- Jelani Nelson
Organizations
- Office of Naval Research
- President and Fellows of Harvard College
- United States Navy