Approximating $L_p$ unit balls via random sampling

Abstract

Let $X$ be an isotropic random vector in $R^d$ that satisfies that for every $v\in S^{d-1}$, $\Vert <X,v>{\Vert }_{L_q}\le L\Vert <X,v>{\Vert }_{L_p}$ for some $q\ge 2p$. We show that for $0<\epsilon <1$, a set of $N=c(p,q,\epsilon )d$ random points, selected independently according to $X$, can be used to construct a $1\pm \epsilon$ approximation of the $L_p$ unit ball endowed on $R^d$ by $X$. Moreover, $c(p,q,\epsilon )\le c^p{\epsilon }^{-2}\log (2/\epsilon )$; when $q=2p$ the approximation is achieved with probability at least $1-2\exp (-cN{\epsilon }^2/{\log }^2(2/\epsilon ))$ and if $q$ is much larger than $p$---say, $q=4p$, the approximation is achieved with probability at least $1-2\exp (-cN{\epsilon }^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,\epsilon )d^{p/2}\log d$ random points are enough, and that the approximation is valid with constant probability.

References in corpus (1)

• Concentration inequalities and asymptotic results for ratio type empirical processes