CAREER: Next-Generation Algorithmics for Sparse Recovery

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

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.