Modern-Day Dimensionality Reduction: Streaming and Sketching Algorithms for Matrix Norms
Abstract
Data dimensionality reduction is a powerful technique, which has led to extremely efficient algorithms for a large number of problems. Roughly peaking, one takes an object and compresses it to a much smaller representation,while preserving critical information about the object. Such compression can come in various forms, such as sampling key features or recording a few linear combinations of the object. The same compression algorithm may be run on anyobject, or the compression could be data-driven and tailored to the specific object. If one wants to check if a property P of the original object holds, one may look for that property in the compressed representation, or one may look for anentirely different property P0 in the compressed representation to certify property P of the original object. We plan to study data dimensionality reduction, both from the perspective of pushing the limits of fundamental problems in datastreamalgorithmics, and from the perspective of the multitude of applications that can benefit from such dimensionality reduction. Given the rich interplay between data stream techniques and other areas, we hope that by studying the mostcentral problems in data streams, new applications will arise, as witnessed multiple times in the past. Conversely, we also hope that by studying the applications, and the specific constraints on dimensionality reduction they impose, new connections can be drawn between them and data-stream algorithms. Our research will focus on four items:1. Characterize the fundamental limits of data-stream algorithms.2. Understand the power of dimensionality reduction for vectors and for matrices.3. Delineate different data-stream models, like insertion-only vs. turnstile, and entry-arrival vs.row-arrival.4. Broaden connections to other areas and further applications.Our research will directly contribute to Topic 1 of the BAA, Research concentration areas (1) and (2). In particular, our sketching and streaming algorithms will allow to approximate matrix norms with a sublinear amount of computational resources. By using matrix norms as a surrogate for the spectrum of a matrix, our methods can build a new framework for a broad class of spectrumbased matrix computations in numerical linear algebra applications. As modern datasets, from text documents and images to social graphs, are often represented as a large matrix, our sketching methods will be applicable in many domains critical for the Navy, including database queries, data mining, network transactions and sensor networks.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 10, 2018
- Source ID
- N000141812364
Entities
People
- Vladimir Braverman
Organizations
- Johns Hopkins University
- Office of Naval Research
- United States Navy