This content will become publicly available on May 6, 2025
 Award ID(s):
 2154918
 NSFPAR ID:
 10533579
 Publisher / Repository:
 European Mathematical Society
 Date Published:
 Journal Name:
 Revista Matemática Iberoamericana
 ISSN:
 02132230
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

We introduce and study the notion of *an outer biLipschitz 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 biLipschitz 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 biLipschitz extensions. We also study outer biLipschitz extensions of nearisometric 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) nonzero 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

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 NPhard problems. In fact, it is UGChard to approximate k to withina factor smaller than 2 even when the metric sans outliers is isometrically embeddable into ℓ2. We considerbicriteria 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 is
arbitrarily small in 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 AzzamSchul 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 biLipschitz mappings. 
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 "kwise 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 kmetric 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_{i1}, y, x_{i+1}, …, x_k). (The definition holds for any fixed k ≥ 2, and a 2metric space is just a (standard) metric space.) In this work, we introduce strong kmetric spaces, kmetric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary kmetrics, which generalize 𝓁_p metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain kmetrics, which generalize shortest path metrics (and capture all strong kmetrics). 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) kmetrics, and show that natural quantities, like simplex volume, are strong kmetrics.more » « less

In this article we start a systematic study of the biLipschitz geometry of lamplighter graphs. We prove that lamplighter graphs over trees biLipschitzly embed into Hamming cubes with distortion at most 6. It follows that lamplighter graphs over countable trees biLipschitzly embed into l1. We study the metric behaviour of the operation of taking the lamplighter graph over the vertexcoalescence of two graphs. Based on this analysis, we provide metric characterisations of superreflexivity in terms of lamplighter graphs over star graphs or rose graphs. Finally, we show that the presence of a clique in a graph implies the presence of a Hamming cube in the lamplighter graph over it. An application is a characterisation, in terms of a sequence of graphs with uniformly bounded degree, of the notion of trivial Bourgain–Milman–Wolfson type for arbitrary metric spaces, similar to Ostrovskii’s characterisation previously obtained in Ostrovskii (C. R. Acad. Bulgare Sci. 64(6), 775–784 (2011)).more » « less