Stable recovery and the coordinate small-ball behaviour of random vectors Academic Article uri icon

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 $(||)_{i=1}^m$, where $T:mathbb{R}^n o 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 $||$ are at least of the order $|T|_{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.

author list (cited authors)

  • Mendelson, S., & Paouris, G.

complete list of authors

  • Mendelson, Shahar||Paouris, Grigoris

publication date

  • April 2019