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. I will demonstrate instances of such extreme compression by considering three prototype inverse problems: super-resolution imaging, compressive covariance sensing, and tensor CP decomposition. 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.