{
  "id": "1904.08532",
  "version": "v1",
  "published": "2019-04-17T23:17:48.000Z",
  "updated": "2019-04-17T23:17:48.000Z",
  "title": "Stable recovery and the coordinate small-ball behaviour of random vectors",
  "authors": [
    "Shahar Mendelson",
    "Grigoris Paouris"
  ],
  "categories": [
    "math.PR",
    "math.ST",
    "stat.TH"
  ],
  "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 $\\|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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-04-17T23:17:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random vector",
      "coordinate small-ball behaviour",
      "stable recovery",
      "sub-sampled convolutions satisfy stable",
      "convolutions satisfy stable point separation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}