人工智能培训

搜索

机器学习论文:通过外BI-LIPSCHITZ扩展的非线性降维(Nonlinear Dimension Reduction via Outer Bi-Lipsch

[复制链接]
redfrog 发表于 5 天前 | 显示全部楼层 |阅读模式
redfrog 5 天前 42 0 显示全部楼层
机器学习论文:通过外BI-LIPSCHITZ扩展的非线性降维(Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions)我们介绍和研究欧几里德空间之间的地图的外部双Lipschitz扩展的概念。这个概念是Lipschitz映射的Lipschitz扩展概念的自然类比。我们展示了每张地图$ f $ thereexists一个外部双Lipschitz扩展$ f'$,其失真大于$ f $,最多是一个常数因子。这个结果可以看作是外部双Lipschitzextensions的经典Kirszbraun定理的开头部分。我们还研究了近等距地图的外部双Lipschitz扩展,并显示了它们的上下界。然后,我们将我们的结果应用于优先级和终端维数减少问题。*我们证明了Johnson-Lindenstrauss引理的优先变体:给出一组点$ X \ subset \ mathbb {R} ^ d $,大小$ N $和$ X $的置换(“priorityranking”),$ $ mathbb {R} ^ {O(\ logN)} $中存在$ f $ $ $ $ $ $ $(\ log \ log N) $等级$ j $只有$ O(\ log ^ {3 + \ varepsilon} j)$非零坐标 - 更具体地说,除了第一个$ O(\ log ^ {3+ \ varepsilon} j)$坐标等于$ 0 $; $ f $限制在第一个$ j $点(根据排名)的失真最多是$ O(\ log \ log j)$。结果使得Elkin,Filtser和Neiman回答关于优先级维度减少的问题得到了进展。*我们证明,在$ \ mathbb {R} ^ d $中给出$ $ $ $ $ $ $ $ $ $,这里有一个终端维度将$ \ mathbb {R} ^ d $嵌入到$ \ mathbb {R} ^ {d'} $中,其中$ d'= O \ left(\ frac {\ log N} {\ varepsilon ^ 4} \ right )$,它保持距离$ \ | xy \ | $之间的距离$ x \在X $和$ y \ in \ mathbb {R} ^ {d} $之间,乘以$ 1 \ pm \ varepsilon $的乘法因子。这改进了Elkin,Filtser和Neiman的最新结果。我们获得的尺寸减小是非线性的,并且这种非线性是必要的。
We introduce and study the notion of an outer bi-Lipschitz extension of a mapbetween Euclidean spaces.The notion is a natural analogue of the notion of aLipschitz extension of a Lipschitz map.We show that for every map $f$ thereexists an outer bi-Lipschitz extension $f'$ whose distortion is greater thanthat of $f$ by at most a constant factor.This result can be seen as acounterpart of the classic Kirszbraun theorem for outer bi-Lipschitzextensions.We also study outer bi-Lipschitz extensions of near-isometric mapsand show upper and lower bounds for them.Then, we present applications of ourresults to prioritized and terminal dimension reduction problems.* We prove a prioritized variant of the Johnson-Lindenstrauss lemma: given aset of points $X\subset \mathbb{R}^d$ of size $N$ anda permutation ("priorityranking") of $X$, there exists an embedding $f$ of $X$ into $\mathbb{R}^{O(\logN)}$ with distortion $O(\log \log N)$ such that the point of rank $j$ has only$O(\log^{3 + \varepsilon} j)$ non-zero coordinates - more specifically, all butthe first $O(\log^{3+\varepsilon}j)$ coordinates are equal to $0$;thedistortion of $f$ restricted to the first $j$ points (according to the ranking)is at most $O(\log\log j)$.The result makes a progress towards answering anopen question by Elkin, Filtser, and Neiman about prioritized dimensionreductions.* We prove that given a set $X$ of $N$ points in $\mathbb{R}^d$, there existsa terminal dimensionreduction embedding of $\mathbb{R}^d$ into$\mathbb{R}^{d'}$, where $d' = O\left(\frac{\log N}{\varepsilon^4}\right)$,which preserves distances $\|xy\|$ between points $x\in X$ and $y \in\mathbb{R}^{d}$, up to a multiplicative factor of $1 \pm \varepsilon$.Thisimproves a recent result by Elkin, Filtser, and Neiman.The dimension reductions that we obtain are nonlinear, and this nonlinearityis necessary.机器学习论文:通过外BI-LIPSCHITZ扩展的非线性降维(Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions) E8422Hqdy97Dh04Q.jpg
URL地址:https://arxiv.org/abs/1811.03591     ----pdf下载地址:https://arxiv.org/pdf/1811.03591    ----机器学习论文:通过外BI-LIPSCHITZ扩展的非线性降维(Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则 返回列表 发新帖

redfrog当前离线
新手上路

查看:42 | 回复:0

快速回复 返回顶部 返回列表