Grothendieck inequality explained

In mathematics, the Grothendieck inequality states that there is a universal constant

K _{G} with the following property. If M_ij is an n × n (real or complex) matrix with| \sum _{i,j} M _{ij} s _{i} t _{j} | \le 1

for all (real or complex) numbers s_i, t_j of absolute value at most 1, then

| \sum _{i,j} M _{ij} \langle S _{i,} T _{j} \rangle | \le K _{G}

for all vectors S_i, T_j in the unit ball B(H) of a (real or complex) Hilbert space H, the constant

K _{G} being independent of n. For a fixed Hilbert space of dimension d, the smallest constant that satisfies this property for all n × n matrices is called a Grothendieck constant and denoted K _{G(d)} . In fact, there are two Grothendieck constants, K ^{R} _{G} (d) and K ^{C} _{G} (d) , depending on whether one works with real or complex numbers, respectively.^[1]

The Grothendieck inequality and Grothendieck constants are named after Alexander Grothendieck, who proved the existence of the constants in a paper published in 1953.

Motivation and the operator formulation

Let

A = (a _{ij} ) be an m x n matrix. Then A defines a linear operator between the normed spaces ( R ^{m,} \| ⋅ \| _{p)} and ( R ^{n,} \| ⋅ \| _{q)} for 1 \leq p, q \leq inf ty . The (p \to q) -norm of A is the quantity\| A \| _{p} = max _{x \in R ^{n} : \| x \| _{p} =1} \| Ax \| _{q.}

If

p = q , we denote the norm by \| A \| _{p} .

One can consider the following question: For what value of

p and q is \| A \| _{p} maximized? Since A is linear, then it suffices to consider p such that \{ x \in R ^{n} : \| x \| _{p} \leq 1 \} contains as many points as possible, and also q such that \| Ax \| _{q} is as large as possible. By comparing \| x \| _{p} for p = 1 , 2 , \ldots, inf ty , one sees that \| A \| _{infty} \geq \| A \| _{p} for all 1 \leq p, q \leq inf ty .

One way to compute

\| A \| _{infty} is by solving the following quadratic integer program:\begin{align} max & \sum _{i,} A _{ij} x _{i} y _{j} \ s.t. & (x, y) \in \{ -1 , 1 \} ^{m} \end{align}

To see this, note that

\sum _{i,} A _{ij} x _{i} y _{j} = \sum _{i} (Ay) _{i} x _{i} , and taking the maximum over x \in \{ -1 , 1 \} ^{m} gives \| Ay \| _{1} . Then taking the maximum over y \in \{ -1 , 1 \} ^{n} gives \| A \| _{infty} by the convexity of \{ x \in R ^{m} : \| x \| _{infty} = 1 \} and by the triangle inequality. This quadratic integer program can be relaxed to the following semidefinite program:\begin{align} max & \sum _{i,} A _{ij} \langle x ^{(i)} , y ^{(j)} \rangle \ s.t. & x ^{(1)} , \ldots, x ^{(m)} , y ^{(1)} , \ldots, y ^{(n)} areunitvectorsin ( R ^{d,} \| ⋅ \| _{2)} \end{align}

It is known that exactly computing

\| A \| _{p} for 1 \leq q < p \leq inf ty is NP-hard, while exacting computing \| A \| _{p} is NP-hard for p \not \in \{ 1 , 2 , inf ty \} .

One can then ask the following natural question: How well does an optimal solution to the semidefinite program approximate

\| A \| _{infty} ? The Grothendieck inequality provides an answer to this question: There exists a fixed constant C > 0 such that, for any m, n \geq 1 , for any m x n matrix A , and for any Hilbert space H ,max _{x ^{(i)} , y ^{(i)} \in H unitvectors} \sum _{i,} A _{ij} \left\langle x ^{(i)} , y ^{(j)} \right\rangle _{H} \leq C \| A \| _{infty} .

Bounds on the constants

The sequences

K ^{R} _{G} (d) and K ^{C} _{G} (d) are easily seen to be increasing, and Grothendieck's result states that they are bounded,^{[2] [3]} so they have limits.

Grothendieck proved that

1 . 57 ≈ (\pi)/(2) \leq K ^{R} _{G} \leq \operatorname{sinh} (\pi)/(2) ≈ 2 . 3 , where K ^{R} _{G} is defined to be \sup _{d} K ^{R} _{G} (d) .^[4]

^[5] improved the result by proving that

