CAREER: Sketching Algorithms for Massive Data

点击翻译按钮获取中文摘要

A sketch of a massive dataset is some compression of it which still allows for answering, sometimes only approximately, some pre-specified types of queries about the data. For many query types of interest, it turns out that sketches exist that provide exponentially smaller compressions. This feature has made sketching methods pervasive in coping with recent trends in data explosion to reduce both communication bandwidth and required storage capacity. Sketching has also been applied to obtain algorithmic speedup for certain high-dimensional problems such as nearest neighbor search, clustering, and low-rank approximation for large matrices, as well as to enable more efficient signal acquisition in a field that has come to be known as compressed sensing. This research plans to further the state of knowledge concerning three intertwined subtopics of sketching: streaming, dimensionality reduction, and compressed sensing.A fundamental question the PI will investigate is whether one can design sketches that are moderately "universal", in that the same sketch can be used to answer many different types of queries. Dimensionality reduction has been successfully used to circumvent the so-called "curse of dimensionality" in many problems, where the best known algorithms have running times that scale poorly with dimension. This research plans to study the tradeoffs between approximation quality, number of vectors in the data set, and target dimension, and to close gaps between known upper and lower bounds. Compressed sensing has found applications in a diverse range of areas, such as magnetic resonance imaging and photography. This research plans to investigate more efficient compressed sensing schemes for providing various types of approximate recovery guarantees.