Extreme Compression in Convex and Non-convex Inverse Problems: Role of Geometry, Priors and Measurement Design

Abstract

Inferring parameters of interest from high dimensional data is a central problem in signal
processing and machine learning. Fortunately, many modern datasets possess low dimensional
structure (such as sparsity, low-rank) which can be judiciously exploited to reduce the cost of
sensing and computation. Starting from seminal works in compressed sensing and linear
underdetermined estimation, there has been tremendous progress towards understanding how
such low dimensional structure can be optimally exploited in a variety of convex and non-convex
inverse problems with provable theoretical guarantees. Celebrated results (which, in many cases,
rely on randomized measurements to establish probabilistic guarantees) indicate that in many of
these problems, it is indeed possible to obtain reliable inference with a sample complexity that is
proportional to the underlying (low) dimension.
Many inverse problems of practical interest (such as those arising in source localization, super-
resolution imaging, channel estimation) possess additional geometry that is imparted by the
physical measurement model, physical laws governing wave propagation, as well as statistical
priors (such as correlation) on the unknown quantities of interest. In this talk, I will demonstrate
how to tailor the design of “smart” sensing systems and develop corresponding reconstruction
algorithms that can achieve significantly higher compression (henceforth termed extreme
compression) than existing guarantees on sample complexity. Instead of randomized
measurements, I will focus on the design of deterministic Fourier-structured measurement
matrices (that naturally arise in many practical imaging problems) and exploit combinatorial
designs (governed by the idea of “difference sets” in one and multiple dimensions) to attain such
extreme compression. I will derive non-asymptotic probabilistic guarantees in this regime by
developing new algorithms that carefully exploit the geometry of these smart samplers.
Throughout my talk, I will draw examples from applications in radar and sonar signal
processing, super-resolution optical imaging, neural signal processing and hybrid channel
sensing.

Biography

Piya Pal is an Assistant Professor of Electrical and Computer Engineering, and a founding faculty member and faculty advisor of the Halıcıoğlu Data Science Institute at the University of California, San Diego. Her research interests include signal representation and sampling for high-dimensional inference, super-resolution imaging, convex and non-convex optimization, and statistical learning. Her research has been recognized by the 2019 Presidential Early Career Award for Scientists and Engineers (PECASE), 2019 Office of Naval Research Young Investigator Program (ONR YIP) Award, 2016 NSF CAREER Award, 2018 Qualcomm Fellow Mentor Advisor Award and the 2014 Charles and Ellen Wilts Prize for Outstanding Doctoral Thesis in Electrical Engineering at Caltech. She is also a two-time recipient of the Best Graduate Teaching Award in Electrical and Computer Engineering at UC San Diego (in 2017 and 2018). She and her student have received several best paper awards at conferences, including the Best Student Paper Award at the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2017. She is an elected member of the IEEE SAM and SPTM Technical Committees. She received her B.S. degree in Electronics and Electrical Communication Engineering from the Indian Institute of Technology, Kharagpur in 2007 and her Ph.D.  in Electrical Engineering from the California Institute of Technology (Caltech), Pasadena in 2013.