Page 1

Displaying 1 – 1 of 1

Showing per page

Generalizing the Johnson-Lindenstrauss lemma to k-dimensional affine subspaces

Alon Dmitriyuk, Yehoram Gordon (2009)

Studia Mathematica

Let ε > 0 and 1 ≤ k ≤ n and let W l l = 1 p be affine subspaces of ℝⁿ, each of dimension at most k. Let m = O ( ε - 2 ( k + l o g p ) ) if ε < 1, and m = O(k + log p/log(1 + ε)) if ε ≥ 1. We prove that there is a linear map H : m such that for all 1 ≤ l ≤ p and x , y W l we have ||x-y||₂ ≤ ||H(x)-H(y)||₂ ≤ (1+ε)||x-y||₂, i.e. the distance distortion is at most 1 + ε. The estimate on m is tight in terms of k and p whenever ε < 1, and is tight on ε,k,p whenever ε ≥ 1. We extend these results to embeddings into general normed spaces Y.

Currently displaying 1 – 1 of 1

Page 1