Strange shadows of ℓ p \ell_{p} -balls

Zakhar Kabluchko, Mathias Sonnleitner · 2024

Read Strange shadows of ℓ p \ell_{p} -balls by Zakhar Kabluchko, Mathias Sonnleitner (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17475.txt.

Introduction

Zakhar Kabluchko and Mathias Sonnleitner wrote a 2024 math paper on the shadows cast by high dimensional balls of a special kind. They study what happens when such a ball is projected onto a random flat subspace, or cut by one, as the dimension grows without bound. For one range of the shape value, they prove a large deviations law for the projections. For the other range, they prove the same for the cuts.

The rate function in their law lives only on a certain class of shapes and their duals, and it is written through a maximum entropy recipe. A striking upshot is that the scaled shadows almost surely settle toward a round ball of a fixed radius. They also give the chance that a shadow stays inside a smaller ball. As a side result, the work yields a new inequality for the gamma function.

Catalog record

CREATORZakhar Kabluchko, Mathias Sonnleitner
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17475

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strange shadows of ℓ p \ell_{p} -balls Zakhar Kabluchko, Mathias Sonnleitner Abstract . We prove a large deviations principle for orthogonal projections of the unit ball 𝔹 p n \mathbb{B}_{p}^{n} of ℓ p n \ell_{p}^{n} onto a random k k -dimensional linear subspace of ℝ n \mathbb{R}^{n} as n → ∞ n\to\infty in the case 2 < p ≤ ∞ 2<p\leq\infty and for the intersection of 𝔹 p n \mathbb{B}_{p}^{n} with a random k k -dimensional subspace in the case 1 ≤ p < 2 1\leq p<2 . The corresponding rate function is finite only on L q L_{q} -zonoids and their duals, respectively, and given in terms of the maximum entropy over suitable measures generating the L q L_{q} -zonoid, where 1 p + 1 q = 1 \frac{1}{p}+\frac{1}{q}=1 . In particular, we obtain that the renormalized projections/sections almost surely tend to a k k -dimensional Euclidean ball of certain radius. Moreover, we identify the asymptotic probability that the random orthogonal projection remains within a ball of smaller radius. As a byproduct we obtain an interesting inequality for the Gamma function. 2020 Mathematics Subject Classification 52A23 (52A21, 52A22, 60F10) 1. Introduction and main results Let \mathbb{B}_{p}^{n}:=\{x\in\mathbb{R}^{n}\colon\sum_{i=1}^{n}|x_{i}|^{p}\leq 1\} be the unit ball of \ell_{p}^{n} , 1\leq p<\infty , and \mathbb{B}_{\infty}^{n}=[-1,1]^{n} . Via orthogonal projection onto a k -dimensional subspace, k\leq n , the \ell_{p} -ball \mathbb{B}_{p}^{n} casts a k -dimensional shadow. This terminology is also used in Ball’s Shadows of Convex Bodies [ 7 ] , where the author bounds the volume of a convex body by an average of volumes of some of its shadows. By a theorem of Dvoretzky-Milman [ 5 , Cor. 7.24] , as the dimension n grows, most such shadows tend to be very close to the Euclidean ball \mathbb{B}_{2}^{k} , after suitable renormalization. Thus, we might say that \mathbb{B}_{2}^{k} is the typical shadow of \mathbb{B}_{p}^{n} . We are interested in shadows which are unlikely, strange so to speak, occurring with exponentially small (in n ) probability. This can be investigated within the framework of large deviations theory. A classical result, which goes back to Maxwell, Borel and Poincaré, states that the coordinates of a random vector X_{n} which is uniformly distributed in n^{1/2}\mathbb{B}_{2}^{n} become approximately Gaussian as n\to\infty . Due to [ 46 , 47 ] this also holds true for n^{1/p}\mathbb{B}_{p}^{n} but in this case the limit density is proportional to e^{-|x|^{p}/p} for p<\infty and the uniform density on [-1,1] for p=\infty . In contrast, Klartag’s central limit theorem for convex bodies [ 24 ] shows that for any fixed k\in\mathbb{N} most k -dimensional projections of X_{n} become approximately Gaussian. Thus, in some sense, if p\neq 2 , coordinate projections of X_{n} are atypical. From a large deviations perspective this atypicality has been investigated in [ 15 ] and [ 16 ] , which motivated large deviation theorems for norms of X_{n} in [ 2 , 19 ] and triggered a body of work, partly summarized in the surveys [ 43 , 45 ] . For large deviations of random projections of the cube \mathbb{B}_{\infty}^{n} , two more perspectives in terms of random measures have been considered in [ 17 , 20 ] . On a related note, in [ 41 ] a central limit theorem is proven for the volume of random projections of \mathbb{B}_{\infty}^{n} . This has recently been extended to p>1 in [ 44 ] where also large deviation principles are proven. In the following, we provide yet another large deviation perspective of random projections of \ell_{p} -balls, which is in terms of the shape of the random projections of \mathbb{B}_{p}^{n} itself, rather than a distribution defined on it. This allows for a detailed description of the set of strange shadows of \mathbb{B}_{p}^{n} . More precisely, we are interested in large deviations of the sequence of random k -dimensional sets Z_{n,p}:=n^{1/p-1/2}\Pi_{n,k}^{\top}\mathbb{B}_{p}^{n},\qquad n\geq k, where k\in\mathbb{N} is fixed and \Pi_{n,k} is a random n\times k -matrix whose columns form an orthonormal k -frame uniformly distributed on the Stiefel manifold \mathbb{V}_{n,k} , the set of all such frames in \mathbb{R}^{n} , with respect to Haar measure. That is, the first column u_{1} of \Pi_{n,k} is uniformly distributed on the unit sphere \mathbb{S}^{n-1} , the second column u_{2} is uniformly distributed on u_{1}^{\perp}\cap\mathbb{S}^{n-1} , and so on. Then E_{n,k}=\Pi_{n,k}(\mathbb{R}^{k}) is a random k -dimensional subspace of \mathbb{R}^{n} uniformly distributed on the Grassmannian \mathbb{G}_{n,k} , the set of all such subspaces, with respect to Haar measure. Moreover, the composition of the isometry \Pi_{n,k}^{\top}\colon E_{n,k}\to\mathbb{R}^{k} and the orthogonal projection P_{E_{n,k}}\colon\mathbb{R}^{n}\to E_{n,k} onto E_{n,k} satisfies \Pi_{n,k}^{\top}P_{E_{n,k}}=\Pi_{n,k}^{\top} . Thus, the action of \Pi_{n,k}^{\top} can indeed be understood as taking orthogonal projection onto a random subspace and then mapping isometrically to \mathbb{R}^{k} . The object Z_{n,p} is a random element of the space \mathcal{K}^{k} of convex bodies in \mathbb{R}^{k} , that is, nonempty compact convex sets, which is equipped with the Hausdorff metric \delta_{H}(K,L)=\max\Big\{\sup_{x\in K}\inf_{y\in L}\|x-y\|,\sup_{x\in L}\inf_{y\in K}\|x-y\|\Big\},\quad K,L\in\mathcal{K}^{k}. As a random linear image of \mathbb{B}_{p}^{n} , the set Z_{n,p} is a random compact set taking values in \mathcal{K}^{k} in the sense of [ 33 ] and [ 37 ] . Note that for our purposes a convex body is a nonempty compact convex set which may have empty interior, see [ 48 ] . The following class of convex bodies will be essential for the study of the random convex body Z_{n,p} . Let 1<p\leq\infty and let 1\leq q<\infty be the Hölder-conjugate index with \frac{1}{p}+\frac{1}{q}=1 , where \frac{1}{\infty}=0 . An L_{q} -zonoid (also sometimes called L_{q} -centroid body) is a convex body K\in\mathcal{K}^{k} with support function h(K,u):=\sup_{x\in K}\langle x,u\rangle=\Big(\int_{\mathbb{R}^{k}}|\langle x,u\rangle|^{q}\mathrm{d}\mu(x)\Big)^{1/q},\qquad u\in\mathbb{R}^{k}, (1) for some Borel probability measure \mu\in\mathcal{P}_{q}(\mathbb{R}^{k}) on \mathbb{R}^{k} , where \mathcal{P}_{q}(\mathbb{R}^{k})=\Big\{\mu\in\mathcal{P}(\mathbb{R}^{k})\colon\int_{\mathbb{R}^{k}}\|x\|_{2}^{q}\mathrm{d}\mu(x)<\infty\Big\} and \mathcal{P}(\mathbb{R}^{k}) is the set of all Borel probability measures on \mathbb{R}^{k} . In this case, we write K=Z_{q}(\mu) for the L_{q} -zonoid generated by \mu and we denote by \mathrm{Zon}_{k,q}=\{Z_{q}(\mu)\colon\mu\in\mathcal{P}_{q}(\mathbb{R}^{k})\} the set of all L_{q} -zonoids in \mathbb{R}^{k} . Then the random set Z_{n,p} is a random L_{q} -zonoid, i.e. takes values in \mathrm{Zon}_{k,q} , see Proposition 20 below. We will prove a large deviation principle (LDP) for k -dimensional random projections and sections of \mathbb{B}_{p}^{n} in the complete separable metric space (\mathcal{K}^{k},\delta_{H}) . Here, a sequence of random convex bodies (K_{n})_{n\in\mathbb{N}} satisfies an LDP with lower semicontinuous rate function I\colon\mathcal{K}^{k}\to[0,\infty] if for all Borel sets A\subset\mathcal{K}^{k} it holds that \displaystyle-\inf_{K\in\Int A}I(K) \displaystyle\leq\liminf_{n\to\infty}n^{-1}\log\mathbb{P}[K_{n}\in A] \displaystyle\leq\limsup_{n\to\infty}n^{-1}\log\mathbb{P}[K_{n}\in A]\leq-\inf_{K\in\cl A}I(K), where \Int A (respectively, \cl A ) denotes the interior (respectively, closure) of A and \inf\emptyset=\infty . A rate function is good if it additionally has compact sublevel sets. We refer to [ 12 ] for a background on the theory of large deviations. The rate functions in our main results involve the (differential) entropy which, for \mu\in\mathcal{P}(\mathbb{R}^{k}) , is given by {\rm Ent}(\mu)=-\int_{\mathbb{R}^{k}}\log(f(x))f(x)\mathrm{d}x, whenever \mu admits a Lebesgue density f and {\rm Ent}(\mu)=-\infty otherwise. Our main result for random projections of \mathbb{B}_{p}^{n} reads as follows. Theorem 1 . Let 2<p\leq\infty and let 1\leq q<2 with \frac{1}{p}+\frac{1}{q}=1 . Fix k\in\mathbb{N} . The sequence Z_{n,p}=n^{1/p-1/2}\Pi_{n,k}^{\top}\mathbb{B}_{p}^{n} , n\geq k , satisfies an LDP in \mathcal{K}^{k} with good rate function I_{p}(K)=\inf\{\mathrm{Ent}(\gamma^{\otimes k})-\mathrm{Ent}(\mu)\colon\mu\in\mathcal{P}_{q}(\mathbb{R}^{k})\text{ with }Z_{q}(\mu)=K\text{ and }Z_{2}(\mu)\subset\mathbb{B}_{2}^{k}\}, where K\in\mathcal{K}^{k} and \gamma^{\otimes k} denotes the k -dimensional standard Gaussian distribution. Large

Read the complete text