A spectral gap precludes low-dimensional embeddings

DOI10.4230/LIPICS.SOCG.2017.50MaRDI QIDQ4580127zbMATHOpenAlexFDO

Authors Assaf Naor

Publication date 13 August 2018

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

zbMATH Keywords

dimensionality reductioncomplex interpolationexpander graphsnearest neighbor searchMarkov typemetric embeddingsnonlinear spectral gaps

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Stochastic matrices (15B51) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Metric embeddings as related to computational problems and algorithms (68R12)

Abstract: We prove that there is a universal constant $C>0$ with the following property. Suppose that $ninmathbbN$ and that $mathsfA=(a_{ij})in{M}_n(mathbbR)$ is a symmetric stochastic matrix. Denote the second-largest eigenvalue of $mathsfA$ by $lambd{a}_2(mathsfA)$. Then for $mathrmitany$ finite-dimensional normed space $(X,|cdot|)$ we have ${\displaystyle }$ forall, x_1,ldots,x_nin X,qquad mathrm{dim}(X)ge frac12 expleft(Cfrac{1-lambda_2(mathsf{A})}{sqrt{n}}�igg(frac{sum_{i=1}^nsum_{j=1}^n|x_i-x_j|^2}{sum_{i=1}^nsum_{j=1}^na_{ij}|x_i-x_j|^2}�igg)^{frac12} ight). ${\displaystyle }$ This implies that if an $n$-vertex $O(1)$-expander embeds with average distortion $Dge1$ into $X$, then necessarily $mathrmdim(X)gtrsim{n}^{c/D}$ for some universal constant $c>0$, thus improving over the previously best-known estimate $mathrmdim(X)gtrsim(logn{)}^2/D^2$ of Linial, London and Rabinovich, strengthening a theorem of Matouv{s}ek, and answering a question of Andoni, Nikolov, Razenshteyn and Waingarten.

Recommendations

• An average John theorem
• Approximating sparsest cut in low rank graphs via embeddings from approximately low-dimensional spaces
• On embedding expanders into \(\ell_p\) spaces
• Comparison of metric spectral gaps
• Embedding approximately low-dimensional \(\ell_2^2\) metrics into \(\ell_1\)

Cited in

(7)

• scientific article; zbMATH DE number 6287557 (Why is no real title available?)
• Nonpositive curvature is not coarsely universal
• Impossibility of almost extension
• Approximating sparsest cut in low rank graphs via embeddings from approximately low-dimensional spaces
• Dimension reduction for maximum matchings and the fastest mixing Markov chain
• Comparison of metric spectral gaps
• An average John theorem

This page was built for publication: A spectral gap precludes low-dimensional embeddings

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