A Sparse Recovery Framework for Fast and Efficient Network Applications

Modern communication networks present both significant challenges as well as opportunities that are distinct from traditional networks. For example, while the huge number of connected devices in applications such as IoT (Internet of Things) suggests stringent bandwidth and complexity requirements for communication tasks, often, the underlying sparsity in the problem greatly reduces the resources needed. With the above motivation in mind, in this talk, we present a class for sparse recovery algorithms that are optimal or near-optimal in terms of the speed of decoding and the number of measurements needed.

We discuss a novel conceptual framework -- "picking and peeling" -- for fast and efficient algorithms for four important sparse recovery problems -- compressive sensing, compressive phase retrieval, group testing, and network tomography. Using this primitive, we begin by describing our compressive sensing algorithm SHO-FA (for SHOrt and FAst) which achieves a decoding complexity of O(k) while using only O(k) measurements (this is the fastest possible performance in the order sense). Next, we will briefly describe our algorithms for the other three problems. For each of these problems, our algorithms are either order-optimal or near-optimal both in terms of two metrics - the number of measurements and the time complexity of decoding. Finally, we examine another metric for performance - the energy required by the VLSI circuit that implements these algorithms. Surprisingly, even algorithms that are efficient in terms of time complexity are no longer efficient in terms of decoding energy. We show a novel information theoretic lower bound on the decoding energy required in compressive sensing and briefly describe some ideas that may allow us to approach this bound.

Bio: Mayank Bakshi is a Research Assistant Professor at the Institute of Network Coding, Chinese University of Hong Kong. Prior to this, he obtained his B.Tech and M.Tech from IIT Kanpur in 2003 and 2005 respectively, and PhD from Caltech in 2011, all in Electrical Engineering. From 2012-2014, he was a post-doctoral fellow at Institute of Network Coding, CUHK. His research interests include sparse signal recovery, information theoretic security, and network coding.