Questions tagged [metric-embeddings]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9 votes
2 answers
203 views

Hyperbolic space embeds into Wasserstein space

Fix a positive integer $n$, let $\mathbb{H}^n$ be the $n$-dimensional hyperbolic space, $r>0$, $x\in \mathbb{H}^n$ and consider the closed (compact) geodesic ball $B_{\mathbb{H}^n}(x,r)$. Are ...
user avatar
3 votes
1 answer
160 views

Explicit formula for embedding Cayley graph of free group into hyperbolic space

The problem is to embed Cayley graph of free group with $n\geq2$ generators (the same as Bethe lattice with coordination number $2n$) into any model of $\mathbb{H}^2$ (we have no model preference, the ...
user avatar
4 votes
0 answers
59 views

Finite approximations to the Kuratowski/Fréchet embedding

Let $(X,d)$ be a compact doubling metric space with doubling constant $C>0$. Let $\{\mathbb{X}_n\}_{n=0}^{\infty}$ be a sequences of finite subsets of $X$ with $$ \left\{B\left(x_k,\frac1{n}\right)...
user avatar
10 votes
2 answers
551 views

Are hyperbolic spaces actually better for embedding trees than Euclidean spaces?

There is a folklore in the empirical computer-science literature that, given a tree $(X,d)$, one can find a bi-Lipschitz embedding into a hyperbolic space $\mathbb{H}^n$ and that $n$ is "much ...
user avatar
1 vote
0 answers
64 views

Best estimate on doubling constant of a finite metric space

Let $(X,d)$ be a finite metric space. Clearly, $(X,d)$ is a doubling metric space but is there a 'best' estimate of $(X,d)$'s doubling constant? Probability based on its cardinality, diameter, and ...
user avatar
4 votes
2 answers
157 views

Rozendorn's Article

I'm researching the isometric dips of the hyperbolic plane and in particular I'm interested in reading the results of Rozendorn who proved that the hyperbolic plane is isometrically immersed in $\...
user avatar
2 votes
0 answers
81 views

Almost Lipschitz embedding of compact metric measure spaces into Euclidean spaces

Let $(X,d)$ be a compact metric space, $m$ be a metric outer-measure on $X$. Are there 'mild conditions' on $X$ ensuring the existence of a positive integer $N\geq 3$ such that there exist $x_1,\dots,...
user avatar
7 votes
1 answer
177 views

Does there exist a countable metric space which is Lipschitz universal for all countable metric spaces?

Is there a countable metric space $U$ such that any countable metric space is bi-Lipschitz equivalent to a subset of $U$? How about $c_{00}(\mathbb{Q})$ where $\mathbb{Q}$ is the rational numbers? ...
user avatar
  • 73
1 vote
0 answers
63 views

intuition about Gaussian processes over a finite space

In a paper that I am reading the authors defines $\mathbb P(n,q)$ the space of covariance tensors for $\mathbb R^q$-valued Gaussian processes on an abstract finite space $K=\{x_1,\dots,x_n\}$. In his ...
user avatar
2 votes
0 answers
62 views

Kernels with finite dimensional feature spaces

Suppose $x,y \in \mathbb{R}^n$ for some given fixed n. Consider a kernel $K(x,y) = f(\langle x, y \rangle)$, I'd like to know which functions $f$ admit a finite dimensional feature map. In other words,...
user avatar
5 votes
1 answer
280 views

When is a metric space a snowflake?

Let $(X,d)$ be a metric space. For any $0<\epsilon<1$, we call the metric space $(X,d^{\epsilon})$; where $d^{\epsilon}(x,y)\triangleq (d(x,y))^{\epsilon}$ the $\epsilon$-snowflake of $(X,d)$. ...
user avatar
6 votes
1 answer
228 views

Why $(\mathrm{Lip}([0,1]^2))^*$ is finitely representable in 1-Wasserstein space over the plane?

In "Snowflake universality of Wasserstein spaces"" by Alexandr Andoni, Assaf Naor, and Ofer Neiman, they have the following notation: For a metric space X they write $\mathcal{P}_1(X)$ ...
user avatar
4 votes
1 answer
170 views

Bi-Hölder embeddings of finite metric spaces

This is a reference request. There is a large body of work, I'm familiar with, that describes the existence of bi-Hölder embeddings of finite metric spaces into Euclidean space (such as this ...
user avatar
5 votes
0 answers
123 views

Correspondence between Riemannian metrics and Euclidean embeddings

Given a sufficiently smooth manifold M, a Riemannian metric on M induces an isometric embedding into Euclidean space by Nash's theorem, (non-canonically, non-uniquely) an embedding of M into ...
user avatar
3 votes
1 answer
122 views

Banach embedding of finite dimensional spaces

Recall that: let $0<r<s<2$, then $\ell_r$ uniformly contains a subspace isomorphic to $\ell_s^m$, $m\ge 1$ (see [JS]). I am wondering whether are any result for the case when $r>s>2$? ...
user avatar
  • 383
3 votes
0 answers
87 views

An explicit (maybe algebraic) isometric embedding of the double torus with constant curvature K = -1

The following question is related to this previous question, Canonical immersion of the double torus: Is there any known explicit (maybe algebraic) isometric embedding of a genus 2 surface endowed ...
user avatar
2 votes
0 answers
73 views

Dense embeddings into Euclidean space

The question is a follow-up on this old post. Fix a positive integer $d$ and consider $\mathbb{R}^d$ with its usual Euclidean topology. Given a metric space $(X,\delta_X)$, what conditions are ...
user avatar
10 votes
0 answers
755 views

Two questions around the $abc$-conjecture

Let $d(a,b) = 1-\frac{2 \gcd(a,b)}{a+b}$, $d_{ABC}(a,b) = 1-\frac{2\gcd(a,b)^3}{ab(a+b)}$ be two metrics on natural numbers. The abc-conjecture can be formulated using these two metrics as: For ...
user avatar
2 votes
0 answers
109 views

Is the matrix $\mu_f(X_i \cap X_j)$ positive definite?

Let $X_1,\ldots, X_n$ be finite subsets of some larger finite set $Z$. Let $f:Z \rightarrow \mathbb{R}_{>0}$ be any function, and define a (counting) measure $\mu_f(X) = \sum_{x \in X} f(x)$ for a ...
user avatar
2 votes
0 answers
107 views

Partitions of unity with arbitrary Lip-constants

Lets make things simple. Suppose we have a compact metric space $(X,d)$ and then some Lipschitz partition of unity exists, say a collection $\mathcal{F}=\{f_n\}$ subordinate to some open cover $\...
user avatar
2 votes
0 answers
111 views

Embedding a binary subspace to $l_2$ in a much lower dimension

I'm trying to find a way to embed a binary linear subspace of dimension $n$ (a linear code) to the Euclidian space while reducing the dimension significantly. The subspace (or code) contains points ...
user avatar
  • 161
5 votes
0 answers
209 views

Is this function embeddable in Euclidean space?

Let $X = \{v_1,\ldots,v_n\}$ be a set of vectors non-zero vectors $v_i \ge 0$ and such that the vectors are pairwise linear independent. Define a function on this set $X$: $$d(v,w) = 1-\frac{2 \...
user avatar
34 votes
6 answers
2k views

Trigonometry / Euclidean Geometry for natural numbers?

Let $d(a,b) = 1 - \frac{2\gcd(a,b)^3}{ab(a+b)}$ be a metric on natural numbers without $0$. The metric space $X = \{x_0,x_1,\cdots,x_n\},n>2$ is isometric embeddable in $\mathbb{R}^n$ if and only ...
user avatar
3 votes
0 answers
100 views

"Hoelder conjugate" version of the Johnson-Lindenstrauss transform

A variation of the well-known Johnson-Lindenstrauss transform (JLT) asserts that for $x_1,\ldots,x_m\in\mathbb{R}^n$ there exists a linear transformation $A:\mathbb{R}^n\to\mathbb{R}^k$ with $k=\...
user avatar
5 votes
1 answer
430 views

Fast Bourgain embedding (or similar embeddings)?

Currently I am working on applications of Bourgain Embedding (or similar embeddings of finite metric spaces to $l_2$) to automatic feature engineering for machine learning/data science ( http://www....
user avatar
0 votes
1 answer
72 views

Lower Estimate of A Lipschitz Map

Suppose that $(X,d_X)$ and $(Y,d_Y)$ are complete doubling metric spaces and let $f:X\rightarrow Y$ be a non-constant Lipschitz map. Then can does there exist a lsc function $\rho:(0,\infty)\...
user avatar
0 votes
0 answers
99 views

Green's Function for Fractional Laplacian on the Union of Two Balls

I have two disjoint open intervals $B_1, B_2 \subset \mathbb{R}$, and variables $0 < s < 1$ and $t \in B_1 \cup B_2$. I want to solve: $$r_{B_1 \cup B_2}(\Delta^{s} f) = \delta_t$$ for $f$. ...
user avatar
5 votes
2 answers
769 views

Isometric embedding of a genus g surface

Can a genus $g$ surface with constant negative curvature and $g>1$ be isometrically embedded in $\mathbb{R}^4?$
user avatar
3 votes
1 answer
183 views

Suppose that a metric space allows David–Semmes regular map to some Euclidean space. Does it allow bi-Lipschitz embedding into some Euclidean space?

I want to ask about the progress on Question 8 from "Thirty-three yes or no questions about mappings, measures, and metrics" by Juha Heinonen and Stephen Semmes. Is it still open? If yes, ...
user avatar
2 votes
0 answers
106 views

Inclusion of convex polytopes and embedding from $\ell_2$ to $\ell_\infty$

I would like to dig deeper into the problem posted Probability that a convex shape contains the unit ball: If you pick n points uniformly at random from the surface of a d dimensional sphere of ...
user avatar
7 votes
0 answers
170 views

Do manifolds with non-negative Ricci curvature allow bi-Lipschitz embeddings into Euclidean spaces?

QUESTION: Let $n$ be a natural number. Is it true that there exist $N(n), D(n) > 0$ such that any complete $n$-dimensional Riemannian manifold of nonnegative Ricci curvature can be embedded into $N$...
user avatar
6 votes
1 answer
151 views

Embedding Turing machine [closed]

I have some questions about Turing machines. Is there an embedding method where you embed Turing machines, finite automata into continuous space or graphs? Or are there geometrical approaches to ...
user avatar
  • 63
2 votes
2 answers
215 views

Johnson-Lindenstrauss Lemma on $S^{d-1}$

Consider the Johnson-Lindenstrauss lemma in the case where we can assume the $n$ input points $x_i$ in $\mathbb{R}^d$ are actually located on the sphere $$S^{d-1}(r):=\{u=(u_1,\ldots,u_{d}): u_1^2+\...
user avatar
  • 8,653
1 vote
0 answers
113 views

Expectation of a combinatorial extremal random variable?

Consider the finite set $\chi(D)$ of all sets of integer points in $\Bbb Z^n$ around origin which have distance at most $D$ from each other and pick a set $\mathcal P(D)$ from set of sets $\chi(D)$ ...
user avatar
  • 12.8k
2 votes
0 answers
55 views

Totally distance non-preserving transformations

JL lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) guarantees if you have a set of $K$ points in $\Bbb R^N$ a random transformation guarantees that the set can be projected ...
user avatar
  • 12.8k
4 votes
2 answers
276 views

Finitely isometrically persistent metric spaces

The goal of this question is to develop further the discussion initiated in Under which conditions is it possible to find points with same distances under bi-Lipschitz map. The mentioned question was ...
user avatar
12 votes
1 answer
520 views

Is $\ell_p$ $(1<p<\infty)$ finitely isometrically distortable?

Let $Y$ be a Banach space isomorphic to $\ell_p$, $1<p<\infty$. Is it true that any finite subset of $\ell_p$ is isometric to some finite subset of $Y$? It seems to me that it is an interesting ...
user avatar
31 votes
0 answers
850 views

Isometric embeddings of finite subsets of $\ell_2$ into infinite-dimensional Banach spaces

Question: Does there exist a finite subset $F$ of $\ell_2$ and an infinite-dimensional Banach space $X$ such that $F$ does not admit an isometric embedding into $X$? There are some results of the ...
user avatar
4 votes
1 answer
526 views

Embedding graphs into hyperbolic spaces

Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?) I don't ...
user avatar
  • 505
14 votes
3 answers
673 views

Does every CAT(0) space embed in a measurable integral of $\mathbb{R}$-trees?

Question 1. Does every CAT(0) space embed isometrically inside an integral of $\mathbb{R}$-trees? Here an integral of $\mathbb{R}$ trees means the set of functions from a measure space $\mathcal{F}$ ...
user avatar
20 votes
1 answer
817 views

Canonical immersion of the double torus

It is easy to check that the immersion $\mathbb{T}^2=\mathbb{S}^1\times \mathbb{S}^1\longrightarrow\mathbb{R}^4$, $(\alpha,\beta)\longmapsto(\cos\alpha,\sin\alpha,\cos\beta,\sin\beta)$ induces the ...
user avatar
  • 2,041
8 votes
1 answer
345 views

Embedding Euclidean buildings into products of trees

A Euclidean building has a natural metric space structure. (A definition of Euclidean building can be found on Wikipedia, or, more expansively, in Section 4 of Kleiner-Leeb.) Question: Is it true ...
user avatar
17 votes
0 answers
450 views

Large almost equilateral sets in finite-dimensional Banach spaces

Question: Does there exist a function $C:~(0,1)\to (0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space $X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point set $\{x_i\...
user avatar
2 votes
0 answers
233 views

Finitely generated groups non-embeddable into $L_1(0,1)$

I am interested in finitely generated groups which, endowed with their word metrics, do not admit bilipschitz embeddings into $L_1(0,1)$. I know two classes of such groups: (1) Heisenberg group $\...
user avatar
11 votes
1 answer
360 views

Embeddings of finitely generated groups into uniformly convex Banach spaces

de Cornulier, Tessera, and Valette (Geom. Funct. Anal. 17 (2007), 770-792) conjectured that a finitely generated group $G$ with its word metric admits a bilipschitz embedding into a Hilbert space if ...
user avatar
6 votes
1 answer
268 views

Reference request: embedding the hyperbolic triangulation in $\mathbb{R}^3$

Let $T_d$ be the infinite valence $d$ triangulation of the hyperbolic plane, where each triangle is equilateral and $d \ge 7$. Question: Is there an isometric embedding from $T_d \to \mathbb{R}^3$? ...
user avatar
5 votes
3 answers
462 views

How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights. Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight? ...
user avatar
  • 2,899
1 vote
1 answer
290 views

Probabilistic Johnson-Lindenstrauss Lemma for arbitrary points

Consider the following standard formulation of the Johnson-Lindenstrauss lemma: Lemma (JL). For any $0<\epsilon < 1$ and any integer $n$, let $k$ be a positive integer such that $k\geq C\...
user avatar
  • 434
15 votes
3 answers
642 views

Embedding expanders in CAT(0) spaces

It is well-known that expanders are hard to embed into Hilbert (or $\ell^p$) spaces - any embedding of an expander with $n$ vertices has distortion $\Omega(\log n)$. Can anyone provide a reference (...
user avatar
8 votes
0 answers
172 views

Can two random graphs be metrically embedded into one another?

Let $X, Y$ be two random graphs on $n$ vertices (say, in $G(n, p)$ model for some $p$). Can anything (expectation, value with high probabiity, ...) be said about $D(X, Y)$, where $D$ is the minimal ...
user avatar