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.