Low Dimensional Euclidean Volume Preserving Embeddings

Abstract

Let $\mathcal{P}$ be an $n$-point subset of Euclidean space and $d\ge 3$ be an integer. In this paper we study the following question: What is the smallest (normalized) relative change of the volume of subsets of $\mathcal{P}$ when it is projected into $\RR^d$. We prove that there exists a linear mapping $f:\mathcal{P} \mapsto \RR^d$ that relatively preserves the volume of all subsets of size up to $\lfloor d/2\rfloor$ within at most a factor of $O(n^{2/d}\sqrt{\log n\log \log n})$.

8 pages