Probability Seminar: Yaniv Plan

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.