In a recent paper, S. Khot and A. Naor show a natural generalization of the positive semidefinite Grothendieck's inequality. Grothendieck showed that there exists a constant $K > 0$ such that for every $n \times n$, symmetric semidefinite matrix $A=[a_{ij}]$, the following inequality holds:

$$\max_{x_1,\ldots,x_n} \sum_{ij} a_{ij}x_i^Tx_j \le K \max_{\epsilon_1,\ldots,\epsilon_n \in [-1,1]} \sum_{ij}a_{ij} \epsilon_i\epsilon_j,$$ where each $x_i$ is a unit vector (in Euclidean norm, so that $x_i^Tx_i=1$).

Khot and Naor studied a natural variant of this inequality, where the $n$ numbers $\epsilon_i$ are replaced by $n$ vectors $u_1,\ldots,u_n$ chosen from a set of $k < n$ unit vectors $v_1,\ldots,v_n$. The inequality becomes:

$$\max_{x_1,\ldots,x_n} \sum_{ij} a_{ij}x_i^Tx_j \le C \max_{u_1,\ldots,u_n \in \{v_1,\ldots,v_k\}} \sum_{ij}a_{ij} u_i^Tu_j.$$

They proved that this inequality actually holds, but the proof looks very complicated; as does the constant $C$. My question is thus in two parts:

(a) Is there any chance that there is a simpler proof for this "natural" generalization to Grothendieck's inequality?

(b) Does it seem like a feasible project to try and estimate this constant?

I am not an expert in these inequalities, but this generalization looks so interesting, that I had to seek out expert opinion.


Perhaps it would be beneficial to summarize the proof in words:

We wish to prove a certain Grothendieck-type inequality. We begin with a Lemma.

In Lemma 3.2 of this paper, we find an expression for a certain probability. In some sense, this calculation is really just (Hermite) Fourier analysis. We have a certain function, and we expand it into a (Hermite) Fourier basis. This proves our lemma.

We now use the probabilistic method to calculate the expected value of a certain random inner product. Using positive definiteness of the matrix A, and applying Lemma 3.2, we can throw away all but the "first level" (Hermite) Fourier coefficients. This gives our desired inequality, which ends up being sharp.

By the way of analogy, think about Hurwitz's proof of the Isoperimetric Inequality using Fourier series. We have an arbitrary curve, we expand it into its Fourier components, and we see that the inequality becomes sharp when all but the "first level" Fourier coefficients are set to zero. In a way, the same proof idea is used here.

As for computing the constant, this is indeed a challenge even in the simplest nontrivial cases. I don't think estimating it is very hard (for say, a "rough" estimate). To see what I mean, I would recommend reading the first in the series, "Approximate kernel clustering" (by the same authors).

  • $\begingroup$ Hi Steven, thanks for the nice summary. $\endgroup$
    – Suvrit
    Jan 26 '11 at 7:24
  • $\begingroup$ Sure! Though I suppose I didn't really answer your question directly. I guess I was trying to imply that the proof can be reduced to a "simple" description, and in doing this we see that it probably cannot be simplified very much (though I'm certainly no expert). As far as details go, maybe Gaussian randomness could be replaced by some other randomness, which would then change the choice of Fourier basis. Simplifying the general scheme of the proof may be hard, since it incorporates the "most direct" methods of other Grothendieck inequality proofs, plus additional ideas. $\endgroup$ Jan 27 '11 at 19:14

to clarify, are you asking if there is a simpler proof if one doesn't care about the optimal constant C? the sharp C seems to be the main point of the paper that you mention. I can imagine a slightly simpler proof with a non-sharp C, though note that the proof in the link is quite simple and short.

  • $\begingroup$ actually both: a simpler proof, with a reasonable, not necessarily best $C$, as well as simpler proof for the sharp $C$; but really, you think the proof in the paper is simple and short? I think the proof strategy is very well-explained and short, but the details are fairly long and technical. $\endgroup$
    – Suvrit
    Oct 20 '10 at 14:12
  • 2
    $\begingroup$ Although this is a good question by alex, I can't help feeling that it should have been left as a comment $\endgroup$
    – Yemon Choi
    Oct 20 '10 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.