Structured Sampling for Covariance Compression

Wednesday May 10, 2017 4:00 PM

Structured Sampling for Covariance Compression

Speaker: Piya Pal , Department of Electrical and Computer Engineering , University of California, San Diego
Location: Moore B280

ABSTRACT: A number of problems in statistical signal processing model the data as a Wide-Sense Stationary (WSS) time series, whose power spectrum (or equivalently, the covariance matrix) acts as a sufficient statistic for inferring parameters of interest. The covariance matrix of such data exhibit Toeplitz structure, which can be leveraged to design highly efficient compressive samplers to reduce the dimension of the WSS data, without requiring it to have a sparse representation. Unlike existing results in Compressed Sensing, the goal here is to recover the high dimensional covariance matrix (or infer parameters of interest from it), instead of reconstructing the data itself.

Inspired by our past work on nested sensor arrays, I will describe a new sampling technique, known as the "Generalized Nested Sampler" (GNS), to acquire compressive measurements in such a way that it becomes possible to perfectly reconstruct the original high dimensional covariance matrix from these compressed sketches. I will focus on low-rank Toeplitz covariance matrices and develop an efficient GNS-based sampler which allows the recovery of a rank-r Toeplitz covariance matrix from a compressed sketch of size O(√r) x O(√r), where the size of the sketch has no dependence on the ambient large dimension N. Our reconstruction technique will use a regularizer-free framework, combined with the ability to extrapolate additional "unobserved" entries of the NxN covariance matrix. The algorithm has significantly lower computational complexity (that does not scale with N) compared to recent nuclear-norm based compressive covariance estimators, and is provably robust against bounded errors. Finally, I will consider the special case of rank-1 and sparse covariance matrices that arise in the important problem of "phase retrieval" in optical imaging. The role of 2nd order difference sets in complex phase retrieval will be demonstrated, inspiring the design of a new class of non-uniform Fourier sampler that can provably recover a complex signal (up to a global phase ambiguity) from its amplitude measurements with near-minimal number of samples. An interesting connection with the so‑called 4N-4 conjecture will also be established, which hypothesizes 4N-4 to be the minimum number of measurements necessary to ensure injectivity in N dimensions for complex phase retrieval.

Joint work with Heng Qiao, graduate student, University of California, San Diego.

BIO: Dr. Piya Pal is an Assistant Professor of Electrical and Computer Engineering at the University of California, San Diego. Prior to her appointment at UCSD, she was an Assistant Professor of Electrical and Computer Engineering at the University of Maryland, College Park where she was also affiliated with the Institute for Systems Research. She received her Bachelors in Technology degree in Electronics and Electrical Communication Engineering from Indian Institute of Technology, Kharagpur, India in 2007, and her Ph.D. in Electrical Engineering from Caltech in 2013, where her Ph.D. thesis won the Charles and Ellen Wilts Prize for Outstanding Doctoral Thesis in Electrical Engineering. Her research interests span compressive and structured sampling, high dimensional statistical signal processing with applications in radar and sensor array processing high resolution imaging, tensor methods, and statistical learning. She is an elected member of the IEEE SAM Technical Committee and a recipient of the 2016 NSF CAREER Award.

HOST: Oguzhan Teke

Series: Electrical Engineering Systems Seminar Series
Contact: Katie Pichotta pichotta@caltech.edu
Department of Electrical Engineering