Probability Seminar: Yaniv Plan

  • Date: 03/29/2017
  • Time: 15:00
Yaniv Plan, UBC Math

University of British Columbia


A simple tool for bounding the deviation of random matrices on geometric sets


Let A be an isotropic, sub-gaussian m by n matrix. We prove that the process Z_x = ||A x||_2 – m^(.5) ||x||_2 has sub-gaussian increments. Using this, we show that for any bounded set T in R^n, the deviation of ∥Ax∥2 around its mean is uniformly bounded by the Gaussian complexity of T. In other words, we give a simple sufficient condition for a random sub-Gaussian matrix to be well conditioned when restricted to a subset of R^n. We also prove a local version of this theorem, which allows for unbounded sets. These theorems have various applications, such as a general theory of compressed sensing. We discuss some applications and point to open (probabilistic) questions that remain.

Other Information: 

Location: ESB 2012