Computable Performance Analysis of Sparse Recovery with Applications

NYU Community Event

Speaker: Professor Arye Nehorai

Host Faculty: Professor Shiv Panwar


The last decade has witnessed burgeoning developments in the reconstruction of signals based on exploiting their low-dimensional structures, particularly their sparsity, block-sparsity, and low-rankness. The reconstruction performance of these signals is heavily dependent on the structure of the operating matrix used in sensing. The quality of these matrices in the context of signal recovery is usually quantified by the restricted isometry constant and its variants. However, the restricted isometry constant and its variants are extremely difficult to compute.

We present a framework for analytically computing the performance of the recovery of signals with sparsity structures. We define a family of incoherence measures to quantify the goodness of arbitrary sensing matrices. Our primary contribution is the design of efficient algorithms, based on linear programming and second order cone programming, to compute these incoherence measures. As a by-product, we implement efficient algorithms to verify sufficient conditions for exact signal recovery in the noise-free case. The utility of the proposed incoherence measures lies in their relationship to the performance of reconstruction methods. We derive closed-form expressions of bounds on the recovery errors of convex relaxation algorithms in terms of these measures. The second part of the talk applies the developed theory and algorithms to the optimal design of an OFDM radar system with multi-path components.

About the Speaker

Arye Nehorai is the Eugene and Martha Lohman Professor and Chair of the Preston M. Green Department of Electrical and Systems Engineering at Washington University in St. Louis (WUSTL). Under his leadership as department chair, the undergraduate enrollment has tripled in the last four years. Earlier he was a faculty member at Yale University and the University of Illinois at Chicago. In 2001 he was named University Scholar of the University of Illinois. He received the B.Sc. and M.Sc. degrees from the Technion, Israel, and the Ph.D. from Stanford University, California. Dr. Nehorai has served as Editor-in-Chief of the IEEE Transactions on Signal Processing during the years 2000 to 2002. From 2003 to 2005 he was Vice President (Publications) of the IEEE Signal Processing Society (SPS), Chair of the Publications Board, and member of the Executive Committee of this Society. He was the Founding Editor of the special columns on Leadership Reflections in the IEEE Signal Processing Magazine from 2003 to 2006.Dr. Nehorai received the 2006 IEEE SPS Technical Achievement Award and the 2009 IEEE SPS Meritorious Service Award. He was elected Distinguished Lecturer of the IEEE SPS for the term 2004 to 2005. He co-authored three journal papers that received best paper awards from the IEEE Signal Processing Society. He was also co-author of five best paper awards in student competitions at international conferences. He is a Fellow of the Institute of Electrical and Electronics Engineers (IEEE), the Royal Statistical Society, and the American Association for the Advancement of Science (AAAS).