K ^{R} _{G} \le (\pi)/(2ln ( 1+ \sqrt{ 2) )} ≈ 1 . 7822 , conjecturing that the upper bound is tight. However, this conjecture was disproved by .^[6]

Grothendieck constant of order d

Boris Tsirelson showed that the Grothendieck constants

K ^{R} _{G} (d) play an essential role in the problem of quantum nonlocality: the Tsirelson bound of any full correlation bipartite Bell inequality for a quantum system of dimension d is upperbounded by K ^{R} _{G} ( 2 d ^{2)} .^{[7] [8]}

Lower bounds

Some historical data on best known lower bounds of

K ^{R} _{G} (d) is summarized in the following table.

d	Grothendieck, 1953	Krivine, 1979	Davie, 1984^[9]	Fishburn et al., 1994^[10]	Vértesi, 2008^[11]	Briët et al., 2011^[12]	Hua et al., 2015^[13]	Diviánszky et al., 2017^[14]	Designolle et al., 2023
2		\sqrt{ 2 } ≈ 1.41421
3					1.41724		1.41758	1.4359	1.4367
4					1.44521		1.44566	1.4841
5				(10)/(7) ≈ 1.42857	1.46007		1.46112
6							1.47017
7						1.46286	1.47583
8						1.47586	1.47972
9						1.48608
∞	(\pi)/(2) ≈ 1.57079		1.67696

Upper bounds

Some historical data on best known upper bounds of

K ^{R} _{G} (d) :

d	Grothendieck, 1953	Rietz, 1974^[15]	Krivine, 1979	Braverman et al., 2011	Hirsch et al., 2016^[16]	Designolle et al., 2023
2			\sqrt{ 2 } ≈ 1.41421
3			1.5163		1.4644	1.4546
4			(\pi)/(2) ≈ 1.5708
8			1.6641
∞	\operatorname{sinh} (\pi)/(2) ≈ 2.30130	2.261	(\pi)/(2ln ( 1+ \sqrt{ 2) )} ≈ 1.78221	(\pi)/(2ln ( 1+ \sqrt{ 2) )} - \varepsilon

Applications

Cut norm estimation

Given an

m x n real matrix A = (a _{ij} ) , the cut norm of A is defined by\| A \| _{\square} = max _{S} \left| \sum _{i} a _{ij} \right|.

The notion of cut norm is essential in designing efficient approximation algorithms for dense graphs and matrices. More generally, the definition of cut norm can be generalized for symmetric measurable functions

W : [ 0 , 1 ] ^{2} \to R so that the cut norm of W is defined by\| W \| _{\square} = \sup _{S,} \left| \int _{S} W \right|.

This generalized definition of cut norm is crucial in the study of the space of graphons, and the two definitions of cut norm can be linked via the adjacency matrix of a graph.

An application of the Grothendieck inequality is to give an efficient algorithm for approximating the cut norm of a given real matrix

A ; specifically, given an m x n real matrix, one can find a number \alpha such that\| A \| _{\square} \leq \alpha \leq C \| A \| _{\square,}

where

C is an absolute constant.^[17] This approximation algorithm uses semidefinite programming.

We give a sketch of this approximation algorithm. Let

B = (b _{ij} ) be (m + 1 ) x (n + 1 ) matrix defined by\begin{pmatrix} a _{11} & a _{12} & \ldots & a _{1n} & - \sum ^{n} _{k =1} a _{1k} \ a _{21} & a _{22} & \ldots & a _{2n} & - \sum ^{n} _{k =1} a _{2k} \ \vdots & \vdots & \ddots & \vdots & \vdots \ a _{m1} & a _{m2} & \ldots & a _{mn} & - \sum ^{n} _{k =1} a _{mk} \ - \sum ^{m} _{\ell =1} a _{\ell} & - \sum ^{m} _{\ell =1} a _{\ell} & \ldots & - \sum ^{m} _{\ell =1} a _{\ell} & \sum ^{n} _{k =1} \sum ^{m} _{\ell =1} a _{\ell} \end{pmatrix}.

One can verify that

\| A \| _{\square} = \| B \| _{\square} by observing, if S \in [m + 1 ], T \in [n + 1 ] form a maximizer for the cut norm of B , thenS ^{*} = \begin{cases} S, & if m + 1 \not \in S, \ {[m]} \setminus S, & otherwise , \end{cases} T ^{*} = \begin{cases} T, & if n + 1 \not \in T, \ {[n]} \setminus S, & otherwise , \end{cases}

