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.