ترجمه فارسی مقاله در پسوندهای بیرونی دو-لپشیتز از تعبیه خطی جانسون-لینندراس از زیر مجموعه های $mathbb{R}^N$

چکیده

The celebrated Johnson-Lindenstrauss lemma states that for all $\varepsilon \in (0,1)$ and finite sets $X \subseteq \mathbb{R}^N$ with $n>1$ elements, there exists a matrix $Φ\in \mathbb{R}^{m \times N}$ with $m=\mathcal{O}(\varepsilon^{-2}\log n)$ such that \[ (1 – \varepsilon) \|x-y\|_2 \leq \|Φx-Φy\|_2 \leq (1+\varepsilon)\| x- y\|_2 \quad \forall\, x, y \in X.\] Herein we consider terminal embedding results which have recently been introduced in the computer science literature as stronger extensions of the Johnson-Lindenstrauss lemma for finite sets. After a short survey of this relatively recent line of work, we extend the theory of terminal embeddings to hold for arbitrary (e.g., infinite) subsets $X \subseteq \mathbb{R}^N$, and then specialize our generalized results to the case where $X$ is a low-dimensional compact submanifold of $\mathbb{R}^N$. In particular, we prove the following generalization of the Johnson-Lindenstrauss lemma: For all $\varepsilon \in (0,1)$ and $X\subseteq\mathbb{R}^N$, there exists a terminal embedding $f: \mathbb{R}^N \longrightarrow \mathbb{R}^{m}$ such that $$(1 – \varepsilon) \| x – y \|_2 \leq \left\| f(x) – f(y) \right\|_2 \leq (1 + \varepsilon) \| x – y \|_2 \quad \forall \, x \in X ~{\rm and}~ \forall \, y \in \mathbb{R}^N.$$ Crucially, we show that the dimension $m$ of the range of $f$ above is optimal up to multiplicative constants, satisfying $m=\mathcal{O}(\varepsilon^{-2} ω^2(S_X))$, where $ω(S_X)$ is the Gaussian width of the set of unit secants of $X$, $S_X=\overline{\{(x-y)/\|x-y\|_2 \colon x \neq y \in X\}}$. Furthermore, our proofs are constructive and yield algorithms for computing a general class of terminal embeddings $f$, an instance of which is demonstrated herein to allow for more accurate compressive nearest neighbor classification than standard linear Johnson-Lindenstrauss embeddings do in practice.

چکیده به فارسی (ترجمه ماشینی)

Lemma مشهور جانسون-لینندراسس اظهار داشت که برای همه $ \ varepsilon \ in (0،1) $ و مجموعه های محدود $ x \ subseteq \ mathbb {r}^n $ با $ n> 1 $ $ ، یک ماتریکس $ φ وجود دارد\ in \ mathbb {r}^{m \ times n} $ با $ m = \ mathcal {o} (\ varepsilon^{-2} \ log n) $ به گونه ای که \ [(1-\ varepsilon) \ | x-y\ | _2 \ leq \ | φx-φy \ | _2 \ leq (1+ \ varepsilon) \ |X- y \ | _2 \ Quad \ forall \ ، x ، y \ in x. \] در اینجا ما نتایج تعبیه ترمینال را در نظر می گیریم که اخیراً در ادبیات علوم کامپیوتر به عنوان پسوندهای قوی تر لیمما جانسون-لینستراوس برای مجموعه های محدود معرفی شده است.پس از یک بررسی کوتاه از این خط کار نسبتاً اخیر ، ما تئوری تعبیه های ترمینال را برای نگه داشتن زیر مجموعه های دلخواه (به عنوان مثال ، نامحدود) $ x \ subseteq \ mathbb {r}^n $ گسترش می دهیم ، و سپس نتایج عمومی خود را به نتایج تخصص می دهیم.موردی که $ x $ یک زیر مجموعه جمع و جور کم بعدی از $ \ Mathbb {r}^n $ است.به طور خاص ، ما تعمیم زیر از Lemma Johnson-LindenStrauss را اثبات می کنیم: برای همه $ \ varepsilon \ in (0،1) $ و $ x \ subseteq \ mathbb {r}^n $ ، یک ترمینال وجود دارد که $ f:\ Mathbb {r}^n \ longrightarrow \ mathbb {r}^{m} $ به گونه ای که $ $ (1 – \ varepsilon) \ |x – y \ | _2 \ leq \ سمت چپ \ |f (x) – f (y) \ راست \ | _2 \ leq (1 + \ varepsilon) \ |x – y \ | _2 \ quad \ forall \ ، x \ in x ~ {\ rm و} ~ \ forall \ ، y \ in \ mathbb {r}^n. $ $ به طور مهم نشان می دهیم که ابعاد $ m $ $ $از دامنه $ f $ در بالا بهینه است تا ثابت های چند برابر ، رضایت $ m = \ mathcal {o} (\ varepsilon^{-2} ω^2 (s_x)) $ ، جایی که $ ω (s_x) $ استعرض گاوسی از مجموعه واحد Secants از $ x $ ، $ s_x = \ overline {\ {(x-y)/\ | x-y \ | _2 \ colon x \ neq y \ in x \}} $.علاوه بر این ، اثبات ما الگوریتم های سازنده و عملکردی برای محاسبه یک کلاس کلی از تعبیه های ترمینال $ f $ است که نمونه ای از آن در اینجا نشان داده شده است تا امکان طبقه بندی دقیق نزدیکترین همسایه را نسبت به تعبیه های خطی خطی جانسون-لینندراس در عمل انجام دهد.