Loading...
Please wait, while we are loading the content...
Similar Documents
Ultra-Low-Dimensional Embeddings for Doubling Metrics ∗
| Content Provider | CiteSeerX |
|---|---|
| Author | Hubert, T.-H. Anupam, Chan Talwar, Gupta Kunal |
| Abstract | We consider the problem of embedding a finite metric space (V, d) with small doubling dimension into low-dimensional Euclidean space, with provable bounds on the distortion. Roughly, a metric has doubling dimension dimD = k if and only if it has 2k points at roughly the same distance from each other, but no larger; a more formal definition can be found in [1]. A metric (V, d) is called doubling if the doubling dimension is a constant, independent of size n = V of the metric space. Note that for a low-dimensional manifold M, the geodesic distance metric dM has doubling dimension depending only on the manifold dimension and not on the ambient dimension. Thus our results also give embeddings for a finite set of points lying on a low-dimensional manifold into a low-dimensional Euclidean space. Dimension reduction in Euclidean spaces have been studied extensively. The celebrated and surprising “flattening ” lemma of Johnson and Lindenstrauss [2] states that the dimension of any Euclidean metric on n log n ɛ2 points can be reduced to O ( ) with (1 + ɛ) distortion using a random linear map. Moreover, this result is existentially tight: a simple packing argument shows that any distortion-D embedding of a uniform metric on n points into Euclidean space requires at least Ω(logD n) dimensions—intuitively, there aren’t enough distinct directions in a low dimensional Euclidean space to accommodate a large number of equidistant |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Dimension Reduction Provable Bound Geodesic Distance Metric Dm Aren Enough Distinct Direction Low Dimensional Euclidean Space Ambient Dimension Low-dimensional Manifold Random Linear Map Manifold Dimension Ultra-low-dimensional Embeddings Dimension Dimd Distortion-d Embedding Large Number Finite Set Metric Space Formal Definition Simple Packing Argument Low-dimensional Euclidean Space Finite Metric Space Euclidean Space |
| Content Type | Text |
