A spectral gap precludes low-dimensional embeddings
From MaRDI portal
Publication:4580127
DOI10.4230/LIPICS.SOCG.2017.50zbMath1433.68312arXiv1611.08861OpenAlexW2964245156MaRDI QIDQ4580127
Publication date: 13 August 2018
Full work available at URL: https://arxiv.org/abs/1611.08861
dimensionality reductioncomplex interpolationexpander graphsnearest neighbor searchMarkov typemetric embeddingsnonlinear spectral gaps
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)
Related Items (4)
Impossibility of almost extension ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ An average John theorem ⋮ Nonpositive curvature is not coarsely universal
This page was built for publication: A spectral gap precludes low-dimensional embeddings