Theory, Implementation, and Applications of Sublinear-Time Fourier Transform Algorithms

计算数据的傅立叶表示是一个基础问题，出现在数学、科学和技术的许多领域。 最近，已经提出了一类算法来近似傅立叶变换，具有可证明的质量保证，在显着更少的时间比传统的精确出租所需的。 研究者和他的同事们评估了算法的竞争变化，包括提出的和新的，并从它们中选择最好的用于一般用途以及用于磁共振成像和偏微分方程的解决方案的具体应用，包括对流扩散方程。傅立叶变换是一种具有许多应用的基本技术。 研究人员和他的团队调查了最近的近似方法，这些方法比传统方法更有效。 该团队直接解决了生物医学磁共振成像和液体和气体行为建模的应用，这些应用进一步应用于研究环境中的大气和水体，以及制造业的应用。 研究人员和他的团队也可以使用基本的工具，这些工具将对国外的科学，教育和工程环境中的其他人有用，包括模拟微小粒子的相互作用，可靠的电信和一般的成像。 该项目结合了来自多个学科的尖端技术，并在这些技术及其整合方面培训了一名研究生。

The problem of computing a Fourier representation of data is afundamental one, that arises in many areas of mathematics, science,and technology. Recently, a class of algorithms has been proposed toapproximate the Fourier transform, with provable quality guarantees,in dramatically less time than required by traditional exactalgorithms. The investigator and his colleagues evaluate competingvariations of the algorithm, both proposed and new, and choose thebest from among them for general purpose use as well as for specificapplication to Magnetic Resonence Imaging and solution of partialdifferential equations, including advection-diffusion equations.The Fourier Transform is a fundamental technique with manyapplications. The investigator and his team investigate recentapproximate methods that are dramatically more efficient thantraditional methods. The team directly addresses applications tobiomedical Magnetic Resonance Imaging and the modeling of liquid andgas behavior, which has further applications to studying theatmosphere and bodies of water in the environment, as well asapplications to manufacturing. The investigator and his team alsomake available fundamental tools that will be useful to others in abroad range of scientific, educational, and engineering settingsincluding modeling the interactions of tiny particles, reliabletelecommunications, and imaging generally. The project combinescutting-edge techniques from several disciplines and trains a graduatestudent in these techniques and their integration.