Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality

Let XX be a n×pn×p real matrix with coherence μ(X)=maxj≠j′|XjtXj′|. We present a simplified and improved study of the quasi-isometry property for most submatrices of XX obtained by uniform column sampling. Our results depend on μ(X)μ(X), the operator norm ‖X‖‖X‖ and the dimensions with explicit constants, which improve the previously known values by a large factor. The analysis relies on a tail-decoupling argument, of independent interest, and a recent version of the Non-Commutative Chernoff inequality (NCCI).