Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
复制标题
降维：超越 Johnson-Lindenstrauss 界限
DOI：
10.1137/1.9781611973082.68
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
L. Schulman
中科院分区：
文献类型：
--
作者：
Y. Bartal;Benjamin Recht;L. Schulman
降低度量数据已成为众多应用的有用技术。 - 已知这种界限几乎是紧身的。
在许多应用程序中，所有距离都应该保留的需求太强大了，我们表明，在嵌入目标的自然放松下，目标尺寸可以降低结果可以看作是局部尺寸的，在各种经验情况下，小距离是有意义的和可靠的。来源编码，图像处理，计算生物学和其他应用，是诸如ISOMAP和本地线性嵌入等广泛启发式方法的动机。
追求惠特尼（Whitney）开始的工作，纳什（Nash）表明，维度D的每个C1歧管都可以嵌入R2D+2中，以使每个点的局部结构都保留在等速度上。欧几里得空间。
我们表明，欧几里得空间的任何有限子集都可以嵌入O（ε-2 log k） - 数量时，同时使用（1 +ε） - 限制了每个点的“核心社区”中的距离。围绕该点的度量球，其半径是基数K的半径k-Neighborhood的大部分。 （嵌入维度的某种依赖性对增长率）。
作为我们方法的应用，我们获得了（Assouad风格的）尺寸减小欧几里得空间的有限子集，其中指标升至某些分数（所得的指标都称为雪花）。嵌入具有1 +ε扭曲的尺寸（ε -3 DIM（x））中，其中dim（x）是倍增尺寸，这是集合的内在维度的度量。 Gottlieb和Krauthgamer [20]几乎紧密地束缚。
新的降低结果可用于诸如聚类和距离标签之类的应用。
Dimension reduction of metric data has become a useful technique with numerous applications. The celebrated Johnson-Lindenstrauss lemma states that any n-point subset of Euclidean space can be embedded in O(ε−2 log n)-dimension with (1 + ε)-distortion. This bound is known to be nearly tight.
In many applications the demand that all distances should be nearly preserved is too strong. In this paper we show that indeed under natural relaxations of the goal of the embedding, an improved dimension reduction is possible where the target dimension is independent of n. Our main result can be viewed as a local dimension reduction. There are a variety of empirical situations in which small distances are meaningful and reliable, but larger ones are not. Such situations arise in source coding, image processing, computational biology, and other applications, and are the motivation for widely-used heuristics such as Isomap and Locally Linear Embedding.
Pursuing a line of work begun by Whitney, Nash showed that every C1 manifold of dimension d can be embedded in R2d+2 in such a manner that the local structure at each point is preserved isometrically. Our work is an analog of Nash's for discrete subsets of Euclidean space. For perfect preservation of infinitesimal neighborhoods we substitute near-isometric embedding of neighborhoods of bounded cardinality.
We show that any finite subset of Euclidean space can be embedded in O(ε−2 log k)-dimension while preserving with (1 + ε)-distortion the distances within a "core neighborhood" of each point. (The core neighborhood is a metric ball around the point, whose radius is a substantial fraction of the radius of the ball of cardinality k, the k-neighborhood.) When the metric space satisfies a weak growth rate property, the guarantee applies to the entire k-neighborhood (with some dependency of the embedding dimension on the growth rate). We also show how to obtain a global embedding that also keeps distant points well-separated (at the cost of dependency on the doubling dimension of the space).
As an application of our methods we obtain an (Assouad-style) dimension reduction for finite subsets of Euclidean space where the metric is raised to some fractional power (the resulting metrics are known as snowflakes). We show that any such metric X can be embedded in dimension Õ(ε−3 dim(X)) with 1 + ε distortion, where dim(X) is the doubling dimension, a measure of the intrinsic dimension of the set. This result improves recent work by Gottlieb and Krauthgamer [20] to a nearly tight bound.
The new dimension reduction results are useful for applications such as clustering and distance labeling.