CAREER: Next-Generation Algorithmics for Sparse Recovery

稀疏恢复是有效地跟踪d中最大的m个项目的问题。这包括跟踪雷达图像中m个最亮的光点或磁共振图像中m个最显著的特征。许多社区，包括理论计算机科学界，都已经解决了这些问题。理论计算机科学界对算法中的随机性和近似性的原则性方法导致的解决方案比传统方法明显更有效，特别是当问题的大小d很大时，就像许多雷达和医学成像问题的情况一样。但是，尽管理论上的进步带来了巨大的希望，但到目前为止，大规模数据集的处理方式在实践中几乎没有什么戏剧性的影响。对于许多海量数据集算法，新算法在重要方面比经典算法快得多。指数级的算法最终必然会取代现有的算法。这个项目解决了雷达或医学成像中出现的海量数据集问题。它通过理论计算机科学家和工程师之间的合作，将稀疏恢复方面的理论进步带到了这些领域。

Sparse recovery is the problem of efficiently tracking the m largest items out of d. This includes tracking m brightest blips in a RADAR image or the m most prominent features in a Magentic Resonance image. Many communities, including the theoretical computer science community, have addressed these problems. The theoretical computer science community's principled approach to randomness and approximation in algorithms leads to solutions that are remarkably more efficient than traditional approaches, especially when the size d of the problem is large, as is the case in many RADAR and medical imaging problems. But, despite the tremendous promise of theoretical advances, to date there has been little dramatic impact on the way massive datasets are handled in practice. For many massive dataset algorithms, the new algorithms are exponentially faster than classical algorithms in important respects. Exponentially algorithms will eventually, of necessity, replace existing algorithms.This project addresses massive dataset issues that arise in RADAR or medical imaging. It brings theoretical advances in sparse recovery to those fields through collaboration between theoretical computer scientists and engineers.