TY - GEN
T1 - A spectral gap precludes low-dimensional embeddings
AU - Naor, Assaf
N1 - Publisher Copyright:
© Assaf Naor.
PY - 2017/6/1
Y1 - 2017/6/1
N2 - We prove that there is a universal constant C > 0 with the following property. Suppose that n ∈ ℕ and that A = (aij) ∈ Mn(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of A by λ2(A). Then for any finite-dimensional normed space (X, ⊥ · ⊥) we have (Equation presented) It follows that if an n-vertex O(1)-expander embeds with average distortion D ≧ 1 into X, then necessarily dim(X) ≳ nc/D for some universal constant c > 0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X) ≳ (log n)2/D2 of Linial, London and Rabinovich, strengthens a theorem of Matoušek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.
AB - We prove that there is a universal constant C > 0 with the following property. Suppose that n ∈ ℕ and that A = (aij) ∈ Mn(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of A by λ2(A). Then for any finite-dimensional normed space (X, ⊥ · ⊥) we have (Equation presented) It follows that if an n-vertex O(1)-expander embeds with average distortion D ≧ 1 into X, then necessarily dim(X) ≳ nc/D for some universal constant c > 0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X) ≳ (log n)2/D2 of Linial, London and Rabinovich, strengthens a theorem of Matoušek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.
KW - Complex interpolation
KW - Dimensionality reduction
KW - Expander graphs
KW - Markov type
KW - Metric embeddings
KW - Nearest neighbor search
KW - Nonlinear spectral gaps
UR - http://www.scopus.com/inward/record.url?scp=85024373776&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024373776&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2017.50
DO - 10.4230/LIPIcs.SoCG.2017.50
M3 - Conference contribution
AN - SCOPUS:85024373776
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 501
EP - 5016
BT - 33rd International Symposium on Computational Geometry, SoCG 2017
A2 - Katz, Matthew J.
A2 - Aronov, Boris
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd International Symposium on Computational Geometry, SoCG 2017
Y2 - 4 July 2017 through 7 July 2017
ER -