AitF: FULL: Sparse Fourier Transform: From Theory to Practice

AitF：FULL：稀疏傅里叶变换：从理论到实践

• 批准号: 1535851
• 负责人: Piotr Indyk
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1535851&HistoricalAwards=false
• 关键词: AitF; FULL; Sparse; Fourier; Transform

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.

离散傅立叶变换（DFT）是一种强大的工具，用于许多大数据领域，包括多媒体处理、医学成像、基因组学研究、天文学、石油和天然气储量发现的地震学以及网络安全领域的恶意流量检测。 基于该项目背后的研究人员最近取得的突破，该奖项将为稀疏数据集上的实际高速DFT开发算法和系统基础。为达致这个目标，研究人员将进行高度跨学科的研究，包括数学、理论计算机科学、软件设计和特定应用领域（如无线网络）的思想和技术。该项目将多管齐下，集中于三个主题：（a）算法：PI将开发一系列算法，这些算法比稀疏DFT的当前最新技术更快、更简单和更准确。新的算法将能够将先验数据的结构，并适用于多维数据集。(b)软件实现：PI将开发稀疏FFT算法的软件实现，并探索算法并行化，以进一步降低功耗和处理时间。(c)应用领域：研究人员将应用这些算法，并在使用现有电子收费转发器为智能运输系统提供智能服务的具有成本效益的网络系统的背景下，以经验证明它们。

项目成果

Set Cover in Sub-linear Time

以亚线性时间设定封面

• 发表时间: 2018
• 期刊: Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Indyk, Piotr;Mahabadi, Sepideh;Rubinfeld, Ronitt;Vakilian, Ali;Yodpinyanee, Anak
• 通讯作者: Yodpinyanee, Anak