RLE Events

Pushing the Limits of Sparse Recovery: The Interplay of Structured Sampling and Correlation Awareness

Mon, Mar 11, 2013, 3pm / 34-401A


Refreshments 2:45 pm
Hosts: Al Oppenheim

Piya Pal, Caltech

Modern Sensing and Signal Processing Systems face a fundamental challenge in the extraction of meaningful information from large, complex and often distributed datasets. Such “Big Data” routinely arises in sensor networks, genomics, physiology, imaging, particle physics, social networks, and so forth. Fortunately however, the amount of information buried in the data in most scenarios is substantially lower compared to the number of raw samples acquired. This key observation has led to the design of sensing systems that can directly capture the information using far fewer samples typically acquired via random projections. In many natural scenarios however, the physics of the problem itself imposes “structure” on the ensuing acquisition scheme. Also often, one can make informed realistic assumptions about the “statistical properties” of the data, in the form of priors. Recent approaches to sparse sensing and reconstruction have only begun to investigate the advantages that such structure and prior knowledge can offer over more traditional approaches to sparse recovery. One common example is the rank of the matrix of data vectors, and has been exploited in the past to some extent.

In this talk, I will describe how “sparse structured sampling” strategies and the use of “priors” in the form of correlation of the data can dramatically push the limits of extraction of low dimensional information buried in high dimensional data (e.g. the spatio temporal signal received by an array of sensors), much beyond what is guaranteed by existing methods. In particular, I will develop novel sparse samplers (temporal and spatial) in one and multiple dimensions that can directly exploit the prior information contained in the correlation and/or higher order moments of the data to greatly increase the number of identifiable parameters. I will also develop new fast and robust algorithms for sparse recovery that work on a low dimensional data and guarantees recovery of sparsity levels that can be orders of magnitude larger than that achieved by existing approaches. This new paradigm of sparse support recovery that explicitly establishes the fundamental interplay between sampling, statistical priors and the underlying sparsity, leads to exciting future research directions in a variety of application areas, and also gives rise to new questions that can lead to stand-alone theoretical results in their own right.