-isometric dimension reduction for incompressible subsets of _p

DOI10.1007/S00454-023-00587-WMaRDI QIDQ6145674zbMATH OpenFDO

Authors Alexandros Eskenazis

Publication date 9 January 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2109.06602

zbMATH Keywords

\( \varepsilon \)-isometric embeddingchange of measuredimension reductionMaurey's empirical method

Mathematics Subject Classification ID

Probabilistic methods in Banach space theory (46B09) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Spaces of measurable functions ((L^p)-spaces, Orlicz spaces, Köthe function spaces, Lorentz spaces, rearrangement invariant spaces, ideal spaces, etc.) (46E30) Metric embeddings as related to computational problems and algorithms (68R12)

Abstract: Fix $pin[1,infty)$, $Kin(0,infty)$ and a probability measure $mu$. We prove that for every $ninmathbbN$, $varepsilonin(0,1)$ and $x_1,ldots,x_{n}in{L}_p(mu)$ with $$, there exists $dleqfrac32e^2(2K{)}^{2p}lognvarepsilo{n}^2$ and vectors $y_1,ldots,y_{n}inel{l}_p^d$ such that ${\displaystyle }$forall i,jin{1,ldots,n}, qquad |x_i-x_j|^p_{L_p(mu)}- varepsilon leq |y_i-y_j|_{ell_p^d}^p leq |x_i-x_j|^p_{L_p(mu)}+varepsilon.${\displaystyle }$ Moreover, the argument implies the existence of a greedy algorithm which outputs ${y_i}_{i=1}^n$ after receiving ${x_i}_{i=1}^n$ as input. The proof relies on a derandomized version of Maurey's empirical method (1981) combined with a combinatorial idea of Ball (1990) and classical factorization theory of $L_p(mu)$ spaces. Motivated by the above embedding, we introduce the notion of $varepsilon$-isometric dimension reduction of the unit ball $$ of a normed space $(E,|cdot{|}_E)$ and we prove that $$ does not admit $varepsilon$-isometric dimension reduction by linear operators for any value of $peq2$.

Recommendations

• On the impossibility of dimension reduction for doubling subsets of \(\ell_p\)
• On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
• Isomorphic embedding of \(\ell_p^n\), \(1<p<2\), into \(\ell_1^{(1+\varepsilon)n}\)
• Tight embedding of subspaces of 𝐿_{𝑝} in ℓ_{𝑝}ⁿ for even 𝑝
• Dimension reduction techniques for \(\ell_p\) \((1<p<2)\), with applications

Cites work

• A Quantized Johnson–Lindenstrauss Lemma: The Finding of Buffon’s Needle
• A simple tool for bounding the deviation of random matrices on geometric sets
• An algorithmic theory of learning: Robust concepts and random projection
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Approximate Carathéodory's theorem in uniformly smooth Banach spaces
• Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings
• Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory's theorem
• Bounds on Dimension Reduction in the Nuclear Norm
• Concentration of the distance in finite dimensional normed spaces
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Dimension reduction by random hyperplane tessellations
• Dimensionality reduction with subgaussian matrices: a unified theory
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Empirical processes and random projections
• Extensions of Lipschitz mappings into a Hilbert space
• Finite dimensional subspaces of \(L_p\)
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 4061904 (Why is no real title available?)
• scientific article; zbMATH DE number 3772326 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 3437855 (Why is no real title available?)
• Isometric embedding in \(\ell_ p\)-spaces
• Metric dimension reduction: a snapshot of the Ribe program
• Metric embeddings. Bilipschitz and coarse embeddings into Banach spaces
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Nearest-neighbor-preserving embeddings
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• On the distortion required for embedding finite metric spaces into normed spaces
• On the impossibility of dimension reduction in l ₁
• On the Volume of the Intersection of Two L n p Balls
• On variants of the Johnson–Lindenstrauss lemma
• Revisiting the approximate Carathéodory problem via the Frank-Wolfe algorithm
• Sampling discretization and related problems
• Small Width, Low Distortions: Quantized Random Embeddings of Low-complexity Sets
• Sparser Johnson-Lindenstrauss transforms
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces

This page was built for publication: \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145674)