In recent years, using signal sparsity has proven to be an important technique in many problems of practical interest. Spurred by the seminal work on Compressive Sensing of Candes and Tao (2006) and Donoho (2006), much attention has focussed on devising fast, efficient, and robust algorithms for problems where the underlying dataset is highly “compressible”. In this talk, we look at several examples of such problems and present our recent work this direction. The results presented here are based on joint work with Prof Sidharth Jaggi, Prof Minghua Chen, Sheng Cai, Chun Lam Chan, and Mohammad Jahangoshahi.
In the first part of this talk, we present a class of sparse measurement matrices and a corresponding algorithm that we call SHO-FA (for SHort and FAst) that, with high probability over the measurement matrix, can reconstruct a real-valued signal with sparse support. The SHO-FA algorithm is the first to simultaneously have the following properties: (a) the number of measurements required scales linearly with the sparsity, k, and is independent of the ambient dimension, n, (b) the bit-precision of each measurement and each arithmetic operation is O(log(n)), (c) the computational complexity of decoding is O(k) arithmetic operations, and (d) if the reconstruction goal is simply to recover a single component of x instead of all of x, with high probability, this can be done in constant time.
Next, we argue that our algorithm applies to several settings that go beyond compressive sensing. As an example, we consider the problem of network delay tomography via path measurements. While this gives rise to a natural compressive sensing problem, unlike traditional compressive sensing, the measurement design here is constrained by the network topology. We briefly describe an algorithm that we call FRANTIC (for Fast Reference-based Algorithm for Network Tomography vIa Compressive sensing) that builds upon our previous algorithm SHO-FA and and show that O(k log n/logM) measurements suffice for FRANTIC. Further, the computational complexity of decoding is at most O(k log n/log M).
In the final part of this talk, we describe two related measurement models – group testing and threshold group testing. Again, under the assumption that the sample is sparse, we briefly describe new algorithms for these setups that improve upon prior known algorithms in terms of either computational complexity or measurement rate, or both.
Dr. Mayank Bakshi is a postdoctoral fellow at the Institute of Network Coding, CUHK. He finished his PhD in Electrical Engineering from California Institute of Technology, USA in 2011. Prior to that, he did his Master and Bachelor degrees in Electrical Engineering at Indian Institute of Technology, Kanpur, India in 2005 and 2003 respectively. His research focuses on Network Coding, Data Compression, and Compressive Sensing.
