Better Fast Algorithms for Large and High-Dimensional Datasets: Sparse Fourier Transforms and Fast Density Estimators

在过去的几十年里，由于计算机和通信技术的快速发展，大型高维数据集的规模、范围和重要性一直在以惊人的速度增长。 因此，分析大量高维数据在包括分子生物学、基因组学、金融、市场营销、经济学、社会学和流行病学等在内的广泛学科中变得越来越必要。对于快速计算技术的需求，可以快速准确地处理，压缩和减少巨大的数据集，而不会丢失重要信息。这项研究将开发快速计算方法，由严格的理论保证支持，在分析这样的大型和高维数据集时遇到的两种重要类型的问题：（i）近似大数据集的离散傅立叶变换，以及（ii）估计大数据和高维数据的统计特性。解决这两组问题的困难源于输入数据集的庞大规模和复杂性，这限制了现有计算方法的适用性。在这两种情况下，将开发新的和计算上易于处理的算法，利用隐藏的简化结构（傅立叶稀疏在第一种情况下，和内在的低维几何结构在第二种情况下），往往存在于大型和高维数据集在实践中。

The size, scope, and importance of large, high-dimensional data sets have been accelerating at tremendous rates over the last several decades fueled by the rapid proliferation of computers and communication technology. As a result, analyzing massive amounts of high-dimensional data is becoming increasingly necessary in a wide array of disciplines including molecular biology, genomics, finance, marketing, economics, sociology, and epidemiology, among others. The need for fast computational techniques that can both rapidly and accurately process, compress, and reduce huge datasets without losing important information has never been greater.This research will develop fast computational methods, supported by rigorous theoretical guarantees, for two important types of problems encountered during the analysis of such large and high dimensional data sets: (i) approximating discrete Fourier transforms of big data sets, and (ii) estimating the statistical properties of large and high-dimensional data. The difficulty in solving both sets of problems stems from the sheer size and complexity of the input data sets, which limits the applicability of existing computational methods. In both cases, new and computationally tractable algorithms will be developed that take advantage of hidden simplifying structure (Fourier sparsity in the first case, and intrinsic low-dimensional geometric structure in the second) that often exists in large and high-dimensional data sets in practice.