{
  "id": "2008.08380",
  "version": "v1",
  "published": "2020-08-19T11:20:28.000Z",
  "updated": "2020-08-19T11:20:28.000Z",
  "title": "Approximating $L_p$ unit balls via random sampling",
  "authors": [
    "Shahar Mendelson"
  ],
  "categories": [
    "math.PR",
    "math.FA"
  ],
  "abstract": "Let $X$ be an isotropic random vector in $R^d$ that satisfies that for every $v \\in S^{d-1}$, $\\|<X,v>\\|_{L_q} \\leq L \\|<X,v>\\|_{L_p}$ for some $q \\geq 2p$. We show that for $0<\\varepsilon<1$, a set of $N = c(p,q,\\varepsilon) d$ random points, selected independently according to $X$, can be used to construct a $1 \\pm \\varepsilon$ approximation of the $L_p$ unit ball endowed on $R^d$ by $X$. Moreover, $c(p,q,\\varepsilon) \\leq c^p \\varepsilon^{-2}\\log(2/\\varepsilon)$; when $q=2p$ the approximation is achieved with probability at least $1-2\\exp(-cN \\varepsilon^2/\\log^2(2/\\varepsilon))$ and if $q$ is much larger than $p$---say, $q=4p$, the approximation is achieved with probability at least $1-2\\exp(-cN \\varepsilon^2)$. In particular, when $X$ is a log-concave random vector, this estimate improves the previous state-of-the-art---that $N=c^\\prime(p,\\varepsilon) d^{p/2}\\log d$ random points are enough, and that the approximation is valid with constant probability.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-08-19T11:20:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "unit ball",
      "random sampling",
      "approximation",
      "random points",
      "isotropic random vector"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}