Computing and Mathematical Sciences Colloquium

Our era of data deluge is seriously challenging our ability to scale in diverse fields in engineering and the sciences (both physical and data-oriented). Sparsity in data structure offers promise in addressing this challenge, as evidenced by the success of fields like compressed sensing. However, existing popular methods are typically based on convex relaxation techniques, which scale polynomially with the problem dimension, and are getting increasingly hard to scale. In this talk, we will view the problem of sparse support recovery in high-dimensional problems through a novel sparse-graph coding lens. Using a simple divide-and-conquer philosophy and fast peeling-based decoding, we show how to achieve sub-linear time costs for both acquisition and computation. This helps us break the complexity barrier while providing strict performance guarantees, and has the potential to enable "real-time" processing of massive data-sets featuring sparsity. We will describe how our framework can be used for a host of problems from sparse Discrete Fourier Transform computation to support recovery in compressed sensing and compressed phase-retrieval systems to group testing, with applications to imaging, optics, quantum information systems, and machine learning.