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）软件实现：PIS将开发稀疏FFT算法的软件实现，并探索算法并行化，以进一步减少功率和处理时间。 （c）应用程序：PIS将应用这些算法，并在经验上证明它们在具有成本效益的网络系统的背景下，用于使用现有的电子收费传输器为智能运输系统提供智能服务。

项目成果

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