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

Michigan State University, East Lansing MI

Investigators

Abstract

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.