form a maximizer for the cut norm of

A . Next, one can verify that \| B \| _{\square} = \| B \| _{infty} / 4 , where\| B \| _{infty} = max \left\{ \sum ^{m +1} _{i =1} \sum ^{n +1} _{j =1} b _{ij} \varepsilon _{i} \delta _{j} : \varepsilon _{1,} \ldots, \varepsilon _{m} \in \{ -1 , 1 \}, \delta _{1,} \ldots, \delta _{n} \in \{ -1 , 1 \} \right\}.

Although not important in this proof,

\| B \| _{infty} can be interpreted to be the norm of B when viewed as a linear operator from \ell ^{m} _{inf ty} to \ell ^{m} _{1} .

Now it suffices to design an efficient algorithm for approximating

\| A \| _{infty} . We consider the following semidefinite program:SDP (A) = max \left\{ \sum ^{m} _{i =1} \sum ^{n} _{j =1} a _{ij} \left\langle x _{i,} y _{j} \right\rangle : x _{1,} \ldots, x _{m,} y _{1,} \ldots, y _{n} \in S ^{n} \right\}.

Then

SDP (A) \geq \| A \| _{infty} . The Grothedieck inequality implies that SDP (A) \leq K ^{R} _{G} \| A \| _{infty} . Many algorithms (such as interior-point methods, first-order methods, the bundle method, the augmented Lagrangian method) are known to output the value of a semidefinite program up to an additive error \varepsilon in time that is polynomial in the program description size and log ( 1 /\varepsilon) .^[18] Therefore, one can output \alpha = SDP (B) which satisfies\| A \| _{\square} \leq \alpha \leq C \| A \| _{\square} with C = K ^{R} _{G} .

Szemerédi's regularity lemma

Szemerédi's regularity lemma is a useful tool in graph theory, asserting (informally) that any graph can be partitioned into a controlled number of pieces that interact with each other in a pseudorandom way. Another application of the Grothendieck inequality is to produce a partition of the vertex set that satisfies the conclusion of Szemerédi's regularity lemma, via the cut norm estimation algorithm, in time that is polynomial in the upper bound of Szemerédi's regular partition size but independent of the number of vertices in the graph.^[19]

It turns out that the main "bottleneck" of constructing a Szemeredi's regular partition in polynomial time is to determine in polynomial time whether or not a given pair

(X, Y) is close to being \varepsilon -regular, meaning that for all S \subset X, T \subset Y with |S| \geq \varepsilon |X|, |T| \geq \varepsilon |Y| , we have\left| (e(S, T))/(|S||T|) - (e(X, Y))/(|X||Y|) \right| \leq \varepsilon,

where

e(X', Y') = |\{ (u, v) \in X' x Y' : uv \in E \}| for all X', Y' \subset V and V, E are the vertex and edge sets of the graph, respectively. To that end, we construct an n x n matrix A = (a _{xy} ) _{(x,} , where n = |V| , defined bya _{xy} = \begin{cases} 1 - (e(X, Y))/(|X||Y|) , & if xy \in E, \ - (e(X, Y))/(|X||Y|) , & otherwise . \end{cases}

Then for all

S \subset X, T \subset Y ,\left| \sum _{x} a _{xy} \right| = |S||T| \left| (e(S, T))/(|S||T|) - (e(X, Y))/(|X||Y|) \right|.

Hence, if

(X, Y) is not \varepsilon -regular, then \| A \| _{\square} \geq \varepsilon ^{3} n ^{2} . It follows that using the cut norm approximation algorithm together with the rounding technique, one can find in polynomial time S \subset X, T \subset Y such thatmin \left\{ n|S|, n|T|, n ^{2} \left| (e(S, T))/(|S||T|) - (e(X, Y))/(|X||Y|) \right| \right\} \geq \left|\sum _{x} a _{xy} \right| \geq (1)/(K ^{R} _{G}) \varepsilon ^{3} n ^{2} \geq (1)/(2) \varepsilon ^{3} n ^{2.}

Then the algorithm for producing a Szemerédi's regular partition follows from the constructive argument of Alon et al.^[20]

Variants of the Grothendieck inequality

Grothendieck inequality of a graph

The Grothendieck inequality of a graph states that for each

n \in N and for each graph G = (\{ 1 , \ldots, n \}, E) without self loops, there exists a universal constant K > 0 such that every n x n matrix A = (a _{ij} ) satisfies thatmax _{x _{1,} \ldots, x _{n} \in S ^{n}} \sum _{ij} a _{ij} \left\langle x _{i,} x _{j} \right\rangle \leq K max _{\varepsilon _{1,} \ldots, \varepsilon _{n} \in \{ -1 , 1 \} } \sum_ a_ \varepsilon_1 \varepsilon_n.^[21]

The Grothendieck constant of a graph

G , denoted K(G) , is defined to be the smallest constant K that satisfies the above property.

The Grothendieck inequality of a graph is an extension of the Grothendieck inequality because the former inequality is the special case of the latter inequality when

G is a bipartite graph with two copies of \{ 1 , \ldots, n \} as its bipartition classes. Thus,K _{G} = \sup _{n} \{ K(G) : G isan n -vertexbipartitegraph \}.

For

G = K _{n} , the n -vertex complete graph, the Grothendieck inequality of G becomesmax _{x _{1,} \ldots, x _{n} \in S ^{n}} \sum _{i,} , i ≠ j} a _{ij} \left\langle x _{i,} x _{j} \right\rangle \leq K(K _{n)} max _{\varepsilon _{1,} \ldots, \varepsilon _{n} \in \{ -1 , 1 \} } \sum_ a_ \varepsilon_i \varepsilon_j.

