Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBi-Lipschitz embeddings of quasiconformal trees
64
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A quasiconformal tree is a doubling metric tree in which the diameter of each arc is bounded above by a fixed multiple of the distance between its endpoints. In this paper we show that every quasiconformal tree bi-Lipschitz embeds in some Euclidean space, with the ambient dimension and the bi-Lipschitz constant depending only on the doubling and bounded turning constants of the tree. This answers Question 1.6 in cite{DV} (arXiv:2007.12297).
rate research
Read More
We study the Lipschitz structures on the geodesic compactification of a regular tree, that are preserved by the automorphism group. They are shown to be similar to the compactifications introduced by William Floyd, and a complete description is given.
We propose a dimensionality reducing matrix design based on training data with constraints on its Frobenius norm and number of rows. Our design criteria is aimed at preserving the distances between the data points in the dimensionality reduced space as much as possible relative to their distances in original data space. This approach can be considered as a deterministic Bi-Lipschitz embedding of the data points. We introduce a scalable learning algorithm, dubbed AMUSE, and provide a rigorous estimation guarantee by leveraging game theoretic tools. We also provide a generalization characterization of our matrix based on our sample data. We use compressive sensing problems as an example application of our problem, where the Frobenius norm design constraint translates into the sensing energy.
In this article we start a systematic study of the bi-Lipschitz geometry of lamplighter graphs. We prove that lamplighter graphs over trees bi-Lipschitzly embed into Hamming cubes with distortion at most~$6$. It follows that lamplighter graphs over countable trees bi-Lipschitzly embed into $ell_1$. We study the metric behaviour of the operation of taking the lamplighter graph over the vertex-coalescence of two graphs. Based on this analysis, we provide metric characterizations 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 characterization 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 Ostrovskiis characterization previously obtained in cite{ostrovskii:11}.
The problem of computing a bi-Lipschitz embedding of a graphical metric into the line with minimum distortion has received a lot of attention. The best-known approximation algorithm computes an embedding with distortion $O(c^2)$, where $c$ denotes the optimal distortion [Bu{a}doiu etal~2005]. We present a bi-criteria approximation algorithm that extends the above results to the setting of emph{outliers}. Specifically, we say that a metric space $(X,rho)$ admits a $(k,c)$-embedding if there exists $Ksubset X$, with $|K|=k$, such that $(Xsetminus K, rho)$ admits an embedding into the line with distortion at most $c$. Given $kgeq 0$, and a metric space that admits a $(k,c)$-embedding, for some $cgeq 1$, our algorithm computes a $({mathsf p}{mathsf o}{mathsf l}{mathsf y}(k, c, log n), {mathsf p}{mathsf o}{mathsf l}{mathsf y}(c))$-embedding in polynomial time. This is the first algorithmic result for outlier bi-Lipschitz embeddings. Prior to our work, comparable outlier embeddings where known only for the case of additive distortion.
We prove sharp bounds for the product and the sum of two hyperbolic distances between the opposite sides of hyperbolic Lambert quadrilaterals in the unit disk. Furthermore, we study the images of Lambert quadrilaterals under quasiconformal mappings from the unit disk onto itself and obtain sharp results in this case, too.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
