CAREER: Next-Generation Algorithmics for Sparse Recovery

职业：下一代稀疏恢复算法

• 批准号: 0743372
• 负责人: Martin Strauss
• 金额: $ 40万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0743372&HistoricalAwards=false
• 关键词: CAREER; Next; Generation; Algorithmics; Sparse

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.

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