It turns out that

K(K _{n)} \asymp log n . On one hand, we have K(K _{n)} \lesssim log n .^{[22] [23] [24]} Indeed, the following inequality is true for any n x n matrix A = (a _{ij} ) , which implies that K(K _{n)} \lesssim log n by the Cauchy-Schwarz inequality:max _{x _{1,} \ldots, x _{n} \in S ^{n}} \sum _{i,} , i ≠ j} a _{ij} \left\langle x _{i,} x _{j} \right\rangle \leq log \left( (\sum _{i})/(\sum) _{j} \setminus \{ i \}} |a _{ij} |}{\sqrt{\sum _{i} } \sum_ a_^2}}\right) \max_ \sum_ a_ \varepsilon_1 \varepsilon_n.

On the other hand, the matching lower bound

K(K _{n)} \gtrsim log n is due to Alon, Makarychev, Makarychev and Naor in 2006.

The Grothendieck inequality

K(G) of a graph G depends upon the structure of G . It is known thatlog \omega \lesssim K(G) \lesssim log \vartheta,

and

K(G) \leq (\pi)/(2log \left( (1+ \sqrt{(\vartheta -1 ) ^{2} +1)/()) {\vartheta - 1 }\right)}, ^[25]

where

\omega is the clique number of G , i.e., the largest k \in \{ 2 , \ldots, n \} such that there exists S \subset \{ 1 , \ldots, n \} with |S| = k such that ij \in E for all distinct i, j \in S , and\vartheta = min \left\{ max _{i} } \frac : x_1, \ldots, x_n, y \in S^n, \left\langle x_i, x_j \right\rangle = 0 \;\forall ij \in E \right\}.

The parameter

\vartheta is known as the Lovász theta function of the complement of G .^{[26] [27]}

L^p Grothendieck inequality

In the application of the Grothendieck inequality for approximating the cut norm, we have seen that the Grothendieck inequality answers the following question: How well does an optimal solution to the semidefinite program

SDP (A) approximate \| A \| _{infty} , which can be viewed as an optimization problem over the unit cube? More generally, we can ask similar questions over convex bodies other than the unit cube.

For instance, the following inequality is due to Naor and Schechtman^[28] and independently due to Guruswami et al:^[29] For every

n x n matrix A = (a _{ij} ) and every p \geq 2 ,max _{x _{1 ,} \ldots, x _{n} \in R ^{n,} \sum ^{n} _{k =1} \| x _{k} \| ^{p} _{2} \leq 1} \sum ^{n} _{i =1} \sum ^{n} _{j =1} a _{ij} \left\langle x _{i,} x _{j} \right\rangle \leq \gamma ^{2} _{p} max _{t _{1 ,} \ldots, t _{n} \in R, \sum ^{n} _{k =1} | t _{k} | ^{p} \leq 1} \sum ^{n} _{i =1} \sum ^{n} _{j =1} a _{ij} t _{i} t _{j,}

where

\gamma _{p} = \sqrt{ 2 } \left( (\Gamma((p +1 )/ 2 ))/(\sqrt{\pi) }\right)^.

The constant

