Gaussian comparisons meet convexity: Precise analysis of structured signal recovery

Printer-friendly version
Speaker: 
Christos Thrampoulidis
Institution: 
MIT
Time: 
Tue, 11/14/2017 - 11:00am - 11:50am
Host: 
Roman Vershynin
Location: 
RH 306

Gaussian comparison inequalities are classical tools that often lead to simple proofs of powerful results in random matrix theory, convex geometry, etc. Perhaps the most celebrated of these tools is Slepian’s Inequality, which dates back to 1962. The Gaussian Min-max Theorem (GMT) is a non-trivial generalization of Slepian’s result, derived by Gordon in 1988. Here, we prove a tight version of the GMT in the presence of convexity. Based on that, we describe a novel and general framework to precisely evaluate the performance of non-smooth convex optimization methods under certain measurement ensembles (Gaussian, Haar). We discuss applications of the theory to box-relaxation decoders in massive MIMO, 1-bit compressed sensing, and phase-retrieval.