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) 应用：PI 将应用这些算法，并在具有成本效益的网络系统背景下进行实证演示，以便使用现有的电子收费应答器为智能交通系统提供智能服务。

项目成果

Set Cover in Sub-linear Time

以亚线性时间设定封面

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