Speaker: Babak Hassibi

Title: Gaussian Comparison Lemmas and Convex Optimization

Abstract: In the past couple of decades, non-smooth convex optimization has emerged as a powerful tool for the recovery of structured signals (sparse, low rank, finite constellation, etc.) from (possibly) noisy measurements in a variety of applications in statistics, signal processing, machine learning, communications, etc. I will describe a fairly general theory for how to determine the performance (minimum number of measurements, mean-square-error, probability-of-error, etc.) of such methods for certain measurement ensembles (Gaussian, Haar, quantized Gaussian, etc.). Among other results, we shall show that the expression for the mean-square error of the LASSO algorithm is identical to that of classical least squares, provided the ambient dimension of the unknown signal is replaced by its “statistical dimension”, and that the performance of the box relaxation for recovering BPSK signals in communications comes within 3 db of the celebrated “matched filter bound”. The genesis of the theory can be traced back to an inconspicuous 1962 lemma of Slepian (on comparing Gaussian processes).