A spectral gap precludes low-dimensional embeddings

Assaf Naor

doi:10.4230/LIPIcs.SoCG.2017.50

A spectral gap precludes low-dimensional embeddings

Assaf Naor

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

We prove that there is a universal constant C > 0 with the following property. Suppose that n ∈ ℕ and that A = (a_ij) ∈ M_n(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of A by λ₂(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) ≳ n^c/^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)²/D² of Linial, London and Rabinovich, strengthens a theorem of Matoušek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.

Original language	English (US)
Title of host publication	33rd International Symposium on Computational Geometry, SoCG 2017
Editors	Matthew J. Katz, Boris Aronov
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	501-5016
Number of pages	4516
ISBN (Electronic)	9783959770385
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2017.50
State	Published - Jun 1 2017
Event	33rd International Symposium on Computational Geometry, SoCG 2017 - Brisbane, Australia Duration: Jul 4 2017 → Jul 7 2017

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	77
ISSN (Print)	1868-8969

Other

Other	33rd International Symposium on Computational Geometry, SoCG 2017
Country/Territory	Australia
City	Brisbane
Period	7/4/17 → 7/7/17

All Science Journal Classification (ASJC) codes

Software

Keywords

Complex interpolation
Dimensionality reduction
Expander graphs
Markov type
Metric embeddings
Nearest neighbor search
Nonlinear spectral gaps

Access to Document

10.4230/LIPIcs.SoCG.2017.50

Cite this

Naor, A. (2017). A spectral gap precludes low-dimensional embeddings. In M. J. Katz, & B. Aronov (Eds.), 33rd International Symposium on Computational Geometry, SoCG 2017 (pp. 501-5016). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 77). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2017.50

@inproceedings{b1c5618ce5f441fea0c1e511c67808b0,

title = "A spectral gap precludes low-dimensional embeddings",

abstract = "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{\v s}ek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.",

keywords = "Complex interpolation, Dimensionality reduction, Expander graphs, Markov type, Metric embeddings, Nearest neighbor search, Nonlinear spectral gaps",

author = "Assaf Naor",

note = "Publisher Copyright: {\textcopyright} Assaf Naor.; 33rd International Symposium on Computational Geometry, SoCG 2017 ; Conference date: 04-07-2017 Through 07-07-2017",

year = "2017",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2017.50",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "501--5016",

editor = "Katz, {Matthew J.} and Boris Aronov",

booktitle = "33rd International Symposium on Computational Geometry, SoCG 2017",

address = "Germany",

}

Naor, A 2017, A spectral gap precludes low-dimensional embeddings. in MJ Katz & B Aronov (eds), 33rd International Symposium on Computational Geometry, SoCG 2017. Leibniz International Proceedings in Informatics, LIPIcs, vol. 77, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 501-5016, 33rd International Symposium on Computational Geometry, SoCG 2017, Brisbane, Australia, 7/4/17. https://doi.org/10.4230/LIPIcs.SoCG.2017.50

A spectral gap precludes low-dimensional embeddings. / Naor, Assaf.
33rd International Symposium on Computational Geometry, SoCG 2017. ed. / Matthew J. Katz; Boris Aronov. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. p. 501-5016 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 77).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

A spectral gap precludes low-dimensional embeddings

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Cite this