An official website of the United States government
We introduce and study the notion of *an outer bi-Lipschitz extension* of a map between Euclidean spaces. The notion is a natural analogue of the notion of *a Lipschitz extension* of a Lipschitz map. We show that for every map f there exists an outer bi-Lipschitz extension f′ whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a *prioritized* variant of the Johnson–Lindenstrauss lemma: given a set of points X⊂ ℝd of size N and a permutation (”priority ranking”) of X, there exists an embedding f of X into ℝO(logN) with distortion O(loglogN) such that the point of rank j has only O(log3 + ε j) non-zero coordinates – more specifically, all but the first O(log3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O(loglogj). The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. We prove that given a set X of N points in ℜd, there exists a *terminal* dimension reduction embedding of ℝd into ℝd′, where d′ = O(logN/ε4), which preserves distances ||x−y|| between points x∈ X and y ∈ ℝd, up to a multiplicative factor of 1 ± ε. This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.
more »
« less
Bi-Lipschitz arcs in metric spaces with controlled geometry
In this paper, we generalize a bi-Lipschitz extension result of David and Semmes from Euclidean spaces to complete metric measure spaces with controlled geometry (Ahlfors regularity and supporting a Poincaré inequality). In particular, we find sharp conditions on metric measure spaces X so that any bi-Lipschitz embedding of a subset of the real line into X extends to a bi-Lipschitz embedding of the whole line. Along the way, we prove that if the complement of an open subset Y of X has small Assouad dimension, then it is a uniform domain. Finally, we prove a quantitative approximation of continua in X by bi-Lipschitz curves.
more »
« less
- Award ID(s):
- 2154918
- PAR ID:
- 10533579
- Publisher / Repository:
- European Mathematical Society
- Date Published:
- Journal Name:
- Revista Matemática Iberoamericana
- ISSN:
- 0213-2230
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the design of embeddings into Euclidean space with outliers. Given a metric space (X, d) and aninteger k, the goal is to embed all but k points in X (called the “outliers”) into ℓ2 with the smallest possibledistortion c. Finding the optimal distortion c for a given outlier set size k, or alternately the smallest k fora given target distortion c are both NP-hard problems. In fact, it is UGC-hard to approximate k to withina factor smaller than 2 even when the metric sans outliers is isometrically embeddable into ℓ2. We considerbi-criteria approximations. Our main result is a polynomial time algorithm that approximates the outlier setsize to within an O(log2 k) factor and the distortion to within a constant factor.The main technical component in our result is an approach for constructing Lipschitz extensions ofembeddings into Banach spaces (such as ℓp spaces). We consider a stronger version of Lipschitz extensionthat we call a nested composition of embeddings: given a low distortion embedding of a subset S of the metricspace X, our goal is to extend this embedding to all of X such that the distortion over S is preserved, whereasthe distortion over the remaining pairs of points in X is bounded by a function of the size of X \ S. Priorwork on Lipschitz extension considers settings where the size of X is potentially much larger than that of Sand the expansion bounds depend on |S|. In our setting, the set S is nearly all of X and the remaining setX \ S, a.k.a. the outliers, is small. We achieve an expansion bound that is polylogarithmic in |X \ S|.more » « less
-
We study the quantitative properties of Lipschitz mappings from Euclidean spaces into metric spaces. We prove that it is always possible to decompose the domain of such a mapping into pieces on which the mapping “behaves like a projection mapping” along with a “garbage set” that isarbitrarily smallin an appropriate sense. Moreover, our control is quantitative, i.e., independent of both the particular mapping and the metric space it maps into. This improves a theorem of Azzam-Schul from the paper “Hard Sard”, and answers a question left open in that paper. The proof uses ideas of quantitative differentiation, as well as a detailed study of how to supplement Lipschitz mappings by additional coordinates to form bi-Lipschitz mappings.more » « less
-
Mulzer, Wolfgang; Phillips, Jeff M (Ed.)Metric spaces (X, d) are ubiquitous objects in mathematics and computer science that allow for capturing pairwise distance relationships d(x, y) between points x, y ∈ X. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "k-wise distance relationships" d(x_1, …, x_k) among points x_1, …, x_k ∈ X for k > 2. To that end, Gähler (Math. Nachr., 1963) (and perhaps others even earlier) defined k-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality d(x₁, x₂) ≤ d(x₁, y) + d(y, x₂) to the "simplex inequality" d(x_1, …, x_k) ≤ ∑_{i=1}^k d(x_1, …, x_{i-1}, y, x_{i+1}, …, x_k). (The definition holds for any fixed k ≥ 2, and a 2-metric space is just a (standard) metric space.) In this work, we introduce strong k-metric spaces, k-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary k-metrics, which generalize 𝓁_p metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain k-metrics, which generalize shortest path metrics (and capture all strong k-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fréchet embedding (isometric embedding into 𝓁_∞) and isometric embedding of all tree metrics into 𝓁₁. We also study relationships between families of (strong) k-metrics, and show that natural quantities, like simplex volume, are strong k-metrics.more » « less
-
Abstract Stochastic embeddings of finite metric spaces into graph-theoretic trees have proven to be a vital tool for constructing approximation algorithms in theoretical computer science. In the present work, we build out some of the basic theory of stochastic embeddings in the infinite setting with an aim toward applications to Lipschitz free space theory. We prove that proper metric spaces stochastically embedding into$$\mathbb {R}$$-trees have Lipschitz free spaces isomorphic to$$L^1$$-spaces. We then undergo a systematic study of stochastic embeddability of Gromov hyperbolic metric spaces into$$\mathbb {R}$$-trees by way of stochastic embeddability of their boundaries into ultrametric spaces. The following are obtained as our main results: (1) every snowflake of a compact, finite Nagata-dimensional metric space stochastically embeds into an ultrametric space and has Lipschitz free space isomorphic to$$\ell ^1$$, (2) the Lipschitz free space over hyperbolicn-space is isomorphic to the Lipschitz free space over Euclideann-space and (3) every infinite, finitely generated hyperbolic group stochastically embeds into an$$\mathbb {R}$$-tree, has Lipschitz free space isomorphic to$$\ell ^1$$, and admits a proper, uniformly Lipschitz affine action on$$\ell ^1$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.4171/RMI/1484
