Repository logo
 

ε -Isometric Dimension Reduction for Incompressible Subsets of ℓp

Published version
Peer-reviewed

Repository DOI


Change log

Authors

Abstract

jats:titleAbstract</jats:title>jats:pFix jats:inline-formulajats:alternativesjats:tex-math$$p\in [1,\infty )$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mip</mml:mi> mml:mo∈</mml:mo> mml:mo[</mml:mo> mml:mn1</mml:mn> mml:mo,</mml:mo> mml:mi∞</mml:mi> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, jats:inline-formulajats:alternativesjats:tex-math$$K\in (0,\infty )$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:miK</mml:mi> mml:mo∈</mml:mo> mml:mo(</mml:mo> mml:mn0</mml:mn> mml:mo,</mml:mo> mml:mi∞</mml:mi> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, and a probability measure jats:inline-formulajats:alternativesjats:tex-math$$\mu $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:miμ</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>. We prove that for every jats:inline-formulajats:alternativesjats:tex-math$$n\in \mathbb {N}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:min</mml:mi> mml:mo∈</mml:mo> mml:miN</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, jats:inline-formulajats:alternativesjats:tex-math$$\varepsilon \in (0,1)$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:miε</mml:mi> mml:mo∈</mml:mo> mml:mo(</mml:mo> mml:mn0</mml:mn> mml:mo,</mml:mo> mml:mn1</mml:mn> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, and jats:inline-formulajats:alternativesjats:tex-math$$x_1,\ldots ,x_n\in L_p(\mu )$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:msub mml:mix</mml:mi> mml:mn1</mml:mn> </mml:msub> mml:mo,</mml:mo> mml:mo…</mml:mo> mml:mo,</mml:mo> mml:msub mml:mix</mml:mi> mml:min</mml:mi> </mml:msub> mml:mo∈</mml:mo> mml:msub mml:miL</mml:mi> mml:mip</mml:mi> </mml:msub> mml:mrow mml:mo(</mml:mo> mml:miμ</mml:mi> mml:mo)</mml:mo> </mml:mrow> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> with jats:inline-formulajats:alternativesjats:tex-math$$\big \Vert \max _{i\in {1,\ldots ,n}} |x_i| \big \Vert {L_p(\mu )} \le K$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mrow mml:mo‖</mml:mo> </mml:mrow> mml:msub mml:momax</mml:mo> mml:mrow mml:mii</mml:mi> mml:mo∈</mml:mo> mml:mo{</mml:mo> mml:mn1</mml:mn> mml:mo,</mml:mo> mml:mo…</mml:mo> mml:mo,</mml:mo> mml:min</mml:mi> mml:mo}</mml:mo> </mml:mrow> </mml:msub> mml:mrow mml:mo|</mml:mo> mml:msub mml:mix</mml:mi> mml:mii</mml:mi> </mml:msub> mml:mo|</mml:mo> </mml:mrow> mml:msub mml:mrow mml:mo‖</mml:mo> </mml:mrow> mml:mrow mml:msub mml:miL</mml:mi> mml:mip</mml:mi> </mml:msub> mml:mrow mml:mo(</mml:mo> mml:miμ</mml:mi> mml:mo)</mml:mo> </mml:mrow> </mml:mrow> </mml:msub> mml:mo≤</mml:mo> mml:miK</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, there exist jats:inline-formulajats:alternativesjats:tex-math$$d\le \frac{32e^2 (2K)^{2p}\log n}{\varepsilon ^2}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mid</mml:mi> mml:mo≤</mml:mo> mml:mfrac mml:mrow mml:mn32</mml:mn> mml:msup mml:mie</mml:mi> mml:mn2</mml:mn> </mml:msup> mml:msup mml:mrow mml:mo(</mml:mo> mml:mn2</mml:mn> mml:miK</mml:mi> mml:mo)</mml:mo> </mml:mrow> mml:mrow mml:mn2</mml:mn> mml:mip</mml:mi> </mml:mrow> </mml:msup> mml:molog</mml:mo> mml:min</mml:mi> </mml:mrow> mml:msup mml:miε</mml:mi> mml:mn2</mml:mn> </mml:msup> </mml:mfrac> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> and vectors jats:inline-formulajats:alternativesjats:tex-math$$y_1,\ldots , y_n \in \ell p^d$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:msub mml:miy</mml:mi> mml:mn1</mml:mn> </mml:msub> mml:mo,</mml:mo> mml:mo…</mml:mo> mml:mo,</mml:mo> mml:msub mml:miy</mml:mi> mml:min</mml:mi> </mml:msub> mml:mo∈</mml:mo> mml:msubsup mml:miℓ</mml:mi> mml:mip</mml:mi> mml:mid</mml:mi> </mml:msubsup> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> such that jats:disp-formulajats:alternativesjats:tex-math$$\begin{aligned} {\forall },,i,j\in {1,\ldots ,n}, \quad \Vert x_i-x_j\Vert ^p{L_p(\mu )}-\varepsilon\le & {} \Vert y_i-y_j\Vert {\ell p^d}^p\le \Vert x_i-x_j\Vert ^p{L_p(\mu )}+\varepsilon . \end{aligned}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mtable mml:mtr mml:mtd mml:mrow mml:mrow mml:mo∀</mml:mo> <mml:mspace /> <mml:mspace /> mml:mii</mml:mi> mml:mo,</mml:mo> mml:mij</mml:mi> mml:mo∈</mml:mo> mml:mrow mml:mo{</mml:mo> mml:mn1</mml:mn> mml:mo,</mml:mo> mml:mo…</mml:mo> mml:mo,</mml:mo> mml:min</mml:mi> mml:mo}</mml:mo> </mml:mrow> mml:mo,</mml:mo> <mml:mspace /> mml:mo‖</mml:mo> </mml:mrow> mml:msub mml:mix</mml:mi> mml:mii</mml:mi> </mml:msub> mml:mo-</mml:mo> mml:msub mml:mix</mml:mi> mml:mij</mml:mi> </mml:msub> mml:msubsup mml:mrow mml:mo‖</mml:mo> </mml:mrow> mml:mrow mml:msub mml:miL</mml:mi> mml:mip</mml:mi> </mml:msub> mml:mrow mml:mo(</mml:mo> mml:miμ</mml:mi> mml:mo)</mml:mo> </mml:mrow> </mml:mrow> mml:mip</mml:mi> </mml:msubsup> mml:mo-</mml:mo> mml:miε</mml:mi> mml:mo≤</mml:mo> </mml:mrow> </mml:mtd> mml:mtd mml:mrow mml:mrow <mml:mrow /> mml:mo‖</mml:mo> </mml:mrow> mml:msub mml:miy</mml:mi> mml:mii</mml:mi> </mml:msub> mml:mo-</mml:mo> mml:msub mml:miy</mml:mi> mml:mij</mml:mi> </mml:msub> mml:msubsup mml:mrow mml:mo‖</mml:mo> </mml:mrow> mml:mrow mml:msubsup mml:miℓ</mml:mi> mml:mip</mml:mi> mml:mid</mml:mi> </mml:msubsup> </mml:mrow> mml:mip</mml:mi> </mml:msubsup> mml:mo≤</mml:mo> mml:msubsup mml:mrow mml:mo‖</mml:mo> mml:msub mml:mix</mml:mi> mml:mii</mml:mi> </mml:msub> mml:mo-</mml:mo> mml:msub mml:mix</mml:mi> mml:mij</mml:mi> </mml:msub> mml:mo‖</mml:mo> </mml:mrow> mml:mrow mml:msub mml:miL</mml:mi> mml:mip</mml:mi> </mml:msub> mml:mrow mml:mo(</mml:mo> mml:miμ</mml:mi> mml:mo)</mml:mo> </mml:mrow> </mml:mrow> mml:mip</mml:mi> </mml:msubsup> mml:mo+</mml:mo> mml:miε</mml:mi> mml:mo.</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math></jats:alternatives></jats:disp-formula>Moreover, the argument implies the existence of a greedy algorithm which outputs jats:inline-formulajats:alternativesjats:tex-math$${y_i}{i=1}^n$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msubsup mml:mrow mml:mo{</mml:mo> mml:msub mml:miy</mml:mi> mml:mii</mml:mi> </mml:msub> mml:mo}</mml:mo> </mml:mrow> mml:mrow mml:mii</mml:mi> mml:mo=</mml:mo> mml:mn1</mml:mn> </mml:mrow> mml:min</mml:mi> </mml:msubsup> </mml:math></jats:alternatives></jats:inline-formula> after receiving jats:inline-formulajats:alternativesjats:tex-math$${x_i}{i=1}^n$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msubsup mml:mrow mml:mo{</mml:mo> mml:msub mml:mix</mml:mi> mml:mii</mml:mi> </mml:msub> mml:mo}</mml:mo> </mml:mrow> mml:mrow mml:mii</mml:mi> mml:mo=</mml:mo> mml:mn1</mml:mn> </mml:mrow> mml:min</mml:mi> </mml:msubsup> </mml:math></jats:alternatives></jats:inline-formula> as input. The proof relies on a derandomized version of Maurey’s empirical method (1981) combined with a combinatorial idea of Ball (1990) and a suitable change of measure. Motivated by the above embedding, we introduce the notion of jats:inline-formulajats:alternativesjats:tex-math$$\varepsilon $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:miε</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>-isometric dimension reduction of the unit ball jats:inline-formulajats:alternativesjats:tex-math$${\textbf {B}}_E$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msub mml:miB</mml:mi> mml:miE</mml:mi> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula> of a normed space jats:inline-formulajats:alternativesjats:tex-math$$(E,\Vert \cdot \Vert E)$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mo(</mml:mo> mml:miE</mml:mi> mml:mo,</mml:mo> mml:mo‖</mml:mo> mml:mo·</mml:mo> mml:msub mml:mo‖</mml:mo> mml:miE</mml:mi> </mml:msub> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> and we prove that jats:inline-formulajats:alternativesjats:tex-math$${\textbf {B}}{\ell _p}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msub mml:miB</mml:mi> mml:msub mml:miℓ</mml:mi> mml:mip</mml:mi> </mml:msub> </mml:msub> </mml:math></jats:alternatives></jats:inline-formula> does not admit jats:inline-formulajats:alternativesjats:tex-math$$\varepsilon $$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:miε</mml:mi> </mml:math></jats:alternatives></jats:inline-formula>-isometric dimension reduction by linear operators for any value of jats:inline-formulajats:alternativesjats:tex-math$$p\ne 2$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mip</mml:mi> mml:mo≠</mml:mo> mml:mn2</mml:mn> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>.</jats:p>

Description

Acknowledgements: I am grateful to Keith Ball, Assaf Naor, and Pierre Youssef for insightful discussions and useful feedback.

Keywords

4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

Discrete and Computational Geometry

Conference Name

Journal ISSN

0179-5376
1432-0444

Volume Title

71

Publisher

Springer Science and Business Media LLC