 Almost-isometric Gaussian embedding from l2 into l1

ID: almost-isometric-gaussian-embedding-from-l2-into-l1

(T x)_{i} = \frac{1}{β k} \sum_{j = 1}^{n} Z_{ij} x_{j}

satisfies

P ((1 - δ) ∥ x ∥_{2} \leq ∥ T x ∥_{1} \leq (1 + δ) ∥ x ∥_{2}) \geq 1 - 2 e^{- c δ^{2} k} .

A net argument shows that

k \geq C_{ε} n

permits a linear embedding of distortion below

1 + ε

 New to topics? Read the docs here!