Comparison of metric spectral gaps

DOI10.2478/AGMS-2014-0001zbMATH Open1316.46023arXiv1308.2851OpenAlexW2963946210MaRDI QIDQ5402099FDOQ5402099

Authors: Assaf Naor 

Publication date: 5 March 2014

Published in: Analysis and Geometry in Metric Spaces (Search for Journal in Brave)

Abstract: Let $A=(a_{ij})in{M}_n(R)$ be an $n$ by $n$ symmetric stochastic matrix. For $pin[1,infty)$ and a metric space $(X,d_X)$, let $gamma(A,d_X^p)$ be the infimum over those $gammain(0,infty]$ for which every $x_1,\mathrm{...},x_{n}inX$ satisfy ${\displaystyle }$ frac{1}{n^2} sum_{i=1}^nsum_{j=1}^n d_X(x_i,x_j)^ple frac{gamma}{n}sum_{i=1}^nsum_{j=1}^n a_{ij} d_X(x_i,x_j)^p. ${\displaystyle }$ Thus $gamma(A,d_X^p)$ measures the magnitude of the {em nonlinear spectral gap} of the matrix $A$ with respect to the kernel $d_X^p:XimesXo[0,infty)$. We study pairs of metric spaces $(X,d_X)$ and $(Y,d_Y)$ for which there exists $Psi:(0,infty)o(0,infty)$ such that $gamma(A,d_X^p)lePsi(gamma(A,d_Y^p))$ for every symmetric stochastic $Ain{M}_n(R)$ with $gamma(A,d_Y^p)<infty$. When $Psi$ is linear a complete geometric characterization is obtained. Our estimates on nonlinear spectral gaps yield new embeddability results as well as new nonembeddability results. For example, it is shown that if $ninN$ and $pin(2,infty)$ then for every $f_1,\mathrm{...},f_{n}in{L}_p$ there exist $x_1,\mathrm{...},x_{n}in{L}_2$ such that {equation}label{eq:p factor} forall, i,jin {1,...,n},quad |x_i-x_j|_2lesssim p|f_i-f_j|_p, {equation} and ${\displaystyle }$ sum_{i=1}^nsum_{j=1}^n |x_i-x_j|_2^2=sum_{i=1}^nsum_{j=1}^n |f_i-f_j|_p^2. ${\displaystyle }$ This statement is impossible for $pin[1,2)$, and the asymptotic dependence on $p$ in eqref{eq:p factor} is sharp. We also obtain the best known lower bound on the $L_p$ distortion of Ramanujan graphs, improving over the work of Matouv{s}ek. Links to Bourgain--Milman--Wolfson type and a conjectural nonlinear Maurey--Pisier theorem are studied.

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

Recommendations

• A spectral gap precludes low-dimensional embeddings
• Nonlinear spectral calculus and super-expanders
• Towards a calculus for non-linear spectral gaps
• Uniform estimates of nonlinear spectral gaps
• Metric \(X_{p}\) inequalities

zbMATH Keywords

expandersmetric embeddingsnonlinear spectral gapsnonlinear type

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Stochastic matrices (15B51) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• The concentration of measure phenomenon
• Lectures on analysis on metric spaces
• Extending Lipschitz functions via random metric partitions
• Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Note on Coverings and Packings
• A reinforcement of property (T)
• Martingales with values in uniformly convex spaces
• Geometric algorithms and combinatorial optimization.
• The geometry of graphs and some of its algorithmic applications
• Title not available (Why is that?)
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach
• Expander flows, geometric embeddings and graph partitioning
• Geometry of cuts and metrics
• Ramanujan graphs
• Sharp uniform convexity and smoothness inequalities for trace norms
• Nonlinear spectral calculus and super-expanders
• Towards strong Banach property (T) for \(\mathrm{SL}(3,\mathbb R)\)
• Complex interpolation between Hilbert, Banach and operator spaces
• A strengthened Banach property (T) and the fast Fourier transform
• Title not available (Why is that?)
• Intermediate spaces and interpolation, the complex method
• Poincaré inequalities, embeddings, and wild groups.
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
• Embedded in the Shadow of the Separator
• Optimal numberings and isoperimetric problems on graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• Diameters and Eigenvalues
• Markov type and threshold embeddings
• Random walk in random groups.
• The diameter of random regular graphs
• Random Cayley graphs and expanders
• An introduction to the Ribe program
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Random Sign Embeddings From l n r , 2 < r < &#8734
• A generalization of Khintchine's inequality and its application in the theory of operator ideals
• Title not available (Why is that?)
• On Type of Metric Spaces
• Remarks on non linear type and Pisiers inequality
• Euclidean distortion and the sparsest cut
• Metric cotype
• The coarse geometric Novikov conjecture and uniform convexity
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Markov chains, Riesz transforms and Lipschitz maps
• On metric Ramsey-type phenomena
• Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
• On distance scales, embeddings, and efficient relaxations of the cut cone
• On the moduli of convexity and smoothness
• Excluded minors, network decomposition, and multicommodity flow
• Title not available (Why is that?)
• Improved lower bounds for embeddings into \(L_1\)
• Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian
• The Restricted Isometry Property of Subsampled Fourier Matrices
• The distortion problem
• A NOTE ON NON-AMENABILITY OF ℬ(ℓ_p) FOR p=1,2
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• An asymptotic isoperimetric inequality
• Title not available (Why is that?)
• An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
• Hard metrics from Cayley graphs of abelian groups
• On embedding expanders into \(\ell_p\) spaces
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Sign-Embeddings of l n 1
• Interpolation of Uniformly Convex Banach Spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonembeddability theorems via Fourier analysis
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Title not available (Why is that?)
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• On uniform homeomorphisms of the unit spheres of certain Banach lattices
• On average distortion of embedding metrics into the line
• Über die zusammenziehende und Lipschitzsche Transformationen
• Extending Lipschitz and Hölder maps between metric spaces
• Markov type of Alexandrov spaces of non-negative curvature
• Integrality gaps for sparsest cut and minimum linear arrangement problems
• A PRG for lipschitz functions of polynomials with applications to sparsest cut
• Title not available (Why is that?)
• Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
• On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs
• Spectral calculus and Lipschitz extension for barycentric metric spaces
• Expanders with respect to Hadamard spaces and random graphs
• Pisier's inequality revisited

Cited In (9)

• On the computation of the gap metric
• Group approximation in Cayley topology and coarse geometry. II: Fibred coarse embeddings
• METRIC INEQUALITIES
• On quantitative sphere equivalence and extrapolation phenomenon
• Vertical perimeter versus horizontal perimeter
• Banach space actions and \(L^2\)-spectral gap
• An average John theorem
• Nonpositive curvature is not coarsely universal
• Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings

This page was built for publication: Comparison of metric spectral gaps

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