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.