Recovering structured signals in high-dimensions: Precise performance analysis

Christos Thrampoulidis
Graduate Student, Caltech
Given on: Mar. 11th, 2016


The typical scenario that arises in modern large-scale inference problems is one where the ambient dimension of the unknown signal is very large (e.g. high-resolution images, Massive-MIMO, etc.), yet is such that its desired properties lie in some low-dimensional structure (sparsity, binary, low-rankness, etc.). In the past couple of decades, non-smooth convex optimization has emerged as a powerful tool to reveal those structures. While the algorithms (LASSO, LAD, etc.) are fairly well established, rigorous and unifying frameworks for their exact analysis are only recently emerging.

In this talk we present a novel and general framework to evaluate the asymptotic performance (minimum number of measurements, mean-squared error, probability of error, etc.) of such recovery methods under Gaussian measurement ensembles and under different measurement models (e.g. noisy linear, single-index model). This allows to compare performance between different estimators, and thus, to answer optimality and robustness questions (e.g. optimal loss function and regularizer parameter, robustness to outliers, etc.). For illustration, we will evaluate the bit-error rate of the box relaxation for recovering BPSK signals in communications and compare it to the matched-filter bound. We will further discuss implications of the theory in the design of optimal measurement quantizers.

The analysis is based on Gaussian process methods; in particular, on a classical comparison inequality proved by Gordon in 1988. We will prove a stronger and tight version of Gordon's original result in the presence of additional convexity assumptions. We call this the Convex Gaussian Min-max Theorem (CGMT).


Christos Thrampoulidis is currently a PhD candidate at Caltech, where he is advised by Prof. Babak Hassibi. He received his diploma in Electrical and Computer Engineering from the University of Patras, Greece in 2011 and his Masters degree in Electrical Engineering from Caltech in 2012. His research interests are in high-dimensional signal-processing, compressed sensing, convex analysis and applied probability. He is a recipient of the 2014 Qualcomm Innovation Fellowship and of the Andreas Mentzelopoulos Scholarship from the University of Patras.