Fast Algorithms for Structured Sparsity

Chinmay Hegde
Thursday, September 17, 2015 - 3:30pm
B29 Atanasoff Hall
Event Type: 

Fast Algorithms for Structured Sparsity

Date/Time: September 17, 3:40 pm
Location: B29 Atanasoff Hall


Sparse representations have emerged as powerful tools in signal and image processing. However, real-world signals often exhibit rich combinatorial structure beyond mere sparsity. For example, a natural image has the property that its large wavelet coefficients occupy a *subtree* of the wavelet hierarchy. A general approach for capturing this additional structure is to model the support of the signal as belonging to a given family of sets. Computing a sparse representation of the signal then corresponds to the problem of finding the optimal support from the family. This approach has proved to be beneficial in a number of applications including compression, denoising, and machine learning; however, the optimization problem is often computationally difficult, intractable, and impractical for applications where large-scale signals and datasets are commonplace.

In this talk, I will outline my past, as well as more recent, algorithmic work on structured sparse representations of signals, including piecewise constant representations, tree-sparse approximations and graph-sparse approximations. The algorithms borrow several elements from combinatorial optimization including dynamic programming, graph theory, and approximation algorithms. For many problems the algorithms often run in a (nearly) linear running time, enabling their applicability to very large datasets. Time permitting, I will describe how these algorithms can be fruitfully applied to achieve sample-optimal acquisition of image data arising in surveillance and medical image applications.


Chinmay Hegde is an assistant professor in the Electrical and Computer Engineering Department of Iowa State University. He received his B.Tech. degree from the Indian Institute of Technology (Madras) in 2006, and his Ph.D. from Rice University in 2012. From 2012 to 2015 he was a Shell-MIT postdoctoral associate in the Computer Science and Artificial Intelligence Lab (CSAIL) at MIT. He received the Ralph Budd Award for Best Engineering PhD Thesis in Rice University in April 2013, the Best Student Paper Award in SPARS 2009, and the Best Paper Award in ICML 2015. His research interests include signal processing, machine learning, and design and analysis of algorithms.

Colloquia Lecture Chinmay Hegde.pdf