Dimension Reduction Input:n points,...,R Output::n pointsy1,y2,,yn∈Rkst.1≤i,j≤n: (1-e)x;-xl≤Ily:-yl≤(1+e)l:-xl ·Usually we want k<d. ·How small can k be? ·For what distance‖l·l? The embedding should be efficiently constructible.• Usually we want . • How small can be? • For what distance ? • The embedding should be efficiently constructible. k ≪ d k ∥ ⋅ ∥ Dimension Reduction Input: points Output: points s.t. n x1, x2, …, xn ∈ ℝd n y1, y2, …, yn ∈ ℝk ∀1 ≤ i, j ≤ n : (1 − ϵ)∥xi − xj ∥ ≤ ∥yi − yj ∥ ≤ (1 + ϵ)∥xi − xj ∥