Stable recovery and the coordinate small-ball behaviour of random vectors

Abstract

Recovery procedures in various application in Data Science are based on \emph{stable point separation}. In its simplest form, stable point separation implies that if $f$ is "far away" from $0$, and one is given a random sample $(f(Z_i){)}_{i=1}^m$ where a proportional number of the sample points may be corrupted by noise, that information is still enough to exhibit that $f$ is far from $0$. Stable point separation is well understood in the context of iid sampling, and to explore it for general sampling methods we introduce a new notion---the \emph{coordinate small-ball} of a random vector $X$. Roughly put, this feature captures the number of "relatively large coordinates" of $(|<TX,u_i>|{)}_{i=1}^m$, where $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is an arbitrary linear operator and $(u_i{)}_{i=1}^m$ is any fixed orthonormal basis of ${\mathbb{R}}^m$. We show that under the bare-minimum assumptions on $X$, and with high probability, many of the values $|<TX,u_i>|$ are at least of the order $\Vert T{\Vert }_{S_2}/\sqrt{m}$. As a result, the "coordinate structure" of $TX$ exhibits the typical Euclidean norm of $TX$ and does so in a stable way. One outcome of our analysis is that random sub-sampled convolutions satisfy stable point separation under minimal assumptions on the generating random vector---a fact that was known previously only in a highly restrictive setup, namely, for random vectors with iid subgaussian coordinates.