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 = {\left\lVert Ax \right\rVert}_2 - \sqrt{m} {\left\lVert x \right\rVert}_2$$ has sub-gaussian increments. Using this, we show that for any bounded set $$T$$ in $$\mathbb{R}^n$$, the deviation of $${\left\lVert Ax \right\rVert}_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 $$\mathbb{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.