Edit this page on GitHub

STT 996 — High Dimensional Probability

Lecture 08 — Grothendieck Identity and Max-Cut

(Source: handwritten notes :contentReference[oaicite:0]{index=0})

1. Grothendieck Identity

Let
\(g \sim \mathcal{N}(0, I_n) \in \mathbb{R}^n\)

So: \(g = (g_1, \dots, g_n), \quad g_i \overset{iid}{\sim} \mathcal{N}(0,1)\)

Let: \(u, v \in S^{n-1}, \quad \|u\| = \|v\| = 1\)

Statement (Grothendieck Identity)

\[\mathbb{E}\left[\operatorname{sign}(\langle g, u \rangle)\operatorname{sign}(\langle g, v \rangle)\right] = \frac{2}{\pi} \arcsin(\langle u, v \rangle)\]

Key Idea (Missing from lecture)

This is a purely geometric statement:

  • $g$ defines a random hyperplane
  • $\operatorname{sign}(\langle g, x \rangle)$ tells which side of the hyperplane $x$ lies on
  • So we are asking:

What is the probability that $u$ and $v$ lie on the same side of a random hyperplane?

2. Proof Strategy

Step 1: Rotational Invariance

Let $O$ be orthogonal: \(O^T O = I\)

Gaussian is invariant: \(Og \sim \mathcal{N}(0, I)\)

So we can rotate coordinates such that:

\(Ou = (1,0,\dots,0)\) \(Ov = (v_1, v_2, 0,\dots,0)\)

with: $$ v_1^2 + v_2^2 = 1

Step 2: Reduce to 2D

Then: \(\langle g, u \rangle = g_1\)

\[\langle g, v \rangle = v_1 g_1 + v_2 g_2\]

So the problem reduces to: \((g_1, g_2) \sim \mathcal{N}(0, I_2)\)

Step 3: Define Random Variable

Let: \(X = \operatorname{sign}(\langle g, u \rangle)\operatorname{sign}(\langle g, v \rangle)\)

So:

  • $X = +1$ if same sign
  • $X = -1$ if opposite sign

Let: \(p = \mathbb{P}(X = +1), \quad q = \mathbb{P}(X = -1)\)

Then: \(\mathbb{E}[X] = p - q = 1 - 2q\)

Step 4: Geometry (Missing intuition)

Let $\alpha$ = angle between $u$ and $v$: \(\langle u, v \rangle = \cos \alpha\)

Since: \((g_1, g_2) \sim \text{rotationally symmetric}\)

We can write: \(\frac{g}{\|g\|} \sim \text{Uniform}(S^1)\)

So the direction is uniform on the circle.

Step 5: Compute Probability

Event:

  • signs differ ⇔ hyperplane separates $u$ and $v$

This happens when angle falls in region of size $\alpha$.

Thus: \(q = \frac{\alpha}{\pi}\)

Step 6: Final Result

\[\mathbb{E}[X] = 1 - 2q = 1 - \frac{2\alpha}{\pi}\]

Using: \(\alpha = \arccos(\langle u,v \rangle)\)

We get: \(\mathbb{E}[X] = \frac{2}{\pi}\arcsin(\langle u,v \rangle)\)

(using identity $\arcsin(x) = \frac{\pi}{2} - \arccos(x)$)

3. Connection to Optimization

We consider:

Quadratic Integer Program

\[\max \sum_{i,j} A_{ij} x_i x_j\]

subject to: \(x_i \in \{-1,1\}\)

SDP Relaxation

Replace scalars with vectors: \(x_i \rightarrow u_i \in S^{n-1}\)

Problem becomes: \(\max \sum_{i,j} A_{ij} \langle u_i, u_j \rangle\)

Grothendieck Inequality

If: \(\left|\sum_{i,j} A_{ij} x_i x_j\right| \le 1 \quad \forall x_i \in \{-1,1\}\)

Then: \(\left|\sum_{i,j} A_{ij} \langle u_i, v_j \rangle\right| \le K\)

for some universal constant: \(K \le 1.783\)

4. Max-Cut Problem

Graph: \(G = (V,E)\)

Adjacency matrix: \(A_{ij} = \begin{cases} 1 & \text{if edge exists} \\ 0 & \text{otherwise} \end{cases}\)

Cut Representation

Let: \(x_i \in \{-1,1\}\)

Then: \(\text{cut}(G) = \frac{1}{2}\sum_{i<j} A_{ij}(1 - x_i x_j)\)

SDP Relaxation

Replace: \(x_i x_j \rightarrow \langle u_i, u_j \rangle\)

5. Random Hyperplane Rounding

Sample: \(g \sim \mathcal{N}(0,I)\)

Define: \(x_i = \operatorname{sign}(\langle u_i, g \rangle)\)

Key Theorem (Goemans–Williamson)

\[\mathbb{E}[\text{cut}] \ge 0.878 \cdot \text{OPT}\]

Proof Sketch

Using Grothendieck identity: \(\mathbb{E}[x_i x_j] = \frac{2}{\pi}\arcsin(\langle u_i, u_j \rangle)\)

Thus: \(\mathbb{E}[\text{cut}] = \frac{1}{2}\sum A_{ij}\left(1 - \frac{2}{\pi}\arcsin(\langle u_i,u_j\rangle)\right)\)

Compare with SDP objective: \(\frac{1}{2}\sum A_{ij}(1 - \langle u_i,u_j\rangle)\)

→ gives approximation ratio $0.878$

6. Functional / Tensor Notes

If: \(X \perp Y\)

then: \(f_{X,Y}(x,y) = f_X(x) f_Y(y)\)

Tensor notation: \(f_X \otimes f_Y = f_{X,Y}\)

Tensor Example

Vectors: \(a \in \mathbb{R}^m, \quad b \in \mathbb{R}^n\)

Outer product: \(a \otimes b = \begin{bmatrix} a_i b_j \end{bmatrix}\)

Inner product: \(\langle A, B \rangle = \sum_{i,j} A_{ij} B_{ij}\)

Higher Order Tensor

\[A \in \mathbb{R}^{n \times n \times k}, \quad B \in \mathbb{R}^{n \times n \times k}\] \[\langle A, B \rangle = \sum_{i,j,\ell} A_{ij\ell} B_{ij\ell}\]

Key Takeaways (What professor skipped)

  1. Rotation trick = Gaussian invariance
  2. Everything reduces to 2D geometry
  3. Random hyperplane = sign(g·x)
  4. Angle controls probability
  5. This identity powers SDP rounding
  6. Grothendieck bridges discrete ↔ continuous optimization

Mental Model (Very Important)

Think:

  • vectors $u_i$ live on a sphere
  • we slice space with random hyperplane
  • signs = partition of vertices
  • expected agreement = arcsin(inner product)

This is the entire engine behind modern approximation algorithms.

Edit this page on GitHub

Comments