Approximating \(L_p\) unit balls via random sampling (Q2039571)

A measure on \(\mathbb{R}^d\) is isotropic if it is centered and has the identity as its covariance. A random vector is isotropic if it is distributed according to an isotropic measure. In this paper, the author considers an isotropic random vector \(X\) in \(\mathbb {R}^d\) that satisfies that for every \(v \in \mathbb{S}^{d-1}\), \(\|\langle X, v\rangle \|_{L_q} \leq L \| \langle X, v \rangle \|_{L_p}\) for some \(q \geq 2p\). The author shows 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 \(\mathbb {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(-c N \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.