OctoInformBeta

Subpolynomial dimension reduction in Lp

Fix 1<p<∞1<p<\infty, an integer n≥2n\ge2, and a distortion bound D≥1D\ge1. The universal coordinate dimension dp(n,D)d_p(n,D) is the least integer dd such that every nn-point subset XX of a real LpL_p space admits a map f:X→ℓpdf:X\to\ell_p^d and a scale s>0s>0 satisfying s∥x−x′∥p≤∥f(x)−f(x′)∥p≤Ds∥x−x′∥ps\|x-x'\|_p\le\|f(x)-f(x')\|_p\le Ds\|x-x'\|_p for all x,x′∈Xx,x'\in X. The dimension-reduction question concerns the growth of dp(n,D)d_p(n,D) with nn when pp and DD are fixed and the maps need not be linear.

Johnson and Lindenstrauss proved d2(n,D)=OD(log⁡n)d_2(n,D)=O_D(\log n) for every fixed D>1D>1. For 1<p<21<p<2 and fixed D>1D>1, Schechtman obtained dp(n,D)=Op,D(n)d_p(n,D)=O_{p,D}(n). For p>2p>2 and fixed D>1D>1, Naor and Ren proved that arbitrarily large cardinalities require coordinate dimension at least a constant multiple of (log⁡n/(log⁡log⁡n)2)p/2(\log n/(\log\log n)^2)^{p/2}.

For p≠2p\ne2, define γ(p)=2−p\gamma(p)=2-p when 1<p<21<p<2 and γ(p)=1−2/p\gamma(p)=1-2/p when p>2p>2. The preprint proves that for every fixed D>1D>1 there is a finite constant Cp,DC_{p,D} such that dp(n,D)≤exp⁡(Cp,D(log⁡n)γ(p))d_p(n,D)\le\exp\!\bigl(C_{p,D}(\log n)^{\gamma(p)}\bigr) for all n≥2n\ge2. At exact distortion, it proves dp(n,1)=Θp(n2)d_p(n,1)=\Theta_p(n^2).

Lean has checked every result of the Lean library LpDimension, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its Lean declaration. Where the preprint gives a different statement, the preprint’s statement is given beside the Lean library’s. The preprint is a guide only to the order and names of the results.

The Lean library: LpDimension

LpDimension is a Lean library: 19 items, in nine groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): the universal coordinate dimension Coordinate dimension for finite LpL_p configurations.
  2. Theorem 1.1 Dimension bounds for finite LpL_p sets.
§2. Finite coordinates and normalized increments 2 items
  1. Lemma 2.1 Finite LpL_p metrics admit exact coordinates.
  2. §2 (setting): edges and normalized gradients Normalizing coordinate increments on vertex pairs.
§3. From weighted moments to an embedding 1 item
  1. Lemma 3.1 From weighted moments to sampled embeddings.
§4. A projection with controlled row sums 3 items
  1. §4 (setting): electrical and weighted projections Projections onto spaces of edge gradients.
  2. Lemma 4.1 Absolute projection bounds on complete graphs.
  3. Lemma 4.2 Retractions with controlled row sums.
§5. Homogeneous increments and signed Poisson sampling 2 items
  1. §5 (setting): the power-law intensity and signed sums Power intensities and signed jump sums.
  2. Lemma 5.1 Poisson mixing and symmetrization give explicit transforms.
§6. The range 1 < p < 2 2 items
  1. §6 (proof of Theorem 1.1): common stable marginals and their tails Stable laws yield common gradient marginals.
  2. §6 (proof of Theorem 1.1): clipping and the weighted-moment contract Clipped stable gradients control weighted moments.
§7. The range 2 < p < ∞ 3 items
  1. §7.1-§7.2 (setting and proof of Theorem 1.1): the ramp and its error Dyadic ramps yield bounded gradient jumps.
  2. Lemma 7.1 Bounds for moments of symmetric sums.
  3. §7.3-§7.4 (proof of Theorem 1.1): summing the jumps and discarding a bad vector Ramp sums give subpolynomial dimension bounds.
§8. Dimension bounds and exact embeddings 3 items
  1. §8.1 (proof of Theorem 1.1): assembling the upper bound Sampling size and exact coordinate bounds.
  2. §8.2 (proof of Theorem 1.1): packing lower bound Packing forces a dimension lower bound.
  3. §8.3 (setting and proof of Theorem 1.1): disjointness and the grid obstruction Exact dimension is quadratic for p>1p>1, p≠2p\ne2.
Appendix A. Electrical-flow localization 1 item
  1. Appendix A (proof of Lemma 4.1): heat representation and entropy Heat and entropy control electrical localization.

No item matches.