Grothendieck inequality
Let formula_8 be an formula_9 matrix. Then formula_10 defines a linear operator between the normed spaces formula_11 and formula_12 for formula_13. The formula_14-norm of formula_10 is the quantity
formula_16
If formula_17, we denote the norm by formula_18. One can consider the following question: For what value of formula_19 and formula_20 is formula_21 maximized? Since formula_10 is linear, then it suffices to consider formula_19 such that formula_24 contains as many points as possible, and also formula_20 such that formula_26 is as large as possible. By comparing formula_27 for formula_28, one sees that formula_29 for all formula_13. One way to compute formula_31 is by solving the following quadratic integer program:
formula_32
To see this, note that formula_33, and taking the maximum over formula_34 gives formula_35. Then taking the maximum over formula_36 gives formula_31 by the convexity of formula_38 and by the triangle inequality. This quadratic integer program can be relaxed to the following semidefinite program:
formula_39
It is known that exactly computing formula_21 for formula_41 is NP-hard, while exacting computing formula_18 is NP-hard for formula_43. One can then ask the following natural question: How well does an optimal solution to the semidefinite program approximate formula_31? The Grothendieck inequality provides an answer to this question: There exists a fixed constant formula_45 such that, for any formula_46, for any formula_9 matrix formula_10, and for any Hilbert space formula_49,
formula_50 The sequences formula_6 and formula_7 are easily seen to be increasing, and Grothendieck's result states that they are bounded, so they have limits. Grothendieck proved that formula_53 where formula_54 is defined to be formula_55. improved the result by proving that formula_56, conjecturing that the upper bound is tight. However, this conjecture was disproved by . Boris Tsirelson showed that the Grothendieck constants formula_6 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 formula_58. Some historical data on best known lower bounds of formula_6 is summarized in the following table. Some historical data on best known upper bounds of formula_6: Given an formula_9 real matrix formula_8, the cut norm of formula_10 is defined by
formula_64
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 formula_65 so that the cut norm of formula_66 is defined by
formula_67
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 formula_10; specifically, given an formula_9 real matrix, one can find a number formula_70 such that
formula_71
where formula_72 is an absolute constant. This approximation algorithm uses semidefinite programming. We give a sketch of this approximation algorithm. Let formula_73 be formula_74 matrix defined by
formula_75
One can verify that formula_76 by observing, if formula_77 form a maximizer for the cut norm of formula_78, then
formula_79
form a maximizer for the cut norm of formula_10. Next, one can verify that formula_81, where
formula_82
Although not important in this proof, formula_83 can be interpreted to be the norm of formula_78 when viewed as a linear operator from formula_85 to formula_86.
Now it suffices to design an efficient algorithm for approximating formula_31. We consider the following semidefinite program:
formula_88
Then formula_89. The Grothedieck inequality implies that formula_90. 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 formula_91 in time that is polynomial in the program description size and formula_92. Therefore, one can output formula_93 which satisfies
formula_94 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. 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 formula_95 is close to being formula_91-regular, meaning that for all formula_97 with formula_98, we have
formula_99
where formula_100 for all formula_101 and formula_102 are the vertex and edge sets of the graph, respectively. To that end, we construct an formula_103 matrix formula_104, where formula_105, defined by
formula_106
Then for all formula_97,
formula_108
Hence, if formula_95 is not formula_91-regular, then formula_111. It follows that using the cut norm approximation algorithm together with the rounding technique, one can find in polynomial time formula_97 such that
formula_113
Then the algorithm for producing a Szemerédi's regular partition follows from the constructive argument of Alon et al. The Grothendieck inequality of a graph states that for each formula_114 and for each graph formula_115 without self loops, there exists a universal constant formula_116 such that every formula_103 matrix formula_8 satisfies that
formula_119
The Grothendieck constant of a graph formula_120, denoted formula_121, is defined to be the smallest constant formula_122 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 formula_120 is a bipartite graph with two copies of formula_124 as its bipartition classes. Thus,
formula_125
For formula_126, the formula_127-vertex complete graph, the Grothendieck inequality of formula_120 becomes
formula_129
It turns out that formula_130. On one hand, we have formula_131. Indeed, the following inequality is true for any formula_103 matrix formula_8, which implies that formula_131 by the Cauchy-Schwarz inequality:
formula_135
On the other hand, the matching lower bound formula_136 is due to Alon, Makarychev, Makarychev and Naor in 2006. The Grothendieck inequality formula_121 of a graph formula_120 depends upon the structure of formula_120. It is known that
formula_140
and
formula_141
where formula_142 is the clique number of formula_120, i.e., the largest formula_144 such that there exists formula_145 with formula_146 such that formula_147 for all distinct formula_148, and
formula_149
The parameter formula_150 is known as the Lovász theta function of the complement of formula_120. 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 formula_152 approximate formula_31, 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 and independently due to Guruswami et al: For every formula_103 matrix formula_8 and every formula_156,
formula_157
where
formula_158
The constant formula_159 is sharp in the inequality. Stirling's formula implies that formula_160 as formula_161.
Applications
In fact, there are two Grothendieck constants, formula_6 and formula_7, depending on whether one works with real or complex numbers, respectively.