Lecture 15: Grothendieck’s Inequality
The kernel trick, the isonormal process, and Krivine’s bound
Lecture 14 ended with a question. The semidefinite relaxation of a quadratic problem over the cube replaces signs by unit vectors in a Hilbert space, and rounding by a random hyperplane turns the inner products \(\langle X_i,X_j\rangle\) into \(\frac2\pi\arcsin\langle X_i,X_j\rangle\). For max-cut the nonlinearity cost a factor \(0.878\). For a general bilinear form the nonlinearity has no sign to work with, and it is not clear that the relaxation is within any constant factor of the original problem. Grothendieck’s inequality says that it is. The proof given here, due to Krivine, removes the nonlinearity outright: it replaces the vectors by new vectors in a larger Hilbert space whose inner products have exactly the arcsine that the rounding produces. The Gaussian vector used to round then lives in an infinite-dimensional space, and it is the isonormal process of Lecture 10.
1 The inequality
Theorem 1 (Grothendieck’s inequality) There is an absolute constant \(K\) with the following property. Let \(A=(A_{ij})\) be a real \(m\times n\) matrix such that \[ \Big|\sum_{i,j}A_{ij}x_iy_j\Big|\leq1 \qquad\text{for all }x\in\{-1,1\}^m,\ y\in\{-1,1\}^n . \] Then for every real Hilbert space \(H\) and all unit vectors \(u_1,\ldots,u_m,v_1,\ldots,v_n\in H\), \[ \Big|\sum_{i,j}A_{ij}\langle u_i,v_j\rangle\Big|\leq K . \]
The smallest constant for which this holds is Grothendieck’s constant \(K_G\). Its exact value is unknown. Krivine’s argument below gives \[ K_G\leq\frac\pi{2\log(1+\sqrt2)}\approx1.782 , \] and it is known that \(K_G\geq1.676\) and that Krivine’s bound is not sharp.
The inequality would be trivial if \(K\) were allowed to depend on \(A\): the constant \(\sum_{ij}|A_{ij}|\) works, since \(|\langle u_i,v_j\rangle|\leq1\). The content is that one constant serves for all matrices and all dimensions. Before the proof, three reformulations.
Lemma 1 (Equivalent forms)
- The hypothesis is equivalent to \(\big|\sum_{ij}A_{ij}x_iy_j\big|\leq\max_i|x_i|\cdot\max_j|y_j|\) for all real \(x\in\mathbb R^m\), \(y\in\mathbb R^n\).
- The conclusion is equivalent to \(\big|\sum_{ij}A_{ij}\langle u_i,v_j\rangle\big|\leq K\max_i\|u_i\|\cdot\max_j\|v_j\|\) for all vectors \(u_i,v_j\in H\), not necessarily of unit length.
- It suffices to prove the conclusion for \(H=\mathbb R^{m+n}\).
By homogeneity it suffices to consider \(x\in[-1,1]^m\) and \(y\in[-1,1]^n\). For fixed \(y\), the map \(x\mapsto\sum_{ij}A_{ij}x_iy_j\) is linear, so its maximum and minimum over the cube \([-1,1]^m\) are attained at vertices, that is, at \(x\in\{-1,1\}^m\). Repeating the argument in \(y\) reduces to \(y\in\{-1,1\}^n\).
By homogeneity, suppose \(\|u_i\|\leq1\) and \(\|v_j\|\leq1\). Enlarge \(H\) to \(H\oplus\mathbb R^m\) with orthonormal vectors \(e'_1,\ldots,e'_m\) orthogonal to \(H\), and set \[ u'_i:=u_i\oplus\sqrt{1-\|u_i\|^2}\,e'_i, \qquad v'_j:=v_j\oplus0 . \] Then \(\|u'_i\|=1\), \(\langle u'_i,v'_j\rangle=\langle u_i,v_j\rangle\), and the same device applied to the \(v_j\) with a further \(\mathbb R^n\) makes all vectors unit without changing any of the inner products.
The vectors \(u_i,v_j\) span a subspace of \(H\) of dimension at most \(m+n\), which is isometric to a subspace of \(\mathbb R^{m+n}\), and the inequality only involves inner products among them.
2 What it says about semidefinite relaxations
Define the bilinear integer and relaxed problems \[ \mathrm{INT}_{\mathrm{bil}}(A):=\max_{x\in\{\pm1\}^m,\ y\in\{\pm1\}^n}\sum_{ij}A_{ij}x_iy_j, \qquad \mathrm{SDP}_{\mathrm{bil}}(A):=\max_{\substack{u_i,v_j\in S^{m+n-1}}}\sum_{ij}A_{ij}\langle u_i,v_j\rangle . \] Both maxima are nonnegative, since replacing \(x\) by \(-x\) flips the sign, and the second is a semidefinite program by the Gram-matrix lemma of Lecture 14, applied to the \(m+n\) vectors together. The integer value \(\mathrm{INT}_{\mathrm{bil}}(A)\) is the cut norm of \(A\), up to a constant factor, and computing it is NP-hard.
Corollary 1 (The bilinear relaxation is tight up to \(K_G\)) For every real \(m\times n\) matrix \(A\), \[ \mathrm{INT}_{\mathrm{bil}}(A)\leq\mathrm{SDP}_{\mathrm{bil}}(A)\leq K_G\cdot\mathrm{INT}_{\mathrm{bil}}(A). \]
The first inequality takes \(u_i=x_ie_1\), \(v_j=y_je_1\). For the second, if \(\mathrm{INT}_{\mathrm{bil}}(A)=0\) then \(A=0\) and there is nothing to prove; otherwise apply Theorem 1 to \(A/\mathrm{INT}_{\mathrm{bil}}(A)\), which satisfies the hypothesis.
So the bilinear relaxation computes the cut norm to within a factor \(K_G<1.79\) in polynomial time, and with more work the relaxed solution can be rounded to sign vectors achieving a constant fraction of the optimum (Alon and Naor 2006). This is what the hyperplane rounding of Lecture 14 could not do for general coefficients.
The symmetric problem of Lecture 14 is different. For a symmetric \(A\) with zero diagonal, polarization relates the two: \[ \langle Ax,y\rangle=\langle Au,u\rangle-\langle Av,v\rangle, \qquad u=\frac{x+y}2,\ v=\frac{x-y}2 . \] For \(x,y\in\{-1,1\}^n\) the vectors \(u,v\) lie in \([-1,1]^n\), and a quadratic form with zero diagonal is linear in each variable separately, so its maximum and minimum over \([-1,1]^n\) are attained on the cube. Hence \(\mathrm{INT}_{\mathrm{bil}}(A)\leq\mathrm{INT}(A)+\mathrm{INT}(-A)\leq2\max_x|\langle Ax,x\rangle|\), and since the symmetric relaxation is the bilinear one restricted to \(u_i=v_i\), \[ \mathrm{SDP}(A)\leq\mathrm{SDP}_{\mathrm{bil}}(A)\leq2K_G\max_{x\in\{\pm1\}^n}|\langle Ax,x\rangle| . \] The absolute value cannot be removed. Alon, Makarychev, Makarychev and Naor (Alon et al. 2006) showed that the ratio \(\mathrm{SDP}(A)/\mathrm{INT}(A)\) can be as large as \(c\log n\) for symmetric \(A\) with zero diagonal, and that \(C\log n\) is the worst case. So the constant-factor guarantee is a genuinely bilinear phenomenon: letting \(x\) and \(y\) vary independently is what makes the relaxation tight. For max-cut the issue does not arise, because the Goemans–Williamson analysis works directly with the objective \(1-\langle X_i,X_j\rangle\) and never needs a comparison of \(\mathrm{SDP}(A)\) with \(\mathrm{INT}(A)\).
3 Krivine’s proof
By Lemma 1 we may assume \(H=\mathbb R^d\) with \(d=m+n\) and all \(u_i,v_j\) of unit length. The proof has two ideas, which the handwritten notes label as follows.
Idea 1. Find a Hilbert space \(\widehat H\) and maps \(\Phi,\Psi\) from the unit sphere of \(H\) to the unit sphere of \(\widehat H\) such that \[ \frac2\pi\arcsin\big\langle\Phi(u),\Psi(v)\big\rangle=\beta\langle u,v\rangle \qquad\text{for all unit }u,v\in H, \tag{1}\] for some constant \(\beta>0\).
Idea 2. Round with the isonormal process on \(\widehat H\). Grothendieck’s identity turns the left side of Equation 1 into an expectation of a product of signs, and the hypothesis on \(A\) bounds the expectation pointwise.
We carry out Idea 2 first, assuming Idea 1, and then construct \(\Phi\) and \(\Psi\).
Let \(\Phi,\Psi,\beta\) be as in Equation 1, and let \(g\) be the isonormal process on \(\widehat H\) from Lecture 10. For unit vectors \(h,h'\in\widehat H\), the pair \((g(h),g(h'))\) is centered Gaussian with unit variances and covariance \(\langle h,h'\rangle\), which is also the law of \((\langle\gamma,a\rangle,\langle\gamma,b\rangle)\) for \(\gamma\sim N(0,I_2)\) and unit \(a,b\in\mathbb R^2\) with \(\langle a,b\rangle=\langle h,h'\rangle\). Grothendieck’s identity of Lecture 14 depends only on this joint law, so \[ \mathbb E\operatorname{sgn}g(h)\operatorname{sgn}g(h')=\frac2\pi\arcsin\langle h,h'\rangle . \] Apply this with \(h=\Phi(u_i)\) and \(h'=\Psi(v_j)\), and use Equation 1: \[ \sum_{ij}A_{ij}\langle u_i,v_j\rangle =\frac1\beta\sum_{ij}A_{ij}\,\frac2\pi\arcsin\langle\Phi(u_i),\Psi(v_j)\rangle =\frac1\beta\,\mathbb E\Big[\sum_{ij}A_{ij}\,\operatorname{sgn}g(\Phi(u_i))\operatorname{sgn}g(\Psi(v_j))\Big]. \] For every outcome, \(x_i:=\operatorname{sgn}g(\Phi(u_i))\) and \(y_j:=\operatorname{sgn}g(\Psi(v_j))\) are sign vectors, so the bracket is at most \(1\) in absolute value by hypothesis. Hence \(\big|\sum_{ij}A_{ij}\langle u_i,v_j\rangle\big|\leq1/\beta\), which is the theorem with \(K=1/\beta\).
Note where the isonormal process earned its keep. The vectors \(\Phi(u_i)\) and \(\Psi(v_j)\) will live in an infinite-dimensional space, and the Gaussian process indexed by that space is exactly what makes “round with a random hyperplane” meaningful there. Since only finitely many vectors are involved, one could restrict to their span and use an ordinary Gaussian vector; the isonormal process simply avoids having to say so.
3.1 The kernel trick
The construction behind Idea 1 represents a nonlinear function of an inner product as a linear inner product in a bigger space. For \(H=\mathbb R^d\) and \(k\geq1\), the \(k\)-th tensor power of a vector \(u\in\mathbb R^d\) is the array \[ u^{\otimes k}:=\big(u_{i_1}u_{i_2}\cdots u_{i_k}\big)_{1\leq i_1,\ldots,i_k\leq d}\in\mathbb R^{d^k}, \] and with the standard inner product on \(\mathbb R^{d^k}\), \[ \langle u^{\otimes k},v^{\otimes k}\rangle =\sum_{i_1,\ldots,i_k}\prod_{\ell=1}^ku_{i_\ell}v_{i_\ell} =\Big(\sum_iu_iv_i\Big)^k=\langle u,v\rangle^k . \tag{2}\] So the monomial \(t\mapsto t^k\) is realized as an inner product in \(\mathbb R^{d^k}\). Sums of monomials are realized in direct sums of these spaces. For Hilbert spaces \(H_1,H_2,\ldots\) the direct sum \(\bigoplus_kH_k\) is the space of sequences \((h_k)_k\) with \(h_k\in H_k\) and \(\sum_k\|h_k\|^2<\infty\), with inner product \(\langle(h_k),(h'_k)\rangle=\sum_k\langle h_k,h'_k\rangle\); it is a separable Hilbert space when each \(H_k\) is.
Lemma 2 (The kernel trick) Let \(f(t)=\sum_{k\geq1}a_kt^k\) be a power series with \(\sum_k|a_k|\leq1\). Let \(\widehat H:=\bigoplus_{k\geq1}\mathbb R^{d^k}\) and define, for \(u,v\in\mathbb R^d\) with \(\|u\|,\|v\|\leq1\), \[ \Phi(u):=\big(\operatorname{sgn}(a_k)\sqrt{|a_k|}\,u^{\otimes k}\big)_{k\geq1}, \qquad \Psi(v):=\big(\sqrt{|a_k|}\,v^{\otimes k}\big)_{k\geq1}. \] Then \(\Phi(u),\Psi(v)\in\widehat H\), and \[ \langle\Phi(u),\Psi(v)\rangle=f(\langle u,v\rangle), \qquad \|\Phi(u)\|^2=\|\Psi(u)\|^2=\sum_{k\geq1}|a_k|\,\|u\|^{2k}. \] In particular \(\Phi\) and \(\Psi\) map unit vectors to vectors of norm \(\big(\sum_k|a_k|\big)^{1/2}\leq1\), with equality when \(\sum_k|a_k|=1\).
By Equation 2, \(\|u^{\otimes k}\|^2=\|u\|^{2k}\leq1\), so \(\sum_k|a_k|\|u\|^{2k}\leq\sum_k|a_k|<\infty\) and \(\Phi(u)\in\widehat H\); likewise for \(\Psi\). The inner product is \[ \langle\Phi(u),\Psi(v)\rangle=\sum_k\operatorname{sgn}(a_k)|a_k|\langle u^{\otimes k},v^{\otimes k}\rangle =\sum_ka_k\langle u,v\rangle^k=f(\langle u,v\rangle), \] the series converging absolutely since \(|\langle u,v\rangle|\leq1\). The norms are computed the same way with \(u=v\).
The signs of the coefficients are placed on \(\Phi\) only. This is why two different maps are needed: a single map \(\Phi=\Psi\) would represent only series with nonnegative coefficients, and the function we need has coefficients of both signs.
3.2 Krivine’s choice of \(f\)
Identity Equation 1 asks for \[ \langle\Phi(u),\Psi(v)\rangle=\sin\Big(\frac{\pi\beta}2\langle u,v\rangle\Big), \] so we take \(f(t)=\sin(ct)\) with \(c=\pi\beta/2\). Its power series is \[ \sin(ct)=\sum_{k\geq0}\frac{(-1)^kc^{2k+1}}{(2k+1)!}\,t^{2k+1}, \qquad \sum_k|a_k|=\sum_{k\geq0}\frac{c^{2k+1}}{(2k+1)!}=\sinh c . \] For Lemma 2 to send unit vectors to unit vectors we need \(\sinh c=1\), that is \[ c=\operatorname{arcsinh}(1)=\log\big(1+\sqrt2\big), \qquad \beta=\frac{2c}\pi=\frac2\pi\log\big(1+\sqrt2\big)\approx0.561 . \] With this choice, for unit \(u,v\) the vectors \(\Phi(u),\Psi(v)\) are unit vectors in \(\widehat H\) with \(\langle\Phi(u),\Psi(v)\rangle=\sin(\frac{\pi\beta}2\langle u,v\rangle)\), and since \(|\frac{\pi\beta}2\langle u,v\rangle|\leq c<\pi/2\), taking the arcsine gives Equation 1. This completes Idea 1, and the theorem follows with \[ K=\frac1\beta=\frac\pi{2\log(1+\sqrt2)}\approx1.782 . \]
The handwritten notes leave \(\beta\) unspecified; the computation above is the only place where a number enters. Larger \(\beta\) would give a better constant, and the constraint \(\sinh(\pi\beta/2)\leq1\) is exactly the requirement that the kernel trick produce unit vectors. Whether a cleverer choice of \(f\), or a cleverer rounding, can do better is the question of the exact value of \(K_G\).
It is instructive to see that \(K_G<\infty\) can be proved without the kernel trick, by Gaussian realization and truncation. Fix \(A\) satisfying the hypothesis and let \(K(A)\) be the best constant in the conclusion over all Hilbert spaces, which is finite. Choose unit vectors realizing it, so \(\sum_{ij}A_{ij}\langle u_i,v_j\rangle=K(A)\), and let \(g\sim N(0,I_d)\), \(U_i=\langle g,u_i\rangle\), \(V_j=\langle g,v_j\rangle\). Then \(K(A)=\mathbb E\sum_{ij}A_{ij}U_iV_j\). If the \(U_i,V_j\) were bounded by \(R\), the hypothesis would give \(K(A)\leq R^2\) at once. They are not, so split \(U_i=U_i^-+U_i^+\) with \(U_i^-=U_i\mathbb 1\{|U_i|\leq R\}\), and likewise \(V_j\). The term with both bounded parts is at most \(R^2\). Each of the three remaining terms is a bilinear form in vectors of \(L^2(\mathbb P)\), a Hilbert space, and the definition of \(K(A)\) bounds it by \(K(A)\max\|U_i^\pm\|_{L^2}\max\|V_j^\pm\|_{L^2}\). A Gaussian tail computation gives \(\|U_i^+\|_{L^2}\leq2/R\) for \(R\geq1\), so \[ K(A)\leq R^2+\frac{6K(A)}R . \] Taking \(R=12\) gives \(K(A)\leq288\), uniformly in \(A\). The argument shows where the difficulty lies: the Gaussian realization is exact, and all the loss is in handling the unbounded tails, which the sign rounding of Krivine’s proof avoids entirely.
4 Kernels, feature maps, and history
The kernel trick is much older and much wider than this application. A function \(\kappa:\mathcal X\times\mathcal X\to\mathbb R\) is a positive definite kernel if \((\kappa(x_i,x_j))_{ij}\) is positive semidefinite for every finite family of points, and the Moore–Aronszajn theorem says that these are exactly the functions of the form \(\kappa(x,y)=\langle\Phi(x),\Phi(y)\rangle\) for a map \(\Phi\) into some Hilbert space, the reproducing kernel Hilbert space of \(\kappa\). In machine learning one chooses a kernel, such as \(\exp(-\|x-y\|^2/2\sigma^2)\) or \((\langle x,y\rangle+r)^k\), and runs a linear algorithm in the feature space without ever writing \(\Phi\) down, since only inner products are needed. Krivine’s argument runs in the other direction: the target function \(\sin(c\langle u,v\rangle)\) is not a positive definite kernel, because its series has coefficients of both signs, and the two maps \(\Phi\neq\Psi\) are what handle the negative ones.
Grothendieck proved the inequality in 1953 (Grothendieck 1953), in the language of tensor norms and with the constant \(\sinh(\pi/2)\approx2.30\). Krivine’s proof and constant date from 1979 (Krivine 1979). Braverman, Makarychev, Makarychev and Naor (Braverman et al. 2013) showed that Krivine’s bound is not the true value of \(K_G\), though no explicit better constant is known. Pisier’s survey (Pisier 2012) traces the inequality through functional analysis, operator algebras, and computer science.
5 Where we go next
The convex relaxation detour is over. The course returns to suprema of Gaussian and sub-Gaussian processes, this time from the upper side: the next lecture proves Dudley’s inequality, which bounds \(\mathbb E\sup X\) by an integral of the metric entropy of the index set over all scales, and introduces chaining, the technique that will occupy the rest of the term.