Bharti School and Dept. of Electrical Engineering, IIT Delhi
Programme:
Time | Event | Venue |
12:00 - 1:30p | Tutorial on Compressive Sensing by Mayank Bakshi (handout) | IIA - 101 |
3:00 - 4:00 | Research talk on Sparse Recovery by Mayank Bakshi | IIA - 105 |
4:00 - 4:30 | Research talk on Phase Imaging by Kedar Khare | IIA - 105 |
4:30 - 5:00 | Discussion | IIA - 105 |
Speaker biographies
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, secure network coding, and information theoretic security. | |
Kedar Khare is an Assistant Professor of Physics at the Indian Institute of Technology Delhi since 2011. Prior to this, he obtained his M. Sc. (5 year integrated) degree in Physics from IIT Kharagpur in 1999, and his Ph.D. (Optics) from The Institute of Optics at the University of Rochester in 2004. From 2004-06 he was a research associate at the University of Rochester, and a Lead Scientist at General Electric (GE) Global Research, USA. His research interests include Optics/Photonics, Computational Imaging, Inverse Problems, Signal Processing, and Compressive Sensing. |
For any questions, contact Uday Khankhoje (uday@ee.iitd.ac.in)
Details
Tutorial Title: Compressed Sensing and Sparse Recovery: fundamental results and recent trends
Abstract: In a wide variety of scenarios, the high ambient dimension of the underlying data imposes serious restrictions on how the data is processed. Fortunately, in many emerging applications — communications, signal processing, medical imaging, and big data, to name a few — the high dimensional data can be described using a ``sparse representation’’ that is of sufficiently low dimensions. Sparse recovery techniques refer to the general class of techniques that attempt to retrieve high-dimensional data from its low-dimensional observations under the assumption of sparsity in the data. Bolstered by the seminal works on compressed sensing by Candes et al and Donoho, sparse recovery algorithms have seen considerable recent interest from both theoretical and practical perspectives.
In this talk, we give a tutorial style introduction to compressed sensing and sparse recovery. We begin with formally describing the compressed sensing problem. Roughly speaking, compressed sensing is a collection of techniques that enable recovering sparse vectors from low-dimensional linear measurements. We note that, without the assumption of sparsity, such a recovery is NP-hard. Next, we give intuition into two key theoretical breakthroughs that makes compressed sensing tractable — L-1 minimisation (basis pursuit) and the Restricted Isometry Property. On the way, we point out the fundamental limits on the number of measurements required in compressed sensing. We also quickly touch upon other important classes of algorithms known for this problem. Subsequently, we introduce the general sparse recovery framework where the measurements may be non-linear and the underlying data may be sparse in alternate representations. Finally, we consider some examples of such problems, such as Group Testing, Phase Retrieval, and Sparse Fast Fourier Transforms and give brief overview of these problems.
Research talk Title: Fast and Efficient Algorithms for Sparse Recovery: A General Framework (Mayank Bakshi)
Abstract: Sparse Recovery refers to a broad collection of techniques that aim to exploit sparsity to dramatically reduce the "cost'' of reconstructing a low dimensional "sparse" dataset embedded in a
prohibitively high dimensional space. While sparse recovery techniques have been around for a long time, the seminal works on Compressive Sensing by Candes, Tao, and Donoho, have renewed interest in this area -- especially among information theorists. Formally, consider an unknown "k-sparse vector" 'x', i.e., a 'n'-length vector with at most 'k' non-zero coordinates. A typical Sparse Recovery problem involves performing m measurements on 'x' to obtain a vector 'y=A(x)'. The goal is to be able to minimize 'm' while being able to reconstruct 'x' from 'y' efficiently. The function 'A(x)' may be linear (e.g. compressive sensing) or non-linear (e.g. phase retrieval).
In this talk, we will discuss a new 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. We will begin the exposition through a small puzzle and use it to explain the key ideas of picking and peeling. Building upon this insight, we will next describe 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 will examine another metric for performance - the energy required by the 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 derive a novel lower bound on the decoding energy required in compressive sensing and outline a new algorithm that matches this bound upto a constant factor.
This talk is based on joint works with Sidharth Jaggi, Minghua Chen, Pulkit Grover, Sheng Cai, Tongxin Li, and Mohammad Jahangoshahi.
Research talk title: Sparsity Assisted Phase Imaging (Kedar Khare)
Abstract: Quantitative phase imaging is a problem of great importance to multiple areas of Optics/Photonics. Phase of an optical wave cannot be measured directly but has to be inferred computationally from interferometric or direct far-field Fourier intensity measurements. In this talk I will review some of our recent work that demonstrates phase imaging performance beyond textbook limits by utilizing image sparsity ideas.
