Questions tagged [metric-embeddings]
The metric-embeddings tag has no usage guidance.
58
questions
9
votes
0
answers
214
views
Embedding a graph into Euclidean space
I want to find a map $v\mapsto \tilde v$ from the vertex set of a connected infinite graph $\Gamma$ to a Euclidean space that meets the following two conditions:
there is $\varepsilon>0$ such that ...
- 41k
1
vote
1
answer
255
views
Bilipschitz embedding of the unit ball of $c_0$ into $\ell_1$
This is a follow-up to this question of mine.
It is well-known that the Banach space $\ell_1$ does not contain any isomorphic copies of $c_0$. One can even go further and show that $\ell_1$ does not ...
- 1,119
2
votes
1
answer
155
views
Volume of submanifold as integral of delta-function
Let $M$ be an $n-m$ dimensional sub-manifold of $\mathbf R^n$ defined by the following set of equations:
\begin{equation}
f_1(\vec x)=0, \\
\vdots \\
f_m(\vec x)=0,
\end{equation}
(where $\vec x$ are ...
- 413
3
votes
0
answers
154
views
Volume of sub-manifold of $\mathbf R^n$
Let $M$ be an $n-m$ dimensional sub-manifold of $\mathbf R^n$ defined by the following set of polynomial equations:
\begin{equation}
P_1(\vec x)=0, \\
\vdots \\
P_m(\vec x)=0,
\end{equation}
(where $\...
- 413
5
votes
1
answer
183
views
Isomorphic embedding of $l^n_{\infty}$ into $l_1^m$?
Given $n$, is there a $C(n)$-isomorphic embedding of $l^n_{\infty}$ into $l^m_1$ for sufficiently large $m$ and $C(n)<<\log(n)$?
For $n=2$ this can done with $m=2$. There are some results about $...
- 725
4
votes
1
answer
187
views
Johnson-Lindenstrauss over torus?
The Johnson-Lindenstrauss lemma is a famous result in dimensionality reduction — Given $m$ points in $\mathbb{R}^N$, and $\varepsilon >0$, there exists a quasi-isometry $f : \mathbb{R}^N\to\mathbb{...
- 1,307
3
votes
0
answers
139
views
Constant in Naor and Neiman's Assouad Theorem
In Naor and Neiman's Assouad embedding theorem - "Assouad’s theorem with dimension independent of the snowflaking" Revisita Mathematica, the authors derive quantitative estimates on the ...
- 4,881
4
votes
0
answers
199
views
To what extent is the Nash embedding not unique?
Consider a smooth Nash embedding, $f$, of a Riemannian manifold $Σ$ into Euclidean space $\mathbb R^n$. To what extent is this embedding not unique?
It is clear that the set of all such embeddings ...
- 413
7
votes
3
answers
298
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 ...
- 115
3
votes
1
answer
226
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 ...
3
votes
0
answers
71
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)...
- 115
12
votes
2
answers
973
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 ...
- 115
1
vote
0
answers
76
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 ...
- 115
5
votes
2
answers
181
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 $\...
- 123
2
votes
0
answers
86
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,...
7
votes
1
answer
182
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? ...
- 73
1
vote
0
answers
69
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 ...
- 4,309
2
votes
0
answers
78
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,...
- 83
6
votes
1
answer
402
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)$.
...
6
votes
1
answer
287
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)$ ...
- 850
4
votes
1
answer
193
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 ...
- 4,881
5
votes
0
answers
151
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
1
answer
131
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$?
...
- 429
3
votes
0
answers
96
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 ...
- 31
2
votes
0
answers
76
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 ...
- 4,881
10
votes
0
answers
771
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 ...
user6671
2
votes
0
answers
114
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 ...
user6671
2
votes
0
answers
122
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 $\...
- 21
2
votes
0
answers
121
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 ...
- 161
6
votes
0
answers
213
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 \...
user6671
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 ...
user6671
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=\...
- 91
5
votes
1
answer
483
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....
user6671
0
votes
1
answer
76
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)\...
- 4,881
0
votes
0
answers
117
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$. ...
- 83
5
votes
2
answers
874
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
1
answer
207
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, ...
- 850
2
votes
0
answers
115
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 ...
- 133
7
votes
0
answers
192
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$...
- 850
6
votes
1
answer
170
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 ...
- 63
2
votes
2
answers
243
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+\...
- 9,538
1
vote
0
answers
125
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)$ ...
- 13.2k
2
votes
0
answers
57
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 ...
- 13.2k
4
votes
2
answers
288
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 ...
- 4,818
12
votes
1
answer
547
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 ...
- 4,818
32
votes
0
answers
880
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,818
4
votes
1
answer
593
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 ...
- 515
14
votes
3
answers
720
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}$ ...
- 9,903
20
votes
1
answer
900
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 ...
- 2,061
8
votes
1
answer
380
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 ...
- 83