Random Euclidean embeddings in spaces of bounded volume ratio

Authors:
  • ALAlexander Litvak
    Alexander Litvak
  • APAlain Pajor
    Alain Pajor
  • MRMark Rudelson
    Mark Rudelson
  • NTNicole Tomczak-Jaegermann
    Nicole Tomczak-Jaegermann
  • RVRoman Vershynin
    Roman Vershynin

Abstract
Let (ℝ N ,∥·∥) be the space ℝ N equipped with a norm ‖·‖ whose unit ball has a bounded volume ratio with respect to the Euclidean unit ball. Let Γ be any random N×n matrix with N>n, whose entries are independent random variables satisfying some moment assumptions. We show that with high probability Γ is a good isomorphism from the n-dimensional Euclidean space (ℝ n ,|·|) onto its image in (ℝ N ,∥·∥): there exist α,β>0 such that for all x∈ℝ n , αN|x|⩽∥Γx∥⩽βN|x|. This solves a conjecture of Schechtman on random embeddings of ℓ2n into ℓ1N.