Questions tagged [metric-embeddings]
The metric-embeddings tag has no usage guidance.
43
questions
5
votes
1answer
108 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? ...
0
votes
0answers
36 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 ...
2
votes
0answers
50 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,...
5
votes
1answer
190 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)$.
...
3
votes
1answer
97 views
Why $(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)$ to ...
4
votes
1answer
148 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 ...
5
votes
0answers
88 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 ...
3
votes
1answer
107 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$?
...
3
votes
0answers
79 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 ...
2
votes
0answers
70 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 ...
10
votes
0answers
746 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 ...
2
votes
0answers
102 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 ...
2
votes
0answers
70 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 $\...
2
votes
0answers
107 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 ...
5
votes
0answers
207 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 \...
34
votes
6answers
1k 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 ...
3
votes
0answers
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=\...
4
votes
1answer
388 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....
0
votes
1answer
65 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)\...
0
votes
0answers
75 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$. ...
5
votes
2answers
664 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?$
3
votes
1answer
167 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, ...
2
votes
0answers
99 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 ...
6
votes
0answers
150 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$...
6
votes
1answer
138 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 ...
2
votes
2answers
200 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+\...
1
vote
0answers
110 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)$ ...
2
votes
0answers
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 ...
4
votes
2answers
264 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 ...
12
votes
1answer
500 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 ...
30
votes
0answers
825 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 ...
4
votes
1answer
467 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 ...
12
votes
2answers
520 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}$ ...
20
votes
1answer
679 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 ...
8
votes
1answer
321 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 ...
17
votes
0answers
433 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\...
2
votes
0answers
232 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 $\...
11
votes
1answer
354 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 ...
6
votes
1answer
259 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$? ...
5
votes
3answers
441 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?
...
1
vote
1answer
276 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\...
15
votes
3answers
603 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 (...
8
votes
0answers
166 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 ...
