Talk on Correlation Awareness and Fundamental Limits in Sparse Support Recovery

Title:  Correlation Awareness and Fundamental Limits in Sparse Support Recovery

Date: Friday, Jan. 3rd, 2013

Time: 4 pm

Tea/coffee: 3.45pm

Venue: Golden Jubilee Hall, ECE Department, IISc Bangalore

Speaker: Piya Pal, PhD candidate, DSP Lab, Caltech, USA

Abstract :

Representation, sampling and reconstruction of sparse signals has been an exciting and active area of research in signal processing for over a decade. Sparse support recovery techniques have gained popularity in the signal processing community for their capability to recover the sparsest solution to a linear underdetermined system Ax = y, where the measurement matrix A ∈ C^M×N, M < N, is fat. An immediate extension of such a model is that of Multiple Measurement Vectors (MMV) where a number (say, L) of unknown vectors share the same sparse support. Such signal models arise in a number of practical situations, such as data obtained from an array of sensors, MRI imaging, channel estimation etc. A wide variety of algorithms exist in literature for recovering the common support in the MMV model. However, for a given N, these methods so far can typically recover supports of size O(M). In this talk, we will show how prior knowledge on the correlation structure of the measurement vectors can drastically improve this bound. Direct exploitation of the correlation present in data has been largely ignored by most existing approaches for support recovery. To bridge this gap, we will develop the theory for “Correlation Aware Support Recovery” and demonstrate that under certain conditions on the statistics of the unknown vectors and the measurement matrix, it is fundamentally possible to increase the recoverable sparsity level to as large as O(M2), in the limit as L → ∞. In the particular context of multiple antenna array processing, our proposed framework has an inherent connection to the interesting notion of “difference co-arrays”. We will show how this naturally justifies the use of sparse antenna array geometries such as the nested and coprime arrays which were previously proposed by us in the context of Direction-of-Arrival (DOA) estimation. We also developed a new algorithm for sparse support recovery which acts upon data of much smaller dimension, derived from the larger MMV model, thereby performing an implicit dimension reduction and leading to faster recovery. For finite L, when we only have estimates of the correlation, we reformulate the support recovery problem as a LASSO and provide conditions for unique recovery of the support. For particular measurement models, such as the Gaussian source, we show that it is possible to recover the sparse support with overwhelming probability (i.e., the probability increases as 1 − β−L, β > 1). We will conclude the talk by pointing out a wide number of open questions and interesting problems that our proposed framework opens up for promising future research.

Bio :

Piya Pal is a graduate student in the department of Electrical Engineering at Caltech, working in the DSP group headed by Prof. P. P. Vaidyanathan. She graduated from Indian Institute of Technology, Kharagpur in 2007, with a B. Tech in Electronics and Electrical Communication Engineering. In September 2007, she joined the PhD program in the Electrical Engineering department at Caltech, funded by an Atwood Fellowship. She is currently pursuing her doctoral research under the guidance of Prof. P. P. Vaidyanathan. She spent the summer of 2012 (June-October) at Microsoft Research, Redmond, as an intern working with Dr. Henrique Malvar.

Leave a Reply