CAREER: Sketching Algorithms for Massive Data

大规模数据集的草图是对数据集的一些压缩，它仍然允许回答（有时只是近似地）一些预先指定的数据查询类型。对于许多感兴趣的查询类型，事实证明存在提供指数级小压缩的草图。这一特性使得草图绘制方法在应对最近数据爆炸的趋势中普遍存在，以减少通信带宽和所需的存储容量。草图也被应用于获得某些高维问题的算法加速，如最近邻搜索、聚类和大矩阵的低秩近似，以及在一个被称为压缩感知的领域中实现更有效的信号采集。本研究计划进一步了解素描的三个相互交织的子主题：流、降维和压缩感知。PI将调查的一个基本问题是，是否可以设计出适度“通用”的草图，因为相同的草图可以用来回答许多不同类型的查询。在许多问题中，降维已经成功地用于规避所谓的“维数诅咒”，在这些问题中，最著名的算法的运行时间随着维数的增加而减少。本研究计划研究近似质量、数据集中向量数量和目标维度之间的权衡，并缩小已知上界和下界之间的差距。压缩传感已经在磁共振成像和摄影等不同领域得到了应用。本研究计划研究更有效的压缩感知方案，以提供各种类型的近似恢复保证。

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.