Topic 1: Randomized Numerical Linear Algebra for Large-Scale, Efficient Matrix Computations
Abstract
Data dimensionality reduction is a powerful technique, which has led to extremely efficient algorithms for a large number of problems. Roughly speaking, 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 any object, 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 compressedrepresentation, or one may look for an entirely different property P0 in the compressed representation to certify property P of theoriginal object. We plan to study data dimensionality reduction, both from the perspective of pushing the limits of fundamental problems in data-stream algorithmics, and from the perspective of the multitudeof 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 most central 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 spectrum based 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 24, 2023
- Source ID
- N000142312737
Entities
People
- Vladimir Braverman
Organizations
- Office of Naval Research
- Rice University
- United States Navy