Skip to main content

Questions tagged [metric-embeddings]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10 votes
1 answer
139 views

Is the face lattice of the cube a polytope graph?

The face lattice of a convex polytope $P\subset\Bbb R^d$ is the partially ordered set whose elements are the faces of $P$ ordered by inclusion. We can turn it into a graph by considering its Hasse ...
M. Winter's user avatar
  • 12.8k
1 vote
1 answer
97 views

Alexandrov's uniqueness theorem in Minkowski spacetime

Suppose $P$ is a convex polyhedron in $\mathbb{R}^{2,1}$. Each face of $P$ comes with induced metric tensor, if the face is space-like, then it is euclidean metric; every time-like face is isometric ...
Anton Petrunin's user avatar
4 votes
1 answer
83 views

Embedding a countably infinite metric space in $\ell^2(\mathbb Z_+)$

Suppose $(X,d)$ is a countably infinite set endowed with a metric $d$ that satisfies the following condition: Every finite subset of $X$ with the induced metric is isometric to a subset of some ...
Daniel Asimov's user avatar
0 votes
0 answers
61 views

Can the sequence of complete graphs coarsely embed into Hilbert space?

Basically the title. If I have the metric space which is the disjoint union of the sequence of complete graphs, and the usual graph metric, has it been shown that the metric space can be coarsely ...
kreitz's user avatar
  • 53
0 votes
0 answers
30 views

Is there a bi-Hölder Weierstrass-type embedding of the circle into some Euclidean space?

We say that $\Phi\colon S^1\to \mathbb{R}^d$ is an $\alpha$-bi-Hölder embedding if there are constants $c_1,c_2>0$, such that $$c_1\leq \frac{\|\Phi(x)-\Phi(y)\|}{d(x,y)^\alpha}\leq c_2,$$ where $d$...
Roope Anttila's user avatar
5 votes
1 answer
137 views

Variants of the Bonk-Schramm embedding

Recently I heard about the following embedding theorem of Bonk and Schramm: every Gromov hyperbolic geodesic metric space with "bounded growth" is roughly similar to a convex subset of $\...
Takao Hishikori's user avatar
2 votes
2 answers
194 views

Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$

Question: is it always possible to embed a complete, symmetric and metric graph $G$ with $n+1$ vertices isometrically in $\mathbb{R}^n$? I'm convinced it must be true, but can't remember having seen ...
Manfred Weis's user avatar
  • 12.8k
1 vote
0 answers
117 views

Intuition behind right-inverse of map from Johnson-Lindenstrauss Lemma

The Johnson–Lindenstrauss lemma states that for every $n$-point subset $X$ of $\mathbb{R}^d$ and each $0<\varepsilon\le 1$, there is a linear map $f:\mathbb{R}^d\to\mathbb{R}^{O(\log(n)/\varepsilon^...
ABIM's user avatar
  • 4,809
3 votes
1 answer
180 views

Bi-Lipschitz embeddings of compact doubling spaces

Suppose that $(X,\rho)$ is a compact doubling metric space. Does there necessarily exist an $\epsilon>0$ and a maximal $\epsilon$-net $\{x_i\}_{i=1}^n\subseteq X$ such that the map $$ \begin{...
ABIM's user avatar
  • 4,809
1 vote
0 answers
121 views

Do cycle graphs embed isometrically in spheres?

I recently came across, what seems to be a folklore. Namely, that cycle graphs embeds isometrically into spheres $S^n(r)$, for some $n\in \mathbb{N}_+$ and some $r>0$. However, I could not track ...
Justin_other_PhD's user avatar
9 votes
0 answers
339 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 ...
Anton Petrunin's user avatar
1 vote
1 answer
269 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 ...
Damian Sobota's user avatar
2 votes
1 answer
295 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 ...
dennis's user avatar
  • 423
3 votes
0 answers
194 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 $\...
dennis's user avatar
  • 423
5 votes
1 answer
302 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 $...
Arun 's user avatar
  • 735
4 votes
1 answer
207 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{...
Mark Schultz-Wu's user avatar
3 votes
0 answers
154 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 ...
ABIM's user avatar
  • 4,809
4 votes
0 answers
221 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 ...
dennis's user avatar
  • 423
7 votes
3 answers
330 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 ...
Carlos_Petterson's user avatar
3 votes
1 answer
354 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 ...
Dmitry Vilensky's user avatar
2 votes
0 answers
88 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)...
Carlos_Petterson's user avatar
17 votes
2 answers
1k 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 ...
Carlos_Petterson's user avatar
1 vote
0 answers
95 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 ...
Carlos_Petterson's user avatar
5 votes
2 answers
192 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 $\...
Zaragosa's user avatar
  • 133
2 votes
0 answers
91 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,...
John_Algorithm's user avatar
7 votes
1 answer
191 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? ...
Rui Liu's user avatar
  • 73
1 vote
0 answers
73 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 ...
leo monsaingeon's user avatar
2 votes
0 answers
97 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,...
Timothy Chu's user avatar
7 votes
1 answer
536 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)$. ...
Bernard_Karkanidis's user avatar
7 votes
1 answer
379 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)$ ...
Vladimir Zolotov's user avatar
4 votes
1 answer
242 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 ...
ABIM's user avatar
  • 4,809
5 votes
0 answers
168 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 ...
NaivelyCurious's user avatar
3 votes
1 answer
137 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$? ...
user92646's user avatar
  • 617
3 votes
0 answers
103 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 ...
Mauro Patrão's user avatar
2 votes
0 answers
77 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 ...
ABIM's user avatar
  • 4,809
10 votes
0 answers
788 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
3 votes
0 answers
126 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
1 vote
1 answer
199 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 $\...
user149610's user avatar
2 votes
0 answers
129 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 ...
GWB's user avatar
  • 181
6 votes
0 answers
217 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
35 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
103 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=\...
user134977's user avatar
5 votes
1 answer
566 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
81 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)\...
ABIM's user avatar
  • 4,809
0 votes
0 answers
132 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$. ...
Timothy Chu's user avatar
5 votes
2 answers
941 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?$
GAUTAM NEELAKANTAN's user avatar
3 votes
1 answer
232 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, ...
Vladimir Zolotov's user avatar
2 votes
0 answers
125 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 ...
user3799934's user avatar
8 votes
0 answers
211 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$...
Vladimir Zolotov's user avatar
6 votes
1 answer
188 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 ...
vvv's user avatar
  • 63