TY - GEN
T1 - Towards a calculus for non-linear spectral gaps
AU - Mendel, Manor
AU - Naor, Assaf
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
PY - 2010
Y1 - 2010
N2 - Given a finite regular graph G = (V, E) and a metric space (X, d X), let γ+(G, X) denote the smallest constant γ+ > 0 such that for all f, g : V → X we have: 1/|V|2 ∑ x,y∈V dx(f(x),g(y))2 ≤ γ+/|E| ∑ xy∈E dx(f(x),g(y))2. In the special case X = R this quantity coincides with the reciprocal of the absolute spectral gap of G, but for other geometries the parameter γ+(G, X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently. Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of super-expander - a family of bounded-degree graphs Gi = (V i, Ei), with limi→∞ |Vi| = ∞, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of Gi in any uniformly convex Banach space is Ω(log |Vi|), which is the worst possible behavior due to Bourgain's embedding theorem [3]. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue [11]. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson [28]. We show that non-linear spectral gaps behave submultiplicatively under zigzag products - a fact that amounts to a simple iteration of the inequality above. This yields as a special case a very simple (linear algebra free) proof of the Reingold-Vadhan-Wigderson theorem which states that zigzag products preserve the property of having an absolute spectral gap (with quantitative control on the size of the gap). The zigzag iteration of Reingold-Vadhan-Wigderson also involves taking graph powers, which is trivial to analyze in the classical "linear" setting. In our work, the behavior of non-linear spectral gaps under graph powers becomes a major geometric obstacle, and we show that for uniformly convex normed spaces there exists a satisfactory substitute for spectral calculus which makes sense in the non-linear setting. These facts, in conjunction with a variant of Ball's notion of Markov cotype and a Fourier analytic proof of the existence of appropriate "base graphs", are shown to imply that Reingold-Vadhan-Wigderson type constructions can be carried out in the non-linear setting.
AB - Given a finite regular graph G = (V, E) and a metric space (X, d X), let γ+(G, X) denote the smallest constant γ+ > 0 such that for all f, g : V → X we have: 1/|V|2 ∑ x,y∈V dx(f(x),g(y))2 ≤ γ+/|E| ∑ xy∈E dx(f(x),g(y))2. In the special case X = R this quantity coincides with the reciprocal of the absolute spectral gap of G, but for other geometries the parameter γ+(G, X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently. Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of super-expander - a family of bounded-degree graphs Gi = (V i, Ei), with limi→∞ |Vi| = ∞, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of Gi in any uniformly convex Banach space is Ω(log |Vi|), which is the worst possible behavior due to Bourgain's embedding theorem [3]. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue [11]. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson [28]. We show that non-linear spectral gaps behave submultiplicatively under zigzag products - a fact that amounts to a simple iteration of the inequality above. This yields as a special case a very simple (linear algebra free) proof of the Reingold-Vadhan-Wigderson theorem which states that zigzag products preserve the property of having an absolute spectral gap (with quantitative control on the size of the gap). The zigzag iteration of Reingold-Vadhan-Wigderson also involves taking graph powers, which is trivial to analyze in the classical "linear" setting. In our work, the behavior of non-linear spectral gaps under graph powers becomes a major geometric obstacle, and we show that for uniformly convex normed spaces there exists a satisfactory substitute for spectral calculus which makes sense in the non-linear setting. These facts, in conjunction with a variant of Ball's notion of Markov cotype and a Fourier analytic proof of the existence of appropriate "base graphs", are shown to imply that Reingold-Vadhan-Wigderson type constructions can be carried out in the non-linear setting.
UR - http://www.scopus.com/inward/record.url?scp=77951674750&partnerID=8YFLogxK
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:77951674750
SN - 9780898717013
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 236
EP - 255
BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 17 January 2010 through 19 January 2010
ER -