A spectral gap precludes low-dimensional embeddings

DOI10.4230/LIPICS.SOCG.2017.50zbMATH Open1433.68312arXiv1611.08861OpenAlexW2964245156MaRDI QIDQ4580127FDOQ4580127

Authors: Assaf Naor 

Publication date: 13 August 2018

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.

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

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\)

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)

Cited In (7)

• Title not available (Why is that?)
• Comparison of metric spectral gaps
• An average John theorem
• Nonpositive curvature is not coarsely universal
• Dimension reduction for maximum matchings and the fastest mixing Markov chain
• Impossibility of dimension reduction in the nuclear norm
• Impossibility of almost extension

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)