\gamma ^{2} _{p} is sharp in the inequality. Stirling's formula implies that \gamma ^{2} _{p} = p/e + O( 1 ) as p \to inf ty .

See also

• Pisier–Ringrose inequality

External links

• (NB: the historical part is not exact there.)

Notes and References

1. .
2. .
3. .
4. .
5. .
6. .
7. Boris Tsirelson . Quantum analogues of the Bell inequalities. The case of two spatially separated domains . Journal of Soviet Mathematics . 1987 . 36 . 4 . 557–570 . 10.1007/BF01663472 . 119363229 .
8. .
9. .
10. .
11. .
12. .
13. .
14. .
15. .
16. .
17. Alon. Noga. Naor. Assaf. January 2006. Approximating the Cut-Norm via Grothendieck's Inequality. SIAM Journal on Computing. en. 35. 4. 787–803. 10.1137/S0097539704441629. 0097-5397.
18. Book: P., Boyd, Stephen. Convex optimization. 2011. Cambridge Univ. Pr. 978-0-521-83378-3. 767754283.
19. Khot. Subhash. Naor. Assaf. 2012-04-25. Grothendieck-Type Inequalities in Combinatorial Optimization. Communications on Pure and Applied Mathematics. 65. 7. 992–1035. 10.1002/cpa.21398. 1108.2464 . 3175317 . 0010-3640.
20. Book: Alon, N.. Proceedings., 33rd Annual Symposium on Foundations of Computer Science . The algorithmic aspects of the regularity lemma . 1992. http://dx.doi.org/10.1109/sfcs.1992.267804. 473–481 . IEEE. 10.1109/sfcs.1992.267804. 0-8186-2900-2 . 2222009 .
21. Alon. Noga. Makarychev. Konstantin. Makarychev. Yury. Naor. Assaf. 2006-03-01. Quadratic forms on graphs. Inventiones Mathematicae. en. 163. 3. 499–522. 10.1007/s00222-005-0465-9. 1432-1297. subscription.
22. Nemirovski. A.. Roos. C.. Terlaky. T.. 1999-12-01. On maximization of quadratic form over intersection of ellipsoids with common center. Mathematical Programming. en. 86. 3. 463–473. 10.1007/s101070050100. 2988923 . 1436-4646.
23. Book: Megretski, Alexandre. Systems, Approximation, Singular Integral Operators, and Related Topics . Relaxations of Quadratic Programs in Operator Theory and System Analysis . 2001. Borichev. Alexander A.. Nikolski. Nikolai K.. https://link.springer.com/chapter/10.1007%2F978-3-0348-8362-7_15. Operator Theory: Advances and Applications. en. Basel. Birkhäuser. 365–392. 10.1007/978-3-0348-8362-7_15. 978-3-0348-8362-7.
24. Book: Charikar. M.. Wirth. A.. 45th Annual IEEE Symposium on Foundations of Computer Science . Maximizing Quadratic Programs: Extending Grothendieck's Inequality . http://dx.doi.org/10.1109/focs.2004.39. 2004 . 54–60 . IEEE. 10.1109/focs.2004.39. 0-7695-2228-9 . 7036076 .
25. Briet. Jop. de Oliveira Filho. Fernando Mario. Vallentin. Frank. 2014. Grothendieck Inequalities for Semidefinite Programs with Rank Constraint. Theory of Computing. en. 10. 1. 77–105. 10.4086/toc.2014.v010a004. 1004947 . 1557-2862. free. 1011.1754.
26. Lovasz. L.. January 1979. On the Shannon capacity of a graph. IEEE Transactions on Information Theory. en. 25. 1. 1–7. 10.1109/TIT.1979.1055985. 0018-9448.
27. Karger. David. Motwani. Rajeev. Sudan. Madhu. 1998-03-01. Approximate graph coloring by semidefinite programming. Journal of the ACM. 45. 2. 246–265. 10.1145/274787.274791. 0004-5411.
28. Naor, A., & Schechtman, G. (2009). An approximation scheme for quadratic form maximization on convex bodies. Manuscript, 1(4), 8.
29. Guruswami. Venkatesan. Raghavendra. Prasad. Saket. Rishi. Wu. Yi. 2012-01-17. Bypassing UGC from some Optimal Geometric Inapproximability Results. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. 699–717 . Philadelphia, PA. Society for Industrial and Applied Mathematics. 10.1137/1.9781611973099.58. 978-1-61197-210-8 .