Principal Investigator Piotr Indyk
Project Website http://www.nsf.gov/awardsearch/showAward?AWD_ID=1535851&HistoricalAwards=false
Project Start Date September 2015
Project End Date August 2018
The Discrete Fourier Transform (DFT) is a powerful tool used in many big data domains, including multimedia processing, medical imaging, genomics research, astronomy, seismology for oil and gas reserve discovery, and malicious traffic detection in cybersecurity domains. Building upon a recent breakthrough by the researchers behind this project, this award will develop the algorithmic and system foundations for practical high-spped DFT over sparse data sets. Addressing this goal involves highly interdisciplinary research encompassing ideas and techniques from mathematics, theoretical computer science, software design, and specific application areas such as wireless networks.
The project will be multi-pronged, focusing on three main themes: (a) Algorithms: The PIs will develop a family of algorithms that are faster, simpler and more accurate than the current state of the art in sparse DFT. The new algorithms will be capable of incorporating priors on the structure of the data and apply to multi-dimensional data sets. (b) Software implementations: The PIs will develop software implementations of sparse FFT algorithms and explore algorithm parallelization for further reduction in power and processing time. (c) Applications: The PIs will apply these algorithms and empirically demonstrate them in the context of cost-effective networked system for delivering smart services for intelligent transportation systems using existing e-toll transponders.