Sparse Recovery (SR) refers to a broad collection of techniques that aim to exploit "sparsity" in efficiently reconstructing an unknown high dimensional sparse dataset through low dimensional measurements. In this talk, we present a framework for fast and efficient algorithms for four SR problems -- compressive sensing (CS), compressive phase retrieval, group testing, and network tomography. We explain our main ideas through our CS algorithm SHO-FA and briefly outline algorithms for the other three problems. For each of these, our algorithms are either order-optimal or near-optimal in the sketch length and the time complexity of decoding. Finally, we examine another performance metric - the energy required by the decoding circuit. Working in the "information-friction" framework, we present a lower bound on the decoding energy for CS and outline an algorithm matching this upto a constant factor.
Prof. Mayank Bakshi is affiliated with the Institute of Network Coding (INC) at the Chinese University of Hong Kong. He finished his PhD from California Institute of Technology in 2011 and was a Postdoctoral Scholar at INC from 2012 to 2014. Prior to this, he did his B. Tech and M.Tech from IIT Kanpur in 2003 and 2005 respectively. He is interested in a variety of Information Theoretic problems including Sparse Recovery, Secure Network Coding, and Network Data Compression.