Optimal Embeddings of Constant-Dimensional ℓₚ-Subspaces

Abstract: For d ≥ 2, p ≥ 1 and ε > 0, let Nₚ(d, ε) be the smallest integer N such that every d-dimensional subspace of ℓₚᵐ admits a linear embedding into ℓₚᴺ with distortion at most 1 + ε. For fixed d ≥ 2 and p ≥ 1, the bound

Nₚ(d, ε) ≤ C(d, p) · ε^(−2(d − 1)/(d + 2p))

is established, where C(d, p) is a constant depending only on d and p. When p is not an even integer, this matches the known lower bound up to constant factors. For odd integers p, previous upper bounds with this exponent incurred additional logarithmic factors, except in the logarithm-free case p = 1; for non-integral p, no upper bound with this exponent was previously known. For even integers p, isometric embeddings of dimension independent of ε are known.

When p is not an even integer, the proof approximates |t|ᵖ by a polynomial with a remainder of small total variation. The polynomial part contributes no error, while the error from the remainder is controlled by an integrated equatorial-band discrepancy estimate.

Short bio: Yi Li is an associate professor in the School of Physical and Mathematical Sciences at Nanyang Technological University, with a joint appointment in the College of Computing and Data Science. His research lies mainly in algorithms for massive data sets, with a recent focus on randomized numerical linear algebra and clustering coresets.