Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Subhash Khot  Assaf Naor

Abstract In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_{ij}) with ∑ _{i=1}^{n} ∑ _{j=1}^{n} a_{ij} = 0 and a (small) k×k symmetric positive semidefinite matrix B = (b_{ij}). The goal is to find a partition {S_{1}, …, S_{k}} of {1, …n} which maximizes ∑ _{i=1}^{k} ∑ _{j=1}^{k} (∑ _{(p,q)∈S_{i}×S_{j}} a_{pq})b_{ij}. We design a polynomial time approximation algorithm that achieves an approximation ratio of \frac{R(B)^{2}}{C(B)}, where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if b_{ij} = ⟨v_{i}, v_{j}⟩ is the Gram matrix representation of B for some v_{1}, …, v_{k} ∈ ^{k} then R(B) is the minimum radius of a Euclidean ball containing the points {v_{1}, …, v_{k}}. The parameter C(B) is defined as the maximum over all measurable partitions {A_{1}, …, A_{k}} of ^{k−1} of the quantity ∑ _{i=1}^{k} ∑ _{j=1}^{k} b_{ij}⟨z_{i}, z_{j}⟩, where for i ∈ {1, …, k} the vector z_{i} ∈ ^{k−1} is the Gaussian moment of A_{i}, i.e., z_{i} = \frac{1}{(2π)^{(k−1)/2}} ∫_{A_{i}}xe^{−∥x∥_{2}^{2}/2}dx. We also show that for every ε > 0, achieving an approximation guarantee of (1 − ε)\frac{R(B)^{2}}{C(B)} is Unique Games hard.

1 Introduction

Kernel Clustering [14] is a combinatorial optimization problem which originates in the theory of machine learning. It is a general framework for clustering massive statistical data so as to uncover a certain hypothesized structure. The problem is defined as follows: let A = (a_{ij}) be an n × n symmetric positive semidefinite matrix which is usually normalized to be centered, i.e., ∑ _{i=1}^{n} ∑ _{j=1}^{n} a_{ij} = 0. The matrix A is often thought of as the correlation matrix of random variables (X_{1}, …, X_{n}) that measure attributes of certain empirical data, i.e., a_{ij} = [X_{i}X_{j}]. We are also given another symmetric positive semidefinite k × k matrix B = (b_{ij}) which functions as a hypothesis, or test matrix. Think of n as huge and k as small. The goal is to cluster A so as to obtain a smaller matrix which most resembles B. Formally, we wish to find a partition {S_{1}, …, S_{k}} of {1, …, n} so that if we write c_{ij} ∑ _{(p,q)∈S_{i}×S_{j}} a_{pq}, i.e., we form a k × k matrix C = (c_{ij}) by clustering A according to the given partition, then the resulting clustered version of A has the maximum correlation ∑ _{i=1}^{k} ∑ _{j=1}^{k} c_{ij}b_{ij} with the hypothesis matrix B. Equivalently, the goal is to evaluate the number:

Clust(A|B) max_{σ:{1,...,n}→{1,...,k}}∑_{i=1}^{k} ∑_{j=1}^{k} a_{ij}b_{σ(i)σ(j)} .  (1)

The strength of this generic clustering framework is based in part on the flexibility of adapting the matrix B to the problem at hand. Various particular choices of B lead to well studied optimization problems, while other specialized choices of B are based on statistical hypotheses which have been applied with some empirical success. We refer to [14, 7] for additional background and a discussion of specific examples.

In [7] we investigated the computational complexity of the kernel clustering problem. Answering a question raised in [14, Sec. 3], we showed that this problem has a constant factor polynomial time approximation algorithm. We refer to [7] for more information on the best known approximation guarantees. We also obtained hardness results for kernel clustering under various complexity assumptions. For example, we showed in [7] that when B = I_{3} is the 3×3 identity matrix then a \frac{16π}{27} approximation guarantee for Clust(A|I_{3}) is achievable, while any approximation guarantee smaller than \frac{16π}{27} is Unique Games hard. We will discuss the Unique Games Conjecture (UGC) presently. At this point it suffices to say that the above statement is evidence that the hardness threshold of the problem of approximating Clust(A|I_{3}) is \frac{16π}{27}, or more modestly that obtaining a polynomial time algorithm which approximates Clust(A|I_{3}) up to a factor smaller than \frac{16π}{27} would require a major breakthrough.

Another result proved in [7] is that when k ≥ 3 and B is either the k × k identity matrix or is spherical (i.e., b_{ii} = 1 for all i ∈ {1, …, k}) and centered (i.e., ∑ _{i=1}^{k} ∑ _{j=1}^{k} b_{ij} = 0) then there is a polynomial time approximation algorithm which, given A, approximates Clust(A|B) to within a factor of \frac{8π}{9} (1 − \frac{1}{k}). We also presented in [7] a conjecture (called the Propeller Conjecture) which we proved would imply that \frac{8π}{9} (1 − \frac{1}{k}) is the UGC hardness threshold when B = I_{k}. We refer to [7] for more information on the Propeller Conjecture, which at present remains open.

The above quoted result from [7] settles the problem of evaluating the UGC hardness threshold of the following type of algorithmic task: given A and an hypothesis matrix B which is guaranteed to belong to a certain class of matrices (in our case centered and spherical), approximate efficiently the number Clust(A|B). Naturally this can be refined to a family of optimization problems which depend on a fixed B: for each B, what is the UGC hardness threshold of the problem of, given A, approximating Clust(A|B)? In [7] we answered this question only when B = I_{3}, and for B = I_{k} assuming the Propeller Conjecture, and asked about the case of general B (we did give some B-dependent bounds in [7], but they were not sharp for B I_{k} for reasons that will become clear presently). This is a natural question since it makes sense to use the best possible polynomial time algorithm if we know B in advance.

Here we answer the above question in full generality. To explain our results we need to define two geometric parameters which are associated to B. Since B is symmetric and positive semidefinite we can find vectors v_{1}, …, v_{k} ∈ ^{k} such that B is their Gram matrix, i.e., b_{ij} = ⟨v_{i}, v_{j}⟩ for all i, j ∈ {1, …, k}. Let R(B) be the smallest possible radius of a Euclidean ball in ^{k} which contains {v_{1}, …, v_{k}} and let w(B) be the center of this ball. Let C(B) be the maximum over all partitions {A_{1}, …, A_{k}} of ^{k−1} into measurable sets of the quantity ∑ _{i=1}^{k} ∑ _{j=1}^{k} b_{ij}⟨z_{i}, z_{j}⟩, where for i ∈ {1, …, k} the vector z_{i} ∈ ^{k−1} is the Gaussian moment of A_{i}, i.e., z_{i} = \frac{1}{(2π)^{(k−1)/2}} ∫_{A_{i}}xe^{−∥x∥_{2}^{2}/2}dx (this maximum exists, as shown in Section 2). Our main result is the following theorem^{1}:

Theorem 1.1. For every symmetric positive semidefinite k×k matrix B there exists a randomized polynomial time algorithm which given an n × n symmetric positive semidefinite centered matrix A, outputs a number Alg(A) such that

Clust(A|B) ≤ [Alg(A)]≤ \frac{R(B)^{2}}{C(B)}Clust(A|B).

On the other hand, assuming the Unique Games Conjecture, no polynomial time algorithm approximates Clust(A|B) to within a factor strictly smaller than \frac{R(B)^{2}}{C(B)}.

As an example of Theorem 1.1 for a particular hypothesis matrix consider the following perturbation of the previously studied case B = I_{3}:

B_{c} (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & c \end{matrix}),

1We refer to the discussion in Question 1 in Section 1.1 below which addresses the issue of computing efficiently good approximate clusterings rather than approximating only the value Clust(A|B).

where c > 0 is a parameter. The problem of approximating efficiently Clust(A|B_{c}) corresponds to partitioning the rows of A into 3 sets S_{1}, S_{2}, S_{3} ⊆ {1, …, n} and maximizing the sum of the total masses of A on S_{1} × S_{1}, S_{2} × S_{2}, S_{3} × S_{3}, where the parameter c can be used to tune the weight of the set S_{3}. This problem is not particularly important—we chose it just as a concrete example for the sake of illustration. In Section 6 we compute the parameters R(B_{c}), C(B_{c}) and deduce that the UGC hardness threshold of the problem of computing Clust(A|B_{c}) equals \frac{4πc(1+c)^{2}}{(1+2c)^{3}} if c ≥ \frac{1}{2} and equals \frac{π(1+c)^{2}}{2+4c} if c ≤ \frac{1}{2}. The change at c = \frac{1}{2} corresponds in a qualitative change in the best algorithm for computing Clust(A|B_{c})—we refer to Section 6 for an explanation.

In the remainder of this introduction we will explain the various ingredients of Theorem 1.1(in particular the Unique Games Conjecture), and the new ideas used in its proof.

The main tool in the design of the algorithm in Theorem 1.1 is a natural generalization of the positive semidefinite Grothendieck inequality. In [4] Grothendieck proved that there exists a universal constant K > 0 such that for every n × n symmetric positive semidefinite matrix A = (a_{ij}) we have^{2}:

max_{x_{1},...,x_{n}∈S^{n−1}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨x_{i}, x_{j}⟩ ≤ K max_{ε_{1},...,ε_{n}∈{−1,1}}∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}ε_{i}ε_{j}.  (2)

The best constant K in (2) was shown in [12] to be equal to \frac{π}{2}. A natural variant of (2) is to replace the numbers −1, 1 by general v_{1}, …, v_{k} ∈ ^{k}, namely one might ask for the smallest constant K > 0 such that for every symmetric positive semidefinite n × n matrix A we have:

max_{x_{1},...,x_{n}∈S^{n−1}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨x_{i}, x_{j}⟩ ≤ K max_{u_{1},...,u_{n}∈{v_{1},...,v_{k}}}∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨u_{i}, u_{j}⟩.  (3)

In Section 3 we prove that (3) holds with K = \frac{1}{C(B)}, where B = (⟨v_{i}, v_{j}⟩)is the Gram matrix of v_{1}, …, v_{k}, and that this constant is sharp. This inequality is proved along the following lines. Fix n unit vectors x_{1}, …, x_{n} ∈ S^{n−1}. Let G = (g_{ij}) be a (k − 1) × n random matrix whose entries are i.i.d. standard Gaussian random variables. Let A_{1}, …, A_{k} ⊆ ^{k−1} be a measurable partition of ^{k−1} at which C(B) is attained. Define a random choice of u_{i} ∈ {v_{1}, …, v_{k}} by setting u_{i} = v_{ℓ} for the unique ℓ ∈ {1, …, k} such that Gx_{i} ∈ A_{ℓ}. The fact that (3) holds with K = \frac{1}{C(B)} is a consequence of the following fact, which we prove in Section 3:

[∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨u_{i}, u_{j}⟩]≥ C(B) ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨x_{i}, x_{j}⟩.  (4)

The crucial point in the proof of (4) is the following identity, proved in Lemma 3.2 as a corollary of the closed-form formula for the Poison kernel of the Hermite polynomials: for every two measurable subsets E, F ⊆ ^{k−1} and any two unit vectors x, y ∈ ^{n}, we have

Pr[Gx ∈ E and Gy ∈ F]

= γ_{k−1}(E)γ_{k−1}(F) + ⟨x, y⟩ ⟨∫_{E} udγ_{k−1}(u), ∫_{F} udγ_{k−1}(u)⟩+ ∑_{ℓ=2}^{∞} ⟨x^{⊗ℓ}, y^{⊗ℓ}⟩ ∑_{\begin{matrix}s∈( ∪\{0\})^{k−1} \\ s_{1}+··· +s_{k−1}=ℓ \end{matrix}} α_{s}(E)α_{s}(F), (5)

2This inequality is sometimes written as max_{x_{i},y_{i}∈S^{n−1}} ∑ _{i=1}^{n} ∑ _{j=1}^{n} a_{ij}⟨x_{i}, y_{j}⟩ ≤ K max_{ε_{i},δ_{i}∈{−1,1}}∑ _{i=1}^{n} ∑ _{j=1}^{n} a_{ij}ε_{i}δ_{j}, but it is easy (and standard) to verify that since A is positive semidefinite this formulation coincides with (2).

for some real coefficients {α_{s}(E)}_{s∈( ∪{0})^{k−1}} , {α_{s}(F)}_{s∈( ∪{0})^{k−1}} ⊆ . Here γ_{k−1} denotes the standard Gaussian measure on ^{k−1}. The product structure of the decomposition (5) hints at the role of the fact that A is positive semidefinite in the proof of (4)—the complete details appear in Section 3.

Once the generalized Grothendieck inequality (18) is obtained with K = \frac{1}{C(B)}, the existence of an algorithm as claimed in Theorem 1.1 follows via a natural semidefinite program (see equation (28) below)—this is done in Section 4.

We shall now pass to an explanation of the hardness result in Theorem 1.1. The Unique Games Conjecture, posed by Khot in [6], is as follows. A Unique Game is an optimization problem with an instance ℒ = ℒ (G(V, W, E), n, {π_{vw}}_{(v,w)∈E}). Here G(V, W, E) is a regular bipartite graph with vertex sets V and W and edge set E. Each vertex is supposed to receive a label from the set {1, …, n}. For every edge (v, w) ∈ E with v ∈ V and w ∈ W, there is a given permutation π_{vw}: {1, …, n} → {1, …, n}. A labeling of the Unique Game instance is an assignment ρ : V ∪ W → {1, …, n}. An edge (v, w) is satisfied by a labeling ρ if and only if ρ(v) = π_{vw}(ρ(w)). The goal is to find a labeling that maximizes the fraction of edges satisfied (call this maximum OPT(ℒ)). We think of the number of labels n as a constant and the size of the graph G(V, W, E) as the size of the problem instance. The Unique Games Conjecture (UGC) asserts that for arbitrarily small constants ε, δ > 0, there exists a constant n = n(ε, δ) such that no polynomial time algorithm can distinguish whether a Unique Games instance ℒ = ℒ (G(V, W, E), n, {π_{vw}}_{(v,w)∈W}) satisfies OPT(ℒ) ≤ δ (soundness) or there exists a labeling such that for 1 − ε fraction of the vertices v ∈ V all the edges incident with v are satisfied (completeness)^{3}. This conjecture is (by now) a commonly used complexity assumption to prove hardness of approximation results. Despite several recent attempts to get better polynomial time approximation algorithms for the Unique Game problem (see the table in [3] for a description of known results), the unique games conjecture still stands.

Our UGC hardness result follows the standard “dictatorship test” approach which is prevalent in PCP based hardness proofs, with a new twist which seems to be of independent interest. Since the kernel clustering problem is concerned with an assignment of one of k labels to each of the rows of the matrix A, the natural setting of our hardness proof is a dictatorship test for functions on {1, …, k}^{n} taking values in {1, …, k} (this was already the case in [7]). The general “philosophy” of such hardness proofs is to associate to every such function a certain numerical parameter called the “objective value” (which is adapted to the optimization problem at hand). The general scheme is to show that for some numbers a, b > 0, if f depends on only one coordinate (i.e., it is a “dictatorship”) then the objective value of f is at least a, while if f does not have any coordinate which is too influential then the objective value of f is at most b + o(1) (the o(1) depends on the notion of having no influential coordinates and its exact form is not important for the purpose of this overview—we refer to Section 5 for details). Once such a result is proved, techniques from the theory of Probabilistically Checkable Proofs can show that under a suitable complexity theoretic assumption (in our case the UGC) no polynomial time algorithm can achieve an approximation factor smaller than \frac{a}{b}.

Implicit to the above discussion is an underlying product distribution on {1, …, k}^{n} with respect to which we measure the influence of variables. In [7] the case of B = I_{k} was solved using the uniform distribution on {1, …, k}. It turns out that in order to prove the sharp hardness result in Theorem 1.1 we need to use a non-uniform distribution which depends on the geometry of B. Namely, writing B as a Gram matrix b_{ij} = ⟨v_{i}, v_{j}⟩, recall that R(B) is the radius of the smallest Euclidean ball containing {v_{1}, …, v_{k}} and w(B) is the center of this ball. A simple separation argument shows that w(B) is in the convex hull of the vectors in {v_{1}, …, v_{k}} whose distance from w(B) is exactly R(B). Writing w(B) as a convex combination of these points and considering the coefficients of this convex combination results in a probability distribution on {1, …, k}. In our hardness proof we use the n-fold product of (a small perturbation of) this probability distribution as the underlying distribution on {1, …, k} for our dictatorship test—see Figure 1 for a schematic description of the situation described above. The full details of this approach, including all the relevant definitions, are presented in Section 5.

3This version of the UGC is not the standard version as stated in [6], which only requires OPT(ℒ) ≥ 1 − ε in the completeness.

However, it was shown in [8] that this seemingly stronger version of the UGC actually follows from the original UGC—we will require this stronger statement in our proofs.

Figure 1: The geometry of the test matrix B induces a dictatorship test: the points above are the vectors {v_{1}, …, v_{k}} ⊆ ^{k} such that B is their Gram matrix. The ball depicted above is the smallest Euclidean ball containing {v_{1}, …, v_{k}}, R(B) is its radius and w(B) is its center. Then w(B) is in the convex hull of the points in {v_{1}, …, v_{k}} which are at distance exactly R(B) from w(B). Writing w(B) as a convex combination of these boundary points yields a distribution over the labels {1, …, k}. Our dictatorship test corresponds to selecting a point from the n-fold power of this probability space and comparing the behavior of a certain “objective value” (defined in equation (31) below), which depends only on the singleton Fourier coefficients, for dictatorships and for functions with low influences.

We end this discussion by referring to [7] for a detailed explanation of the relation to the work of Raghavendra [11] on sharp UGC hardness for constraint satisfaction problems (CSPs). Raghavendra designed a systematic approach that associates to every CSP a certain SDP whose integrality gap coincides with the UGC hardness threshold of the CSP. As explained in [7], a (nontrivial) observation can be used to modify Raghavendra’s theorem so as to apply to the Kernel Clustering problem as well (Kernel Clustering is a CSP with an additional global constraint corresponding to the requirement that the matrix A is positive semidefinite). Thus, one can also design a generic SDP, different from the one used here, whose integrality gap is the UGC hardness threshold of the problem of computing Clust(A|B). However, this alternative approach gives no information on the value of this threshold, and we do not know how to deduce, if at all possible, that it equals \frac{R(B)^{2}}{C(B)}. Moreover, our SDP is very simple and natural (see (28)), and has the additional feature that it does not depend on the test matrix B (though, of course, our rounding algorithm does depend on B). The generic SDP arising from Raghavendra’s method does depend on B. An interesting phenomenon that emerges from our analysis is that (assuming the UGC), on worst case instances there is no point in strengthening our SDP in a way that depends on B.

1.1 Open problems

We end this introduction with a statement of some open problems.

Question 1. Theorem 1.1 shows that the UGC hardness threshold of the problem of computing Clust(A|B) for a fixed hypothesis matrix B equals \frac{R(B)^{2}}{C(B)}. It is natural to ask if there is also a polynomial time algorithm

which outputs a clustering of A whose value is within a factor of \frac{R(B)^{2}}{C(B)} of the optimal clustering. The issue is that our rounding algorithm uses the partition {A_{1}, …, A_{k}} of ^{k−1} at which C(B) is attained. In Section 2 we study this optimal partition, and show that it has a relatively simple structure rather than being composed of general measurable sets: it corresponds to cones which are induced by the faces of a simplex. This information allows us to compute efficiently a partition which comes as close as we wish to the optimal partition when k is fixed, or grows slowly with n (to be safe lets just say for the sake of argument that k ≈ loglogn works). We refer to Remark 2.3 for details. We currently do not know if there is polynomial time rounding algorithm when, say, k ≈ \sqrt{n}. Given ε > 0, is there an algorithm which, given A and B, computes Clust(A|B) to within a factor of (1 + ε)\frac{R(B)^{2}}{C(B)}, and runs in time which is polynomial in both n and k (and maybe even 1/ε)?

Question 2. We remind the reader that the Propeller Conjecture remains open. This conjecture is about the value of C(I_{k}) when k ≥ 4. It states that the partition at which C(I_{k}) is attained is actually much simpler than what one might initially expect: only 3 of the sets have positive measure and they form a cylinder over a planar 120^{∘} “propeller”. We refer to [7] for a precise formulation and some evidence for the validity of the Propeller Conjecture.

Question 3. The kernel clustering problem was stated in [14] for matrices A which are centered. This makes sense from the perspective of machine learning, but it seems meaningful to also ask for the UGC hardness threshold of the same problem when A is not assumed to be centered. In the present paper we did not investigate this case at all, and it seems that the exact UGC hardness threshold when A is not necessarily centered is not known for any interesting hypothesis matrix B. Note that in [7] we showed that there is a constant factor polynomial time approximation algorithm when A is not necessarily centered: we obtained in [7] an approximation guarantee of 1 + \frac{3π}{2} in this case, but this is probably suboptimal.

2 Preliminaries on the parameter C(B)

Let B = (b_{ij})_{i,j=1}^{k} ∈ M_{k}( ) be a k × k symmetric positive semidefinite matrix. In what follows we fix k ≥ 2 and the matrix B. We also fix vectors v_{1}, …, v_{k} ∈ ^{k} for which b_{ij} = ⟨v_{i}, v_{j}⟩ for all i, j ∈ {1, …, k}.

Let γ_{n} denote the standard Gaussian measure on ^{n}, i.e., the density of γ_{n} is \frac{1}{(2π)^{n/2}}e^{−∥x∥_{2}^{2}/2}. We denote by H_{k} the Hilbert space L_{2}(γ_{n}) ⊕ L_{2}(γ_{n}) ⊕ ⋯ ⊕ L_{2}(γ_{n}) (k times) and we consider the convex subset Δ_{k}(γ_{n}) ⊆ H_{k} give by:

Δ_{k}(γ_{n}) {(f_{1}, …, f_{k}) ∈ H_{k} : ∀j ∈ {1, …, k} f_{j} ≥ 0 ∧ ∑_{j=1}^{k} f_{j} = 1} .  (6)

Define:

C(n, B) sup_{(f_{1},...,f_{k})∈Δ_{k}(γ_{n})} ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} · ⟨∫_{^{n}} xf_{i}(x)dγ_{n}(x), ∫_{^{n}} xf_{j}(x)dγ_{n}(x)⟩.  (7)

The following lemma is a variant of Lemma 3.1 in [7] (but see Remark 2.1for an explanation of a subtle difference). It simply states that the supremum in (7) is attained at a k-tuple of functions which correspond to a partition of ^{n}.

Lemma 2.1. There exist disjoint measurable sets A_{1}, …, A_{k} ⊆ ^{n} such that A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{k} = ^{n} and

∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} · ⟨∫_{A_{j}} xdγ_{n}(x), ∫_{A_{j}} xdγ_{n}(x)⟩= C(n, B).

Proof. Define Ψ : Δ_{k}(γ_{n}) → by

Ψ(f_{1}, …, f_{k}) ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} · ⟨∫_{^{n}} xf_{i}(x)dγ_{n}(x), ∫_{^{n}} xf_{j}(x)dγ_{n}(x)⟩.  (8)

We first observe that Ψ is a convex function. Indeed, fix λ ∈ [0, 1] and (f_{1}, …, f_{k}), (g_{1}, …, g_{k}) ∈ Δ_{k}(γ_{n}). Denote z_{i} ∫_{^{n}} xf_{i}(x)dγ_{n}(x) and w_{i} ∫_{^{n}} xg_{i}(x)dγ_{n}(x) for every i ∈ {1, …, k}. Then:

λΨ(f_{1}, …, f_{k}) + (1 − λ)Ψ(g_{1}, …, g_{k}) − Ψ(λf_{1} + (1 − λ)g_{1}, …, λf_{k} + (1 − λ)g_{k})
= ∑_{i=1}^{k} ∑_{j=1}^{k} ⟨v_{i}, v_{j}⟩ (λ⟨z_{i}, z_{j}⟩ + (1 − λ)⟨w_{i}, w_{j}⟩ − ⟨λz_{i} + (1 − λ)w_{i}, λz_{j} + (1 − λ)w_{j}⟩)

= λ(1 − λ) ∑_{i=1}^{k} ∑_{j=1}^{k} ⟨v_{i}, v_{j}⟩⟨z_{i} − w_{i}, z_{j} − w_{j}⟩

= λ(1 − λ) ∥∑_{i=1}^{n} v_{i} ⊗ (z_{i} − w_{i})∥_{2}^{2} ≥ 0.

Since Δ_{k}(γ_{n}) is a weakly compact subset of H_{k} and Ψ is weakly continuous and convex, Ψ attains its maximum (which equals C(n, B)) on Δ_{k}(γ_{n}) at an extreme point of Δ_{k}(γ_{n}), say at (f_{1}^{∗}, …, f_{k}^{∗}) ∈ Δ_{k}(γ_{n}). It follows that there exist measurable sets A_{1}, …, A_{k} ⊆ ^{n} which form a partition of ^{n} such that (f_{1}^{∗}, …, f_{k}^{∗}) = (1_{A_{1}}, …, 1_{A_{k}}) almost everywhere^{4}, as required.

Remark 2.1. In [7] a stronger result was proved when B = I_{k} (the k × k identity matrix). Namely, using the notation of the proof of Lemma 2.1 it was shown that the maximum of Ψ on the larger convex set

{ \atop Δ_{k}(γ_{n})} \{(f_{1}, …, f_{k}) ∈ H_{k} : ∀j ∈ \{1, …, k\} f_{j} ≥ 0 ∧ ∑_{j=1}^{k} f_{j} ≤ 1\}

is also attained at (f_{1}^{∗}, …, f_{k}^{∗}) = (1_{A_{1}}, …, 1_{A_{k}}) for some measurable sets A_{1}, …, A_{k} ⊆ ^{n} which form a partition of ^{n}. It turns out that this stronger fact helps to slightly simplify the proof of the corresponding UGC hardness result. However, we do not know how to prove this stronger statement for general B, so we formulated the weaker statement in Lemma 2.1, at the cost of needing to modify our proof of the UGC hardness result for general B in Section 5.

4To see this standard fact observe that otherwise there would be some A ⊆ ^{n} of positive measure, ε ∈ (0, 1/2), and distinct i, j ∈ {1, …, k} such that f_{i}1_{A}, f_{j}1_{A} ∈ (ε, 1 − ε). But (f_{1}^{∗}, …, f_{k}^{∗}) would then not be an extreme point since it is the average of (g_{1}, …, g_{k}), (h_{1}, …, h_{k}) ∈ Δ_{k}(γ_{n}) \ {(f_{1}^{∗}, …, f_{k}^{∗})}, where g_{ℓ} = h_{ℓ} = f_{ℓ}^{∗} for ℓ ∈ {1, …, k} \ {i, j} and g_{i} = (f_{i}^{∗} + ε)1_{A} + f_{i}^{∗}1_{^{n}\A}, h_{i} = (f_{i}^{∗} − ε)1_{A} + f_{i}^{∗}1_{^{n}\A}, g_{j} = (f_{j}^{∗} − ε)1_{A} + f_{j}^{∗}1_{^{n}\A}, h_{j} = (f_{j}^{∗} + ε)1_{A} + f_{j}^{∗}1_{^{n}\A}.

The same extreme point argument as in the proof of Lemma 2.1 shows that the maximum of Ψ on { \atop Δ_{k}(γ_{n})} is attained at (f_{1}^{∗}, …, f_{k}^{∗}) = (1_{A_{1}}, …, 1_{A_{k}}) for some disjoint measurable sets A_{1}, …, A_{k} ⊆ ^{n}, but now it does not follow that they necessarily cover all of ^{n}. When B = I_{k} it can be shown as in [7] that these sets do cover ^{n}. The same statement is true when B is diagonal, as we now show by arguing as in the proof in [7], but we do not know if it is true for general B. So, assume that B is diagonal with positive diagonal entries (b_{1}, …, b_{k}). Let A = ^{n} \ ⋃ _{i=1}^{k} A_{k}. Denote z_{j} ∫_{A_{j}} xdγ_{n}(x) and w = ∫_{A}xdγ_{n}(x). Note that w + z_{1} + ⋯ + z_{k} = 0. If w = 0 then Ψ attains its maximum on the partition {A ∪ A_{1}, A_{2}, …, A_{k}}, so assume for the sake of contradiction that w 0. For every i ∈ {1, …, k} we have:

∑_{j=1}^{n} b_{j}∥z_{j}∥_{2}^{2} = Ψ(1_{A_{1}}, …, 1_{A_{k}}) ≥ Ψ(1_{A_{1}}, …, 1_{A_{i−1}}, 1_{A∪A_{i}}, 1_{A_{i+1}}, …, 1_{A_{k}})

= ∑_{\begin{matrix}1≤j≤k \\ j i \end{matrix}} b_{j}∥z_{j}∥_{2}^{2} + b_{i}∥z_{i} + w∥_{2}^{2} = ∑_{j=1}^{n} b_{j}∥z_{j}∥_{2}^{2} + 2b_{i}⟨z_{i}, w⟩ + b_{i}∥w∥_{2}^{2}.

Thus 2⟨z_{i}, w⟩ + ∥w∥_{2}^{2} ≤ 0, and if we sum this inequality over i ∈ {1, …, k} while recalling that w = − ∑ _{i=1}^{k} z_{i} we see that (k − 2)∥w∥_{2}^{2} ≤ 0, which is a contradiction. Note that for general B the same argument shows that for all i ∈ {1, …, k} we have 2 ∑ _{j=1}^{k} b_{ij} ⟨z_{j}, w⟩+ b_{ii}∥w∥_{2}^{2} ≤ 0. These inequalities do not seem to lend themselves to the same type of easy contradiction as in the case of diagonal matrices.

The proof of the following lemma is an obvious midification of the proof of Lemma 3.2 in [7].

Lemma 2.2. If n ≥ k − 1 then C(n, B) = C(k − 1, B).

Proof. The inequality C(n, B) ≥ C(k − 1, B) is easy since for every (f_{1}, …, f_{k}) ∈ Δ_{k}(γ_{k−1}) we can define (f̃_{1}, …f̃_{k}) ∈ Δ_{k}(γ_{n}) by f̃_{j}(x, y) = f_{j}(x) (thinking here of ^{n} as ^{k−1} × ^{n−k+1}). Then for all j ∈ {1, …, k} we have ∫_{^{k−1}} xf_{j}(x)dγ_{k−1}(x) = ∫_{^{n}} xf̃_{j}(x)dγ_{n}(x), implying that Ψ (f̃_{1}, …f̃_{k}) = Ψ (f_{1}, …, f_{k}).

In the reverse direction, by Lemma 2.1 there is a measurable partition A_{1}, …, A_{k} of ^{n} such that if we define z_{j} ∫_{A_{j}} xdγ_{n}(x) ∈ ^{n} then we have ∑ _{i=1}^{k} ∑ _{j=1}^{k} b_{ij} ⟨z_{i}, z_{j}⟩ = C(n, B). Note that ∑ _{j=1}^{k} z_{j} = 0. Hence the dimension of the subspace V span{z_{1}, …, z_{k}} is d ≤ k − 1. Define g_{1}, …, g_{k} : V → [0, 1] by g_{j}(x) = γ_{V^{⊥}} ((A_{j} − x) ∩ V^{⊥} ). Then (g_{1}, …, g_{k}) ∈ Δ_{k}(γ_{V}), so that

C(k − 1, B) ≥ C(d, B)
≥ ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨∫_{V}xg_{i}(x)dγ_{V}(x), ∫_{V}xg_{j}(x)dγ_{V}(x)⟩

= ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨∫_{V}∫_{V^{⊥}} 1_{A_{i}}(x + y)xdγ_{V}(x)dγ_{V^{⊥}}(y), ∫_{V}∫_{V^{⊥}} 1_{A_{j}}(x + y)xdγ_{V}(x)dγ_{V^{⊥}}(y)⟩

= ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨∫_{A_{i}}Proj_{V}(w)dγ_{n}(w), ∫_{A_{j}} Proj_{V}(w)dγ_{n}(w)⟩

= ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨Proj_{V}(z_{i}), Proj_{V}(z_{j})⟩

= ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨z_{i}, z_{j}⟩= C(n, B),

as required.

In light of Lemma 2.2 we define C(B) C(k − 1, B). We shall now prove an analogue of Lemma 3.3 in [7] which gives structural information on the partition {A_{1}, …, A_{k}} of ^{k−1} at which C(B) is attained. We first recall some notation and terminology from [7]. Given distinct z_{1}, …, z_{k} ∈ ^{k−1} and j ∈ {1, …, k} define a set P_{j}(z_{1}, …, z_{k}) ⊆ ^{k} by

P_{j}(z_{1}, …, z_{k}) {x ∈ ^{k} : ⟨x, z_{j}⟩ = max_{i∈{1,...,k}}⟨x, z_{i}⟩}.

Thus {P_{j}(z_{1}, …, z_{k})}_{j=1}^{k} is a partition of ^{k−1} which we call the simplicial partition induced by z_{1}, …, z_{k} (strictly speaking the elements of this partition are not disjoint, but they intersect at sets of measure 0).

Lemma 2.3. Let A_{1}, …, A_{k} ⊆ ^{k−1} be a partition into measurable sets such that if we set z_{j} ∫_{A_{j}} xdγ_{k−1}(x) then

C(B) = ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨z_{i}, z_{j}⟩.  (9)

Assume also that this partition is minimal in the sense that the number of elements of positive measure in this partition is minimum among all the possible partitions satisfying (9). Define

J {j ∈ {1, …, k} : γ_{k−1}(A_{j}) > 0}

and set |J| = ℓ. Then up to an orthogonal transformation {z_{j}}_{j∈J} ⊆ ^{ℓ−1} and the vectors {z_{j}}_{j∈J} are non-zero and distinct. Moreover, if we define {w_{j}}_{j∈J} ⊆ ^{ℓ−1} by

w_{j} ∑_{s∈J} b_{js}z_{s},  (10)

then the vectors {w_{j}}_{j∈J} are distinct and for each j ∈ J we have

A_{j} = P_{j}((w_{i})_{i∈J})× ^{k−ℓ}  (11)

up to sets of measure zero.

Proof. Since ∑ _{j∈J} 1_{A_{j}} = 1 almost everywhere we have ∑ _{j∈J} z_{j} = 0. Thus the dimension of the span of {z_{j}}_{j∈J} is at most |J| − 1 = ℓ − 1, and by applying an orthogonal transformation we may assume that {z_{j}}_{j∈J} ⊆ ^{ℓ−1}. Also, for any distinct i, j ∈ J replace A_{i} by A_{i} ∪ A_{j} and A_{j} by the empty set and obtain a partition of ^{k−1} which contains exactly ℓ − 1 elements of positive measure and for which we have (by the minimality of ℓ):

C(B) > ∑_{s,t∈J\{i,j}}b_{st}⟨z_{s}, z_{t}⟩+ 2 ∑_{s∈J\{i,j}}b_{is} ⟨z_{s}, z_{i} + z_{j}⟩+ b_{ii} ∥z_{i} + z_{j} ∥_{2}^{2}
= ∑_{s,t∈J}b_{st}⟨z_{s}, z_{t}⟩+ 2 ∑_{s∈J} (b_{is} − b_{js})⟨z_{s}, z_{j}⟩+ (b_{ii} + b_{jj} − 2b_{ij}) ∥z_{j}∥_{2}^{2}
= C(B) + 2 ⟨w_{i} − w_{j}, z_{j}⟩+ ∥v_{i} − v_{j}∥_{2}^{2} · ∥z_{j}∥_{2}^{2},

where we used the fact that b_{st} = ⟨v_{s}, v_{t}⟩. Thus

2 ⟨w_{i} − w_{j}, z_{j}⟩+ ∥v_{i} − v_{j}∥_{2}^{2} · ∥z_{j}∥_{2}^{2} < 0,  (12)

and by symmetry we also have the inequality:

2 ⟨w_{j} − w_{i}, z_{i}⟩+ ∥v_{i} − v_{j}∥_{2}^{2} · ∥z_{i}∥_{2}^{2} < 0.  (13)

It follows in particular from (12) and (13) that z_{i} and z_{j} are non-zero and that w_{i} w_{j}. Moreover if we sum (12) and (13) we get that

2 ⟨w_{i} − w_{j}, z_{j} − z_{i}⟩+ ∥v_{i} − v_{j}∥_{2}^{2} (∥z_{i}∥_{2}^{2} + ∥z_{j}∥_{2}^{2})< 0

which implies that z_{i} z_{j}.

The above reasoning implies in particular that {P_{j}((w_{i})_{i∈J})× ^{k−ℓ}}_{j∈J} is a partition of ^{k−1} (up to pairwise intersections at sets of measure 0). Assume for the sake of contradiction that there exists i ∈ J such that

γ_{k−1} (A_{i} \ (P_{i}((w_{s})_{s∈J})× ^{k−ℓ}) )> 0.

Arguing as in the proof of Lemma 3.3 in [7] we see that there exists ε > 0 and j ∈ J \ {i} such that if we denote E {x ∈ A_{i} : ⟨x, w_{j}⟩ ≥ ⟨x, w_{i}⟩+ ε}then γ_{k−1}(E) > 0.

Define a partition Ã_{1}, …Ã_{k}of ^{k−1} by

Ã_{r} \{ \begin{matrix}A_{r} & r \{i, j\} \\ A_{i} \ E & r = i \\ A_{j} ∪ E & r = j. \end{matrix}

Then for w ∫_{E} xdγ_{k−1}(x) we have

C(B) ≥ ∑_{s,t∈J}b_{st}⟨∫ Ã_{s}xdγ_{k−1}(x), ∫ Ã_{t}xdγ_{k−1}(x)⟩
= ∑_{s,t∈J\{i,j}}b_{st}⟨z_{s}, z_{t}⟩+ 2 ∑_{s∈J\{i,j}}b_{is} ⟨z_{s}, z_{i} − w⟩+ 2 ∑_{s∈J\{i,j}}b_{js} ⟨z_{s}, z_{j} + w⟩
+2b_{ij} ⟨z_{i} − w, z_{j} + w⟩+ b_{ii}∥z_{i} − w∥_{2}^{2} + b_{jj} ∥z_{j} + w∥_{2}^{2}
= C(B) − 2 ∑_{s∈J} b_{is} ⟨z_{s}, w⟩+ 2 ∑_{s∈J} b_{js} ⟨z_{s}, w⟩+ (b_{ii} + b_{jj} − 2b_{ij}) ∥w∥_{2}^{2}
=^{(10)} C(B) + 2 ⟨w_{j} − w_{i}, w⟩+ ∥v_{i} − v_{j}∥_{2}^{2} · ∥w∥_{2}^{2}
≥ C(B) + 2 ∫_{E} (⟨w_{j}, x⟩ − ⟨w_{i}, x⟩) dγ_{k−1}(x)
≥ C(B) + 2εγ_{k−1}(E) > C(B),

a contradiction.

Remark 2.2. Note that we have the following non-trivial identity as a corollary of Lemma 2.3 (and using the same notation): For each i ∈ J,

z_{j} = ∫_{P_{j}((w_{i})_{i∈J})}xdγ_{ℓ−1}(x),  (14)

where we recall that the w_{i} are defined in (10). This system of equalities seems to contain non-trivial information on the structure of the partition at which C(B) is attained. In future research it would be of interest to exploit this information, though we have no need for it for our present purposes.

Remark 2.3. Given B and ε > 0 we can estimate C(B) up to an error of at most ε in constant time (which depends only on B, k, ε). Moreover, we can compute in constant time a conical simplicial partition of ^{k−1} at which the value of Ψ is at least C(B) − ε. These statements are a simple corollary of Lemma 2.3. Indeed, all we have to do is to run over all choices of ℓ ∈ {1, …, k} and for each such ℓ construct an appropriate net of z_{1}, …, z_{ℓ} ∈ ^{ℓ−1} of bounded size, and then check each of the induced simplicial partitions of ^{k−1} as in (11) for the one which maximizes Ψ. To this end we need some a priori bound on the length of z_{i}: the crude bound

∥z_{i}∥_{2} = ∥∫_{A_{i}}xdγ_{ℓ−1}(x)∥_{2} ≤ ∫_{^{ℓ−1}} ∥x∥_{2}dγ_{ℓ−1}(x) ≤ \sqrt{ℓ}

will suffice. Fix δ > 0 which will be determined momentarily. Let N be a δ-net in the Euclidean ball of

radius \sqrt{ℓ}in ^{ℓ−1}. Then |N| ≤ (^{\frac{3 \sqrt{ℓ}}{δ}})^{ℓ}.

Let A_{1}, …, A_{k} be as in Lemma 2.3, i.e., the true (minimal) partition at which C(B) is attained. Let J, ℓ, z_{i} and w_{i} be as in Lemma 2.3. For each i ∈ J find z′_{i} ∈ N for which ∥z_{i} − z′_{i}∥_{2} ≤ δ. Define w′_{i} = ∑ _{s∈J} b_{js}z′_{s}. Then we have the crude bound ∥w_{i} − w′_{i}∥_{2} ≤ δ ∑ _{s=1}^{k} ∑ _{t=1}^{k} |b_{st}| δ∥B∥_{1}. We also have the a priori bounds ∥w_{i}∥_{2}, ∥w′_{i}∥_{2} ≤ \sqrt{ℓ}∥B∥_{1}. By compactness there exists δ = δ(ε, ℓ, B) such that these estimates imply that for all j ∈ J,

∥z_{j} − ∫_{P_{j}((w′_{i})_{i∈J})}xdγ_{ℓ−1}(x)∥_{2} = ∥∫_{P_{j}((w_{i})_{i∈J})}xdγ_{ℓ−1}(x) − ∫_{P_{j}((w′_{i})_{i∈J})}xdγ_{ℓ−1}(x)∥_{2} ≤ \frac{ε}{2 \sqrt{ℓ}∥B∥_{1}}.  (15)

(It is actually easy to give a concrete bound on the required δ if so desired, but this is not important for our purposes.) It follows from (15) that:

C(B) ≥ ∑_{s,t∈J}b_{st}⟨∫_{P_{s}((w′_{i})_{i∈J})}xdγ_{ℓ−1}(x), ∫_{P_{t}((w′_{i})_{i∈J})}xdγ_{ℓ−1}(x)⟩

≥ ∑_{s,t∈J}b_{st}⟨z_{s}, z_{t}⟩− ∑_{s,t∈J}|b_{st}| · \frac{ε}{2 \sqrt{ℓ}∥B∥_{1}}· 2 \sqrt{ℓ} = C(B) − ε.

Note that the above integrals can be estimated efficiently (polynomial time in k) with arbitrarily good precision due to the fact that the simplicial cones P_{j}((w′_{i})_{i∈J}) have an efficient membership oracle and the Gaussian measure is log-concave. These are very crude bounds that suffice for our algorithmic purposes when k is fixed, but deteriorate exponentially with k. It would be of interest to understand whether we can estimate C(B) (and more importantly the associated partitions, as they are used in our rounding procedure) in time which is polynomial in k. Perhaps the identities (14) can play a role in the design of such an efficient algorithm, but we did not investigate this issue.

We end this section with a simple analytic interpretation of the parameter C(B). Given a square integrable function f : ^{n} → ^{k} its Rademacher projection Rad(f) : ^{n} → ^{k} (see [10] for an explanation of this terminology) is defined for x = (x_{1}, …, x_{n}) ∈ ^{n} as:

Rad(f)(x) = ∑_{i=1}^{n} (∫_{^{n}} y_{i}f (y)dγ_{n}(y))x_{i}.

Assume that f takes values in {v_{1}, …, v_{k}} ⊆ ^{k} and define A_{i} = f^{−1}(v_{i}) for i ∈ {1, …, k}. Then {A_{1}, …, A_{k}} is a measurable partition of ^{n}. We also have the identity:

Rad(f)(x) = ∑_{i=1}^{n} (∑_{j=1}^{k} v_{j} ∫_{A_{j}} y_{i}dγ_{n}(y))x_{i}.

Thus

∥Rad(f)∥_{L_{2}(γ_{n}, ^{k})}^{2} = ∫_{^{n}} ∥Rad(f)(x)∥_{2}^{2} dγ_{n}(x) = ∑_{i=1}^{n} ∥∑_{j=1}^{k} v_{j} ∫_{A_{j}} y_{i}dγ_{n}(y)∥_{2}^{2}

= ∑_{i=1}^{n} ∑_{j=1}^{k} ∑_{ℓ=1}^{k} ⟨v_{j}, v_{ℓ}⟩(∫_{A_{j}} y_{i}dγ_{n}(y))(∫_{A_{ℓ}}y_{i}dγ_{n}(y))= ∑_{j=1}^{k} ∑_{ℓ=1}^{k} b_{jℓ} ⟨∫_{A_{j}} ydγ_{n}(y), ∫_{A_{j}} ydγ_{n}(y)⟩. (16)

The identity (16) implies the following lemma: Lemma 2.4. For every n ≥ k − 1 we have:

C(B) = max_{f: ^{n}→{v_{1},...,v_{k}}} ∥Rad(f)∥_{L_{2}(γ_{n}, ^{k})}^{2} .

Recall that R(B) is defined as the radius of the smallest ball in ^{k} which contains the set {v_{1}, …, v_{k}} and that w(B) is the center of this ball. Lemma 2.4 implies the following corollary: Corollary 2.5. C(B) ≤ R(B)^{2}. Proof. Let {A_{1}, …, A_{k}} be a partition of ^{k−1} into measurable sets such that if we define z_{j} = ∫_{A_{j}} xdγ_{k−1}(x) then

C(B) = ∑_{i=1}^{k} ∑_{j=1}^{k} ⟨v_{i}, v_{j}⟩⟨z_{i}, z_{j}⟩

= ∑_{i=1}^{k} ∑_{j=1}^{k} ⟨v_{i} − w(B), v_{j} − w(B)⟩⟨z_{i}, z_{j}⟩+ 2 ∑_{i=1}^{k} ⟨v_{i}, w(B)⟩⟨z_{i}, ∑_{j=1}^{k} z_{j}⟩+ ∥w(B)∥_{2}^{2} · ∥∑_{j=1}^{k} z_{j} ∥_{2}^{2} . (17)

Since ∑ _{j=1}^{k} z_{j} = 0 it follows from (16) and (17) that for f : ^{k−1} → {v_{i} − w(B)}_{i=1}^{k} defined by f |_{A_{i}} = v_{i}−w(B) we have:

C(B) = ∥Rad(f)∥_{L_{2}(γ_{n}, ^{k})}^{2} ≤^{(⋆)} ∥f ∥_{L_{2}(γ_{n}, ^{k})}^{2} ≤ ∥f ∥_{L_{∞} (γ_{n}, ^{k})}^{2} = max_{i∈{1,...,k}}∥v_{i} − w(B)∥_{2}^{2} = R(B)^{2},

where in (⋆) we used the fact that Rad is an orthogonal projection on the Hilbert space L_{2}(γ_{n}, ^{k}).

3 Generalized positive semidefinite Grothendieck inequalities

The purpose of this section is to prove the following theorem, which as explained in the introduction, is an extension of Grothendieck’s inequality for positive semidefinite matrices. Theorem 3.1. Let A = (a_{ij}) ∈ M_{n}( ) be an n × n symmetric positive semidefinite matrix. Let v_{1}, …, v_{k} ∈ ^{k} be k ≥ 2 vectors and let B = (b_{ij} = ⟨v_{i}, v_{j}⟩) be the corresponding Gram matrix. Then

max_{x_{1},...,x_{n}∈S^{n−1}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨x_{i}, x_{j}⟩ ≤ \frac{1}{C(B)} max_{σ:\{1,...,n\}→\{1,...,k\}}∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨v_{σ(i)}, v_{σ(j)} ⟩.  (18)

We shall prove in Section 3.1 that the factor \frac{1}{C(B)} in (18) cannot be improved, even when in (18) A is restricted to be centered, i.e., ∑ _{i=1}^{n} ∑ _{j=1}^{n} a_{ij} = 0.

The key tool in the proof of Theorem 3.1 is the following lemma:

Lemma 3.2. Let {g_{ij} : i ∈ {1, …, m}, j ∈ {1, …, n}} be i.i.d. standard Gaussian random variables and let G = (g_{ij}) be the corresponding m × n random Gaussian matrix. Fix two unit vectors x, y ∈ S^{n−1} and two measurable subsets E, F ⊆ ^{m}. Then:

Pr[Gx ∈ E ∧ Gy ∈ F]

= γ_{m}(E)γ_{m}(F) + ⟨x, y⟩ ⟨∫_{E} udγ_{m}(u), ∫_{F} udγ_{m}(u)⟩+ ∑_{ℓ=2}^{∞} ⟨x^{⊗ℓ}, y^{⊗ℓ}⟩ ∑_{\begin{matrix}s∈( ∪\{0\})^{m} \\ s_{1}+··· +s_{m}=ℓ \end{matrix}} α_{s}(E)α_{s}(F), (19)

for some real coefficients {α_{s}(E)}_{s∈( ∪{0})^{m}}, {α_{s}(F)}_{s∈( ∪{0})^{m}} ⊆ .

Proof. Denote r = ⟨x, y⟩. Let g, h ∈ be independent standard Gaussian random variables and let g_{1}, …, g_{m} ∈ ^{n} be i.i.d. standard Gaussian random vectors in ^{n} (i.e., they are independent and distributed according to γ_{n}). Then for each i ∈ {1, …, m} the planar random vector (⟨g_{i}, x⟩, ⟨g_{i}, y⟩) ∈ ^{2} has the same distribution as (g, rg + \sqrt{1 − r^{2}}h) ∈ ^{2}, and hence its density is given for (u, v) ∈ ^{2} by:

f_{r}(u, v) \frac{1}{2π \sqrt{1 − r^{2}}} · exp(−\frac{u^{2} − 2ruv + v^{2}}{2(1 − r^{2})}) .

The Hermite polynomials {H_{k}}_{k=0}^{∞} are defined as:

H_{k}(t) (−1)^{k}e^{t^{2}} \frac{d^{k}}{dt^{k}}(e^{−t^{2}}) = ∑_{s=0}^{⌊k/2⌋}\frac{(−1)^{s}k!}{s!(k − 2s)!} (2t)^{k−2s}.

The formula for the Poison kernel for Hermite polynomials (see for example equation 6.1.13 in [1] or the discussion in [15]) says that

f_{r}(u, v) = \frac{e^{−(u^{2}+v^{2})/2}}{2π} ∑_{k=0}^{∞} \frac{r^{k}}{2^{k}k!}H_{k}( \frac{u}{\sqrt{2}})H_{k}( \frac{v}{\sqrt{2}}).

Since the vector (Gx, Gy) ∈ ^{2m} has the same distribution as the vector ((⟨g_{i}, x⟩, ⟨g_{i}, y⟩))_{i=1}^{m}, whose (planar) entries are i.i.d. with density f_{r}, we see that:

Pr[Gx ∈ E ∧ Gy ∈ F]= ∫_{E×F} (∏_{i=1}^{m} f_{r}(u_{i}, v_{i}))dudv

= ∫_{E×F} \frac{e^{−(∥u∥_{2}^{2}+∥v∥_{2}^{2})/2}}{(2π)^{m}}(∏_{i=1}^{m} (∑_{k=0}^{∞} \frac{r^{k}}{2^{k}k!}H_{k}( \frac{u_{i}}{\sqrt{2}})H_{k}( \frac{v_{i}}{\sqrt{2}})))dudv

= ∫_{E×F} ( ∑_{s∈( ∪\{0\})^{m}} \frac{r^{s_{1}+··· +s_{m}}}{2^{s_{1}+··· +s_{m}} ∏ _{i=1}^{m} s_{i}!} (∏_{i=1}^{m} H_{s_{i}} ( \frac{u_{i}}{\sqrt{2}}))(∏_{i=1}^{m} H_{s_{i}} ( \frac{v_{i}}{\sqrt{2}})))dγ_{m}(u)dγ_{m}(v)

= γ_{m}(E)γ_{m}(F) + ⟨x, y⟩ ⟨∫_{E} udγ_{m}(u), ∫_{F} udγ_{m}(u)⟩+ ∑_{ℓ=2}^{∞} ⟨x^{⊗ℓ}, y^{⊗ℓ}⟩ ∑_{\begin{matrix}s∈( ∪\{0\})^{m} \\ s_{1}+··· +s_{m}=ℓ \end{matrix}} α_{s}(E)α_{s}(F),

where we used the fact that H_{0}(t) = 1 and H_{1}(t) = 2t, and for every measurable subset W ⊆ R^{m} and s ∈ ( ∪ {0})^{m} the notation

α_{s}(W) \frac{1}{2^{(s_{1}+··· +s_{m})/2} ∏ _{i=1}^{m} \sqrt{s_{i}!}} ∫_{W} (∏_{i=1}^{m} H_{s_{i}} ( \frac{u_{i}}{\sqrt{2}}))dγ_{m}(u).

The proof of the identity (14) is complete.

Proof of Theorem 3.1. Fix n unit vectors x_{1}, …, x_{n} ∈ S^{n−1}. Let {A_{1}, …, A_{k}} be a partition of ^{k−1} into measurable subsets. Let G be a random Gaussian matrix as in Lemma 3.2 with m = k − 1. Define a random assignment σ : {1, …, n} → {1, …, k} by setting σ(i) to be the unique p ∈ {1, …, k} for which Gx_{i} ∈ A_{p}. Then for every i, j ∈ {1, …, n} we have

[⟨v_{σ(i)}, v_{σ(j)} ⟩] = ∑_{p=1}^{k} ∑_{q=1}^{k} ⟨v_{p}, v_{q}⟩Pr[Gx_{i} ∈ A_{p} ∧ Gx_{j} ∈ A_{q}]= ∑_{p=1}^{k} ∑_{q=1}^{k} b_{pq} Pr[Gx_{i} ∈ A_{p} ∧ Gx_{j} ∈ A_{q}].

We may therefore apply Lemma 3.2 to deduce that:

[∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨v_{σ(i)}, v_{σ(j)} ⟩] = (∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} )∑_{p=1}^{k} ∑_{q=1}^{k} b_{pq}γ_{k−1}(A_{p})γ_{k−1}(A_{q})

+ (∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}, x_{j}⟩)∑_{p=1}^{k} ∑_{q=1}^{k} b_{pq} ⟨∫_{A_{p}}xdγ_{k−1}(x), ∫_{A_{q}}xdγ_{k−1}(x)⟩

+ ∑_{ℓ=2}^{∞} (∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}^{⊗ℓ}, x_{j}^{⊗ℓ}⟩) ∑_{\begin{matrix}s∈( ∪\{0\})^{m} \\ s_{1}+··· +s_{m}=ℓ \end{matrix}} ∑_{p=1}^{k} ∑_{q=1}^{k} b_{pq}α_{s}(A_{p})α_{s}(A_{q})

≥ (∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}, x_{j}⟩)∑_{p=1}^{k} ∑_{q=1}^{k} b_{pq} ⟨∫_{A_{p}}xdγ_{k−1}(x), ∫_{A_{q}}xdγ_{k−1}(x)⟩,

where we used the fact that both A and B are positive semidefinite. It thus follows that there exists an assignment σ : {1, …, n} → {1, …, k} for which

∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨v_{σ(i)}, v_{σ(j)} ⟩≥ (∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}, x_{j}⟩)∑_{p=1}^{k} ∑_{q=1}^{k} b_{pq} ⟨∫_{A_{p}}xdγ_{k−1}(x), ∫_{A_{q}}xdγ_{k−1}(x)⟩,

and since this is true for all measurable partitions {A_{1}, …, A_{k}} of ^{k−1} we deduce that there exists an assignment σ : {1, …, n} → {1, …, k} for which:

∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨v_{σ(i)}, v_{σ(j)} ⟩≥ C(B) ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}, x_{j}⟩,

as required.

3.1 Optimality

The purpose of this section is to show that Theorem 3.1 is sharp:

Theorem 3.3. Let v_{1}, …, v_{k} ∈ ^{k} be k ≥ 2 vectors and let B = (b_{ij} = ⟨v_{i}, v_{j}⟩) be the corresponding Gram matrix. Assume that K > 0 is a constant such that for every n ∈ and every centered symmetric positive semidefinite matrix A = (a_{ij}) ∈ M_{n}( ) we have:

max_{x_{1},...,x_{n}∈S^{n−1}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨x_{i}, x_{j}⟩ ≤ K max_{σ:{1,...,n}→{1,...,k}}∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}⟨v_{σ(i)}, v_{σ(j)} ⟩.  (20)

Then K ≥ \frac{1}{C(B)}.

Proof. The proof consists of a discretization of a continuous example. The discretization step is somewhat tedious, but straightforward. We will start with a presentation of the continuous example. Fix m ∈ and let g, h ∈ ^{m} be independent standard gaussian random vectors. Since (∥g∥_{2}, ∥h∥_{2}) is independent of (\frac{g}{∥g∥_{2}}, \frac{h}{∥h∥_{2}}) we have:

∫_{^{m}× ^{m}} ⟨x, y⟩ · ⟨\frac{x}{∥x∥_{2}}, \frac{y}{∥y∥_{2}}⟩dγ_{m}(x)dγ_{m}(y) = [∥g∥_{2} · ∥h∥_{2} ⟨\frac{g}{∥g∥_{2}}, \frac{h}{∥h∥_{2}}⟩^{2}]

= [∥g∥_{2} · ∥h∥_{2}] · [⟨\frac{g}{∥g∥_{2}}, \frac{h}{∥h∥_{2}}⟩^{2}]= [∥g∥_{2}]^{2} [\frac{g_{1}^{2}}{∥g∥_{2}^{2}}]= [∥g∥_{2}]^{2} \frac{1}{m} ∑_{i=1}^{m} [\frac{g_{i}^{2}}{∥g∥_{2}^{2}}]= \frac{1}{m} [∥g∥_{2}]^{2} , (21)

where we used the rotation invariance of the distribution of h.

The distribution of ∥g∥_{2}^{2} is the χ^{2} distribution with m degrees of freedom, and therefore its density at u > 0 equals \frac{1}{2^{m/2}Γ(m/2)}u^{\frac{m}{2}−1}e^{−u/2}. It follows that

[∥g∥_{2}]= \frac{1}{2^{m/2}Γ(m/2)}∫ _{0}^{∞} \sqrt{u}· u^{\frac{m}{2}−1}e^{−u/2}du = \sqrt{2} · \frac{Γ (\frac{m+1}{2})}{Γ (\frac{m}{2})} ≥ \sqrt{m}(1 − O (\frac{1}{m})) ,  (22)

where the last step is an application of Stirling’s formula. Plugging (22) into (21) we see that:

∫_{^{m}× ^{m}} ⟨x, y⟩ · ⟨\frac{x}{∥x∥_{2}}, \frac{y}{∥y∥_{2}}⟩dγ_{m}(x)dγ_{m}(y) ≥ 1 − O (\frac{1}{m}).  (23)

Now, assuming that m ≥ k − 1, for every f : ^{m} → {v_{1}, …, v_{k}} we have

∫_{^{m}× ^{m}} ⟨x, y⟩ · ⟨f (x), f (y)⟩dγ_{m}(x)dγ_{m}(y) = ∥∫_{^{m}} x ⊗ f (x)dγ_{m}(x)∥_{2}^{2}

= ∥∑_{i=1}^{m} e_{i} ⊗ (∫_{^{m}} x_{i}f (x)dγ_{m}(x))∥_{2}^{2} = ∥Rad(f)∥_{L_{2}(γ_{m}, ^{k})}^{2} ≤ C(B), (24)

where we used Lemma 2.4 (and here e_{1}, …, e_{m} is the standard basis or ^{m}).

We shall now perform a simple discretization argument to conclude the proof of Theorem 3.3. Fix ε > 0 and M ∈ . Let ℱ be the set of all axis parallel cubes in [−εM, εM]^{m} which are a product of m intervals whose endpoints are consecutive integer multiples of ε in [−M, M]. Thus |ℱ | = (2M)^{m} and each Q ∈ ℱ has volume ε^{m}. For Q ∈ ℱ let z_{Q} be the center of Q. For every P, Q ∈ ℱ define

a_{PQ} ε^{2m}e^{− \frac{∥z_{P}∥^{2}_{2}+∥z_{Q}∥^{2}_{2}}{2}} ⟨z_{P}, z_{Q}⟩.

By our assumption (20) there is an assignment σ : ℱ → {1, …, k} such that

∑_{P,Q∈ℱ} a_{PQ}⟨\frac{z_{P}}{∥z_{P}∥_{2}}, \frac{z_{Q}}{∥z_{Q}∥_{2}}⟩≤ K ∑_{P,Q∈ℱ} a_{PQ}⟨v_{σ(P)}, v_{σ(Q)}⟩.  (25)

We shall now use the following straightforward (and crude) estimates:

|∫_{^{m}× ^{m}} ⟨x, y⟩ ⟨\frac{x}{∥x∥_{2}}, \frac{y}{∥y∥_{2}}⟩dγ_{m}(x)dγ_{m}(y) − ∑_{P,Q∈ℱ} a_{PQ}⟨\frac{z_{P}}{∥z_{P}∥_{2}}, \frac{z_{Q}}{∥z_{Q}∥_{2}}⟩|

≤ ∑_{P,Q∈ℱ} ∫_{P×Q} |e^{− \frac{∥z_{P}∥^{2}_{2}+∥z_{Q}∥^{2}_{2}}{2}} ⟨z_{P}, z_{Q}⟩⟨\frac{z_{P}}{∥z_{P}∥_{2}}, \frac{z_{Q}}{∥z_{Q}∥_{2}}⟩− e^{− \frac{∥x∥^{2}_{2}+∥y∥^{2}_{2}}{2}} ⟨x, y⟩⟨\frac{x}{∥x∥_{2}}, \frac{y}{∥y∥_{2}}⟩| dxdy

+ |∫_{( ^{m}× ^{m})\([−εM,εM]^{m}×[−εM,εM]^{m})} ⟨x, y⟩ ⟨\frac{x}{∥x∥_{2}}, \frac{y}{∥y∥_{2}}⟩dγ_{m}(x)dγ_{m}(y)|

≤ O(1) \sqrt{m}ε ( \sqrt{m}Mε)^{3} ∑_{P,Q∈ℱ} ∫_{P×Q} e^{− \frac{∥x∥^{2}_{2}+∥y∥^{2}_{2}}{2}}dxdy + O(1)m^{2}e^{− \frac{(εM)^{2}}{4}}

≤ O(1) \sqrt{m}ε ( \sqrt{m}Mε)^{3} + O(1)m^{2}e^{− \frac{(εM)^{2}}{4}} .

We shall require in what follows that εM = 2m. Hence, using (23) we deduce that:

∑_{P,Q∈ℱ} a_{PQ}⟨\frac{z_{P}}{∥z_{P}∥_{2}}, \frac{z_{Q}}{∥z_{Q}∥_{2}}⟩≥ 1 − O (m^{5}ε + \frac{1}{m}).  (26)

On the other hand, define f : ^{m} → {v_{1}, …, v_{k}} by

f (x) = \{ \begin{matrix}v_{σ(Q)} & x ∈ Q ∈ ℱ , \\ v_{1} & x [−εM, εM]^{m}. \end{matrix}

Observe that by symmetry

∫_{( ^{m}× ^{m})\([−εM,εM]^{m}×[−εM,εM]^{m})} ⟨x, y⟩ · ⟨f (x), f (y)⟩dγ_{m}(x)dγ_{m}(y) = 0,

and therefore a similar crude estimate yields:

|∫_{^{m}× ^{m}} ⟨x, y⟩ · ⟨f (x), f (y)⟩dγ_{m}(x)dγ_{m}(y) − ∑_{P,Q∈ℱ} a_{PQ}⟨v_{σ(P)}, v_{σ(Q)}⟩|

≤ ∑_{P,Q∈ℱ} ∫_{P×Q} |e^{− \frac{∥x∥^{2}_{2}+∥y∥^{2}_{2}}{2}} ⟨x, y⟩− e^{− \frac{∥z_{P}∥^{2}_{2}+∥z_{Q}∥^{2}_{2}}{2}} ⟨z_{P}, z_{Q}⟩| |⟨v_{σ(P)}, v_{σ(Q)}⟩|dxdy
≤ O (m^{5}ε) max_{i∈{1,...,k}}∥v_{i}∥_{2}^{2}.  (27)

Choosing ε = m^{−6} (and thus M = 2m^{7}), and combining (27) with (24) and (26), yields in combination with (25) the bound:

1 − O (\frac{1}{m}) ≤ K (C(B) + O (\frac{1}{m}) max_{i∈\{1,...,k\}}∥v_{i}∥_{2}^{2}).

Letting m → ∞ concludes the proof of Theorem 3.3.

4 A sharp approximation algorithm for kernel clustering

Let A = (a_{ij}) ∈ M_{n}( ) be a centered symmetric positive semidefinite matrix and let B = (b_{ij}) ∈ M_{k}( ) be a symmetric positive semidefinite matrix. Our goal is to design a polynomial time algorithm which approximates the value:

Clust(A|B) = max_{σ:{1,...,n}→{1,...,k}}∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}b_{σ(i)σ(j)} .

We proceed as follows. We first find vectors v_{1}, …, v_{k} ∈ ^{k} such that b_{ij} = ⟨v_{i}, v_{j}⟩ for all i, j ∈ {1, …, k}. This can be done in polynomial time (Cholesky decomposition). Let R(B) be the minimum radius of the Euclidean ball in ^{k} that contains {v_{1}, …, v_{k}} and let w(B) be the center of this ball. Both R(B) and w(B) can be efficiently computed with arbitrary precision by solving an appropriate semidefinite program.

We now use semidefinite programming to compute the value:

SDP(A|B) max {∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}, x_{j}⟩: x_{1}, …, x_{n} ∈ ^{n} ∧ ∥x_{i}∥_{2} ≤ 1 ∀i ∈ {1, …, n}}

= max {∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}, x_{j}⟩: x_{1}, …, x_{n} ∈ S^{n−1} } , (28)

where the last equality in (28) holds since the function (x_{1}, …, x_{n}) ↦ ∑ _{i=1}^{n} ∑ _{j=1}^{n} a_{ij} ⟨x_{i}, x_{j}⟩is convex (by virtue of the fact that A is positive semidefinite). We claim that

\frac{Clust(A|B)}{R(B)^{2}}≤ SDP(A|B) ≤ \frac{Clust(A|B)}{C(B)},  (29)

which implies that if we output the number R(B)^{2}SDP(A|B) we will obtain a polynomial time algorithm which approximates Clust(A|B) up to a factor of \frac{R(B)^{2}}{C(B)}.

To verify (29) let x_{1}^{∗}, …, x_{n}^{∗} ∈ S^{n−1} and σ^{∗} : {1, …, n} → {1, …, k} be such that

SDP(A|B) = ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨x_{i}^{∗}, x_{j}^{∗}⟩,

and

Clust(A|B) = ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}b_{σ^{∗}(i)σ^{∗}(j)} .

Write (a_{ij})_{i,j=1}^{n} = (⟨u_{i}, u_{j}⟩)_{i,j=1}^{n} for some u_{1}, …, u_{n} ∈ ^{n}. The assumption that A is centered means that ∑ _{i=1}^{n} u_{i} = 0. The right-hand side of inequality in (29) is simply a restatement of Theorem 3.1. The left-hand side inequality (29) follows from the fact that \frac{v_{σ^{∗}(i)}−w(B)}{R(B)} has norm at most 1 for all i ∈ \{1, …, n\}. Indeed, these norm bounds imply that:

SDP(A|B) ≥ ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨\frac{v_{σ^{∗}(i)} − w(B)}{R(B)}, \frac{v_{σ^{∗}(j)} − w(B)}{R(B)}⟩

= \frac{1}{R(B)^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ⟨v_{σ^{∗}(i)}, v_{σ^{∗}(j)} ⟩− \frac{2}{R(B)^{2}} ∑_{i=1}^{n} ⟨w(B), v_{σ^{∗}(i)}⟩⟨u_{i}, ∑_{j=1}^{n} u_{j}⟩+ \frac{∥w(B)∥_{2}^{2}}{R(B)^{2}}∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}

= \frac{Clust(A|B)}{R(B)^{2}}.

This completes the proof that our algorithm approximates efficiently the number Clust(A|B), but does not address the issue of how to efficiently compute an assignment σ : {1, …, n} → {1, …, k} for which the induced clustering of A has the required value. An inspection of the proof of Theorem 3.1 shows that the issue here is to find efficiently a conical simplicial partition A_{1}, …, A_{k} of ^{k−1} at which C(B) is almost attained, say

∑_{p=1}^{k} ∑_{q=1}^{k} b_{pq} ⟨∫_{A_{p}}xdγ_{k−1}(x), ∫_{A_{q}}xdγ_{k−1}(x)⟩≥ (1 − ε)C(B).

Once this partition is computed, using the notation in the proof of Theorem 3.1 we have a randomized algorithm which outputs an assignment σ : {1, …, n} → {1, …, k} such that

σ [∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}b_{σ(i)σ(j)} ]≥ \frac{(1 − ε)C(B)}{R(B)^{2}}Clust(A|B).

Note that there is no difficulty to compute σ efficiently once the partition {A_{1}, …, A_{k}} is given, since these sets are simplicial cones. The issue with efficiency here is how to compute this partition in polynomial time. As we discussed in Remark 2.3, this can be done when k is fixed (or grows very slowly with n), but we do not know how to do this when, say, k = \sqrt{n}.

5 Matching Unique Games hardness

In this section we show that for a fixed positive semi-definite matrix B, approximating Clust(A|B) within a ratio strictly smaller than \frac{R(B)^{2}}{C(B)} is Unique Games hard. We will study functions f : \{1, …, k\}^{n} → and their Fourier spectrum at the first level. A novel feature of our proof is that our Fourier analysis will be carried out with respect to a distribution on {1, …, k} that is not necessarily uniform. In fact, the choice of the distribution itself is dictated by the matrix B as described in Section 5.1.

5.1 Choosing a special probability distribution on {1, …, k}

Fact 5.1. Let B = (b_{ij}) be a k×k symmetric positive semi-definite matrix and b_{ij} = ⟨v_{i}, v_{j}⟩ be its Gram representation, where v_{1}, …, v_{k} are vectors (w.l.o.g.) in ^{k}. Let R(B) be the minimum radius of a Euclidean ball containing all these vectors, and w(B) be the center of this ball. Then w(B) is a convex combination of the v_{i}’s that are on the boundary of the ball. In other words, there exist non-negative coefficients p(1), …, p(k) such that ∑ _{i=1}^{k} p(i) = 1, w(B) = ∑ _{i=1}^{k} p(i)v_{i} and p(i) 0 only if ∥v_{i} − w(B)∥_{2} = R(B).

Fact 5.1 is well known (see for example the proof of Proposition 1.13 in [2]). Its proof is a simple separation argument. Indeed, define J {j ∈ {1, …, k} : ∥v_{j} − w(B)∥_{2} = R(B)} and let K be the convex hull of {v_{j}}_{j∈J}. Assume for the sake of contradiction that w(B) K. Then there would be a hyperplane H separating w(B) from K. Moving w(B) a little in the direction of H would turn the equalities on J to strict inequalities, while preserving the strict inequalities off J. This contradicts the minimality of R(B).

We intend to use the probability distribution (p(1), …, p(k)) from fact 5.1. However, for technical reasons, we need the probability mass for each atom to be non-zero, and therefore, we will use a very small perturbation of this distribution. Towards this end we define μ(i) = (1 − β)p(i) + \frac{β}{k} for every i ∈ \{1, …, k\}. The value of β > 0 is chosen to be sufficiently small as in the following lemma.

Lemma 5.2. Fix any ε > 0 and the matrix B. Then for a sufficiently small β = β(ε, B) > 0,

∑_{i=1}^{k} μ(i) ∥v_{i} − ∑_{j=1}^{k} μ(j)v_{j} ∥_{2}^{2} ≥ R(B)^{2} − ε.  (30)

Proof. Note that if β = 0, then μ(i) = p(i) for all i ∈ {1, …, k}, and

∑_{i=1}^{k} μ(i) ∥v_{i} − ∑_{j=1}^{k} μ(j)v_{j} ∥_{2}^{2} = ∑_{i=1}^{k} p(i)∥v_{i} − w(B)∥_{2}^{2} = R(B)^{2},

since p(i) 0 only if ∥v_{i} − w(B)∥_{2} = R(B). Thus by continuity for sufficiently small β the inequality (30) holds. For concreteness we also give a direct argument which gives a reasonable bound on β. Assume that β < \frac{1}{7}. Then, using the fact that μ ≥ (1 − β)p (point-wise), we see that:

(∑_{i=1}^{k} μ(i) ∥v_{i} − ∑_{j=1}^{k} μ(j)v_{j} ∥_{2}^{2})^{1/2} ≥ \sqrt{1 − β} (∑_{i=1}^{k} p(i) ∥(1 − β) (v_{i} − ∑_{j=1}^{k} p(j)v_{j} ) + \frac{β}{k} ∑_{j=1}^{k} (v_{i} − v_{j})∥ _{2}^{2})^{1/2}

≥ \sqrt{1 − β} (∑_{i=1}^{k} p(i) ∥(1 − β)(v_{i} − w(B))∥_{2}^{2})^{1/2} − \sqrt{1 − β} (∑_{i=1}^{k} p(i) ∥\frac{β}{k} ∑_{j=1}^{k} (v_{i} − v_{j})∥_{2}^{2})^{1/2}

≥ (1 − β)^{3/2}R(B) − β \sqrt{1 − β} (∑_{i=1}^{k} p(i)\frac{1}{k} ∑_{j=1}^{k} ∥v_{i} − v_{j} ∥_{2}^{2})^{1/2}
≥ (1 − β)^{3/2}R(B) − β \sqrt{1 − β} max_{i,j∈\{1,...,k\}}∥v_{i} − v_{j}∥_{2}
≥ \sqrt{1 − β} (1 − 3β) R(B)
≥ \sqrt{1 − 7β} · R(B),

where in the penultimate inequality we used the trivial fact that max_{i,j∈{1,...,k}}∥v_{i} − v_{j}∥_{2} ≤ 2R(B). Thus we can take β = \frac{ε}{7R(B)^{2}} to ensure the validity of (30).

Henceforth we fix the probability space (Ω = {1, …, k}, μ). Let U = (u_{ij}) be a k × k orthogonal matrix such that u_{1j} = \sqrt{μ(j)} for all j ∈ \{1, …, k\} (such an orthogonal matrix exists since this ensures that ∑ _{j=1}^{k} u_{1j}^{2} = 1). Now define random variables X_{1}, …, X_{k} : \{1, …, k\} → by X_{i}(j) = \frac{u_{ij}}{\sqrt{μ(j)}} (here is one place

where we need the atoms of μ to have positive mass. We will also use this fact to allow for the application of the result of [9] in the proof of Theorem 5.4 below). Then by design X_{1} is the constant 1 function, and for all i, j ∈ {1, …, k} we have:

∑_{ℓ=1}^{k} μ(ℓ)X_{i}(ℓ)X_{j}(ℓ) = ∑_{ℓ=1}^{k} u_{iℓ}u_{jℓ} = (UU^{t})_{ij} = δ_{ij},

where δ_{ij} is the Kronecker delta. Similarly:

∑_{ℓ=1}^{k} X_{ℓ}(i)X_{ℓ}(j) = \frac{1}{\sqrt{μ(i)μ(j)}} ∑_{ℓ=1}^{k} u_{ℓi}u_{ℓj} = \frac{(U^{t}U)_{ij}}{\sqrt{μ(i)μ(j)}} = \frac{δ_{ij}}{μ(i)}.

By relabeling these random variables (for the sake for simplicity of later notation) we thus obtain the following lemma:

Lemma 5.3. There exist random variables X_{0}, X_{1}, …, X_{k−1} on Ω such that:

• X_{0} ≡ 1.

• For i, j ∈ {0, …, k − 1} we have

μ[X_{i}X_{j}] = \{ \begin{matrix}0 & if i j, \\ 1 & if i = j. \end{matrix}

• For every ω, ω′ ∈ Ω we have

∑_{i=0}^{k−1} X_{i}(ω)X_{i}(ω′) = \{ \begin{matrix}0 & if ω ω′, \\ \frac{1}{μ(ω)} & if ω = ω′. \end{matrix}

5.2 Dictatorships vs. functions with small influences

In this section we will associate to every function from {1, …, k}^{n} to

Δ_{k} {x ∈ ^{k} : x_{i} ≥ 0 ∀ i ∈ {1, …, k}, ∑_{i=1}^{k} x_{i} = 1}

a numerical parameter, or “objective value”. We will show that the value of this parameter for functions which depend only on a single coordinate (i.e. dictatorships) differs markedly from its value on functions which do not depend significantly on any particular coordinate (i.e. functions with small influences). This step is an analog of the “dictatorship test” which is prevalent in PCP based hardness proofs.

We begin with some notation and preliminaries on Fourier-type expansions. For any function f : ^{n} → Δ_{k} we write f = (f_{1}, f_{2}, …, f_{k}) where f_{i} : ^{n} → [0, 1] and ∑ _{i=1}^{k} f_{i} = 1. With this notation we have

C(B) = sup_{f: ^{k−1}→Δ_{k}} ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨∫_{^{k−1}} xf_{i}(x)dγ_{k−1}(x), ∫_{^{k−1}} xf_{j}(x)dγ_{k−1}(x)⟩

where C(B) is as in Section 2. We have already seen that the supremum above is actually attained. Also C(B) remains the same if the supremum is taken over functions over ^{n} with n ≥ k − 1, i.e. for every n ≥ k − 1,

C(B) = sup_{f: ^{n}→Δ_{k}} ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ⟨∫_{^{n}} xf_{i}(x)dγ_{n}(x), ∫_{^{n}} xf_{j}(x)dγ_{n}(x)⟩.

Let (Ω = {1, …, k}, μ) be the probability space as chosen in Section 5.1. Let (Ω^{n}, μ^{n}) be the associated product space. We will be analyzing functions f : Ω^{n} → Δ_{k} (and more generally into ^{k}). As in Lemma 5.3, fix a basis of orthonormal random variables on Ω where one of them is the constant 1 function, that is {X_{0} ≡ 1, X_{1}, …, X_{k−1}}. Then any function f : Ω → can be written as a linear combination of the X_{i}’s.

In order to analyze functions f : Ω^{n} → , we let X = (X_{1}, X_{2}, …, X_{n}) be an “ensemble” of random variables where for i ∈ {1, …, n} we write X_{i} = {X_{i,0}, X_{i,1}, …, X_{i,k−1}}, and for every i, {X_{i,j}}_{j=0}^{k−1} are independent copies of the {X_{j}}_{j=0}^{k−1}. Any σ = (σ_{1}, σ_{2}, …, σ_{n}) ∈ {0, 1, 2, …, k − 1}^{n} will be called a multi-index. We shall denote by |σ| the number on non-zero entries in σ. Each multi-index defines a monomial

x_{σ} := ∏_{\begin{matrix}i∈\{1,...,n\} \\ σ_{i} 0 \end{matrix}}x_{i,σ_{i}}

on a set of n(k − 1) indeterminates {x_{ij} | i ∈ {1, …, n}, j ∈ {1, 2, …, k − 1}}, and also a random variable X_{σ} : Ω^{n} → as

X_{σ}(ω) := ∏_{i=1}^{n} X_{i,σ_{i}} (ω_{i}).

The random variables {X_{σ}}_{σ} form an orthonormal basis for the space of functions f : Ω^{n} → . Thus, every such f can be written uniquely as (the “Fourier expansion”)

f = ∑_{σ} f̂(σ)X_{σ}, f̂(σ) ∈ .

We denote the corresponding multi-linear polynomial as Q_{f} = ∑ _{σ} f̂(σ)x_{σ}. One can think of f as the polynomial Q_{f} applied to the ensemble X, i.e. f = Q_{f} (X). Of course, one can also apply Q_{f} to any other ensemble, and specifically to the Gaussian ensemble G = (G_{1}, G_{2}, …, G_{n}) where G_{i} = {G_{i,0} ≡ 1, G_{i,1}, …, G_{i,k−1}} and G_{i,j}, i ∈ {1, …, n}, j ∈ {1, …, k − 1} are i.i.d. standard Gaussians. Define the influence of the i’th variable on f as

Inf_{i}(f) ∑_{σ_{i} 0} f̂(σ)^{2}.

Roughly speaking, the results of [13, 9] say that if f : Ω^{n} → [0, 1] is a function all of whose influences are small, then f = Q_{f} (X) and Q_{f} (G) are almost identically distributed, and in particular, the values of Q_{f} (G) are essentially contained in [0, 1]. Note that Q_{f} (G) is a random variable on the probability space ( ^{n(k−1)}, γ_{n(k−1)}).

Consider functions f : Ω^{n} → Δ_{k}. We write f = (f_{1}, f_{2}, …, f_{k}) where f_{i} : Ω^{n} → [0, 1] with ∑ _{i=1}^{k} f_{i} = 1. Each f_{i} has a unique representation (along with the corresponding multi-linear polynomial)

f_{i} = ∑_{σ} f̂_{i}(σ)X_{σ}, Q_{i} := Q_{f_{i}} = ∑_{σ} f̂_{i}(σ)x_{σ}.

We shall define an objective function OBJ(f) that is a positive semidefinite quadratic form on the table of values of f which corresponds to a centered symmetric positive semidefinite bilinear form. Then we analyze the value of this objective function when f is a “dictatorship” versus when f has all low influences.

The objective value

For a function f : Ω^{n} → Δ_{k} (or more generally, f : Ω^{n} → ^{k}) define

OBJ(f) := ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ( ∑_{σ: |σ|=1} f̂_{i}(σ)f̂_{j} (σ)) .  (31)

Note that there are n(k − 1) multi-indices σ such that |σ| = 1.

The objective value for dictatorships

For ℓ ∈ {1, …, n} we define a dictatorship function f^{dict,ℓ}: Ω^{n} → Δ_{k} as follows. The range of the function is limited to only k points in Δ_{k}, namely the points {e_{1}, e_{2}, …, e_{k}} where e_{i} is a vector with i^{th}coordinate 1 and all other coordinates zero.

f^{dict,ℓ}(ω) := e_{i} if ω_{ℓ} = i.  (32)

In other words, when one writes f^{dict,ℓ}= (f_{1}, f_{2}, …, f_{k}), for i ∈ {1, …, k}, f_{i} is {0, 1}-valued and f_{i}(ω) = 1 if and only if ω_{ℓ} = i. The Fourier expansion of f_{i} is

f_{i}(ω) = μ(i) ∑_{σ: σ_{j}=0 ∀j ℓ} X_{σ_{ℓ}}(i) X_{σ}(ω).  (33)

Indeed, the right hand side of (33) equals

μ(i) ∑_{0≤σ_{ℓ}≤k−1} X_{σ_{ℓ}}(i) X_{σ_{ℓ}}(ω_{ℓ}) = \{ \begin{matrix}1 if ω_{ℓ} = i, \\ 0 otherwise. (see Lemma 5.3) \end{matrix}

Thus,

OBJ(f^{dict,ℓ}) = ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ( ∑_{σ: |σ|=1} f̂_{i}(σ)f̂_{j} (σ))

= ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} (∑_{r=1}^{k−1} μ(i)X_{r}(i)μ(j)X_{r}(j))

= ∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} · μ(i)μ(j) (∑_{r=0}^{k−1} X_{r}(i)X_{r}(j) − 1)

= ∑_{\begin{matrix}i,j∈\{1,...,k\} \\ i j \end{matrix}}⟨v_{i}, v_{j}⟩ · μ(i)μ(j)(−1) + ∑_{i=1}^{k} ⟨v_{i}, v_{i}⟩ · μ(i)^{2} (\frac{1}{μ(i)} − 1)

= ∑_{i=1}^{k} μ(i) ∥v_{i} − ∑_{j=1}^{k} μ(j)v_{j} ∥_{2}^{2}
≥ R(B)^{2} − ε,  (34)

using Lemma 5.2.

The objective value for functions with low influences

For f : Ω^{n} → , j ∈ {1, …, n} and m ∈ denote (the “degree m-influence” of f):

Inf_{j}^{≤m}(f) ∑_{\begin{matrix}|σ|≤m \\ σ_{j} 0 \end{matrix}} f̂(σ)^{2}.

For every 0 ≤ ρ ≤ 1 we will use the smoothing operator:

T_{ρ}f = ∑_{σ} ρ^{|σ|}f̂(σ)X_{σ}.

Equivalently,

T_{ρ}f (ω_{1}, …, ω_{n}) = [f (ω′_{1}, …, ω′_{n})],

where independently for each i, ω′_{i} is chosen to be ω_{i} with probability ρ and a random (with respect to the underlying distribution μ) element in Ω with probability 1 − ρ.

The following theorem is the key analytic fact used in our UGC hardness result:

Theorem 5.4. For every ε > 0, there exists τ > 0 so that the following holds: for any function f : Ω^{n} → Δ_{k} which satisfies

∀ i ∈ {1, …, k}, ∀ j ∈ {1, …, n}, Inf_{j}^{≤log(1/τ)}(f_{i}) ≤ τ

we have,

OBJ(f) ≤ C(B) + ε.

Proof. Let δ, η > 0 be sufficiently small constants to be chosen later. Let Q_{i} = Q_{f_{i}} be the multi-linear polynomial associated with f_{i}. Recall that Q_{i} is a multi-linear polynomial in the n(k − 1) indeterminates {x_{jp} | j ∈ {1, …, n}, p ∈ {1, …, k − 1}} . Moreover f_{i} = Q_{i}(X) has range [0, 1] and ∑ _{i=1}^{k} f_{i} = 1.

Let R_{i} = (T_{1−δ}Q_{i})(X) and S_{i} = (T_{1−δ}Q_{i})(G) (the smoothening operator T_{1−δ} helps us meet some technical pre-conditions before applying the invariance principle of [9]). Note that R_{i} has range [0, 1] and S_{i} has range . It will follow however from [9] that S_{i} is essentially in [0, 1]. First we relate OBJ(f) to the functions S_{i} which will, up to truncation, induce a partition of ^{n(k−1)}, which in turn will give the bound in terms of C(B).

(1 − δ)^{2} · OBJ(f) = (1 − δ)^{2} ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ} ∑_{σ:|σ|=1} f̂_{i}(σ)f̂_{ℓ}(σ)

= (1 − δ)^{2} ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ} ∑_{j=1}^{n} ∑_{p=1}^{k−1} (∫_{^{n(k−1)}} x_{jp} Q_{i}(x)dγ_{n(k−1)}(x))· (∫_{^{n(k−1)}} x_{jp} Q_{ℓ}(x)dγ_{n(k−1)}(x))

= (1 − δ)^{2} ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨∫_{^{n(k−1)}} x Q_{i}(x)dγ_{n(k−1)}(x), ∫_{^{n(k−1)}} x Q_{ℓ}(x)dγ_{n(k−1)}(x)⟩

= ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨∫_{^{n(k−1)}} x (T_{1−δ}Q_{i})(x)dγ_{n(k−1)}(x), ∫_{^{n(k−1)}} x (T_{1−δ}Q_{ℓ})(x)dγ_{n(k−1)}(x)⟩

= ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨∫_{^{n(k−1)}} x S_{i}(x)dγ_{n(k−1)}(x), ∫_{^{n(k−1)}} x S_{ℓ}(x)dγ_{n(k−1)}(x)⟩.  (35)

We shall now bound the last term above by C(B) + o(1). For any real-valued function h on ^{n(k−1)}, let

chop(h)(x) := \{ \begin{matrix}0 & if h(x) < 0, \\ h(x) & if h(x) ∈ [0, 1], \\ 1 & if h(x) > 1. \end{matrix}

Applying Theorem 3.20 in [9] to the polynomial Q_{i}, it follows that (provided τ is sufficiently small compared to δ and η),

∥S_{i} − chop(S_{i})∥ _{L_{2}(γ_{n(k−1)})}^{2} = ∫_{^{n(k−1)}} |S_{i}(x) − chop(S_{i})(x)|^{2} dγ_{n(k−1)}(x) ≤ η.  (36)

The functions chop(S_{i}) are almost what we want except that they might not sum up to 1. So further define

S_{i}^{∗}(x) := \frac{chop(S_{i})(x)}{∑ _{i=1}^{k} chop(S_{i})(x)}.

Clearly, {S_{i}^{∗}}_{i=1}^{k} have range [0, 1] and ∑ _{i=1}^{k} S_{i}^{∗} ≡ 1. Observe that the following holds point-wise:

∑_{j=1}^{k} |chop(S_{j}) − S_{j}^{∗}| = |∑_{j=1}^{k} chop(S_{j}) − 1| = |∑_{j=1}^{k} chop(S_{j}) − ∑_{j=1}^{k} S_{j} | ≤ ∑_{j=1}^{k} |S_{j} − chop(S_{j})| ,

where we used that ∑ _{j=1}^{k} S_{j} = T_{1−δ} ∑ _{j=1}^{k} Q_{j} = T_{1−δ}1 = 1. It follows that for all i ∈ {1, …, k} we have:

∥chop(S_{i}) − S_{i}^{∗}∥_{L_{2}(γ_{n(k−1)})} ≤ ∑_{j=1}^{k} ∥chop(S_{j}) − S_{j}^{∗}∥_{L_{2}(γ_{n(k−1)})} ≤ ∑_{j=1}^{k} ∥S_{j} − chop(S_{j})∥_{L_{2}(γ_{n(k−1)})} ≤ k \sqrt{η},

where we used (36). Finally,

∥S_{i} − S_{i}^{∗}∥_{L_{2}(γ_{n(k−1)})} ≤ ∥S_{i} − chop(S_{i})∥_{L_{2}(γ_{n(k−1)})} + ∥chop(S_{i}) − S_{i}^{∗}∥_{L_{2}(γ_{n(k−1)})} ≤ (k + 1) \sqrt{η}.  (37)

Now write

u_{i} = ∫_{^{n(k−1)}} x S_{i}(x)dγ_{n(k−1)}(x),  w_{i} = ∫_{^{n(k−1)}} x S_{i}^{∗}(x)dγ_{n(k−1)}(x).  (38)

The norm of u_{i} − w_{i} is bounded by (k + 1) \sqrt{η} using (37) and Lemma 5.5 below. Since |S_{i}^{∗}| ≤ 1, the norm of w_{i} is bounded by 1. Returning to the estimation in Equation (35) and applying Lemma 5.6 below, we see that:

(1 − δ)^{2} · OBJ(f) = ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨u_{i}, u_{ℓ}⟩ ≤ ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨w_{i}, w_{ℓ}⟩ + O (k \sqrt{η})(∑_{i=1}^{k} ∑_{ℓ=1}^{k} |b_{iℓ}|).

Since ∑ _{i=1}^{k} S_{i}^{∗} ≡ 1 we have

∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨w_{i}, w_{ℓ}⟩ = ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨∫_{^{n(k−1)}} x S_{i}^{∗}(x)dγ_{n(k−1)}(x), ∫_{^{n(k−1)}} x S_{ℓ}^{∗}(x)dγ_{n(k−1)}(x)⟩

≤ sup_{f: ^{n(k−1)}→Δ_{k}} (∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨∫_{^{n(k−1)}} x f_{i}(x)dγ_{n(k−1)}(x), ∫_{^{n(k−1)}} x f_{ℓ}(x)dγ_{n(k−1)}(x)⟩)= C(B).

It follows that OBJ(f) ≤ C(B) + ε, provided that η and δ are small enough.

Lemma 5.5. Let g ∈ L_{2}( ^{n}, γ_{n}). Then

∥∫_{^{n}} x g(x)dγ_{n}(x)∥_{2} ≤ ∥g∥_{L_{2}( ^{n},γ_{n})}.

Proof. Note that the square of the left hand side equals

∑_{i=1}^{n} |∫_{^{n}} x_{i} g(x)dγ_{n}(x)|^{2} = ∑_{i=1}^{n} ⟨x_{i}, g⟩^{2}.

Since x_{i} ∈ L_{2}( ^{n}, γ_{n}) are an orthonormal set of functions, the sum of squares of projections of g onto them is at most the squared norm of g.

Lemma 5.6. Suppose {u_{i}}_{i=1}^{k} and {w_{i}}_{i=1}^{k} are vectors in ^{n} such that ∥u_{i} − w_{i}∥_{2} ≤ d for every i ∈ {1, …, k} and ∥w_{i}∥_{2} ≤ 1. Let B = (b_{ij}) be a k × k matrix. Then

|∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨u_{i}, u_{ℓ}⟩ − ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨w_{i}, w_{ℓ}⟩| ≤ (2d + d^{2}) ∑_{i=1}^{k} ∑_{ℓ=1}^{k} |b_{iℓ}|.

Proof. From the given conditions on the norms of a_{i} = u_{i}− w_{i} and w_{i}, it follows that for any i, ℓ ∈ {1, …, k},

|⟨u_{i}, u_{ℓ}⟩ − ⟨w_{i}, w_{ℓ}⟩|≤ |⟨a_{i}, w_{ℓ}⟩| + |⟨a_{ℓ}, w_{i}⟩| + |⟨a_{i}, a_{ℓ}⟩| ≤ 2d + d^{2}.

Hence,

|∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨u_{i}, u_{ℓ}⟩ − ∑_{i=1}^{k} ∑_{ℓ=1}^{k} b_{iℓ}⟨w_{i}, w_{ℓ}⟩| ≤ ∑_{i=1}^{k} ∑_{ℓ=1}^{k} |b_{iℓ}| |⟨u_{i}, u_{ℓ}⟩ − ⟨w_{i}, w_{ℓ}⟩|≤ (2d + d^{2}) ∑_{i=1}^{k} ∑_{ℓ=1}^{k} |b_{iℓ}|,

as required.

The intended hardness factor

As we show next, the dictatorship test can be translated (in a more or less standard way by now) into a Unique Games hardness result. The hardness factor (as usual) turns out to be the ratio of the objective value when the function is a dictatorship versus when the function has all low influences, i.e.

\frac{R(B)^{2} − ε}{C(B) + ε} = \frac{R(B)^{2}}{C(B)}− o(1).

5.3 The reduction from unique games to kernel clustering

Given a Unique Games Instance L(G(V, W, E), n, {π_{vw}}_{(v,w)∈E}), we construct an instance of the clustering problem.

Reformulation of the clustering problem

As in our earlier paper [7], we first reformulate the kernel clustering problem for the ease of presentation. As observed there, we can reformulate it as (the matrix A in the problem Clust(A|B) is captured by the quadratic form Q below):

Kernel Clustering Problem: Given a k × k symmetric positive semidefinite matrix B, and a symmetric positive semidefinite quadratic form Q(·, ·) on ^{N} × ^{N}, find F : {1, …, N} → Δ_{k}, F = (F_{1}, F_{2}, …, F_{k}), so as to maximize ∑ _{i=1}^{k} ∑ _{j=1}^{k} b_{ij}Q(F_{i}, F_{j}).

The clustering problem instance

Given a Unique Games instance ℒ (G(V, W, E), n, {π_{vw}}_{(v,w)∈E}) , the clustering problem is to find a function F : W ×Ω^{n} → Δ_{k} so as to maximize ∑ _{i=1}^{k} ∑ _{j=1}^{k} b_{ij}Q(F_{i}, F_{i}) where Q is a suitably defined symmetric positive semidefinite quadratic form. For notational convenience, we write:

F_{w} := F(w, ·), F_{w} : Ω^{n} → Δ_{k}.

Also, for every v ∈ V, we write:

F_{v} _{(v,w)∈E}[F_{w} ∘ π_{vw}], F_{v} : Ω^{n} → Δ_{k}.

We used the following notation: for any function g : Ω^{n} → Δ_{k} and π : {1, …, n} → {1, …, n} we write g ∘ π : Ω^{n} → Δ_{k} for the function (g ∘ π)(ω) := g(ω_{π(1)}, ω_{π(2)}, …, ω_{π(n)}). As usual, we denote F_{w} = (F_{w,1}, F_{w,2}, …, F_{w,k}) where each F_{w,i}has range [0, 1] and ∑ _{i=1}^{k} F_{w,i} = 1. Similarly, F_{v} = (F_{v,1}, F_{v,2}, …, F_{v,k}) and ∑ _{i=1}^{k} F_{v,i} = 1. Now we are ready to define the clustering problem instance.

Clustering instance: The goal is to find F : W × Ω^{n} → Δ_{k} so as to maximize:

max_{F:W×Ω^{n}→Δ_{k}}  _{v∈V}[OBJ(F_{v})] = max_{F:W×Ω^{n}→Δ_{k}}  _{v∈V} [∑_{i=1}^{k} ∑_{j=1}^{k} b_{ij} ∑_{σ:|σ|=1} F̂_{v,i}(σ) · F̂_{v,j}(σ)].  (39)

Completeness

We will show that if the Unique Games instance has an almost satisfying labeling, then the objective value of the clustering problem is at least R(B)^{2} − o(1). So, let ρ : V ∪ W → {1, …, n} be the labeling, such that for at least 1 − ε fraction of the vertices v ∈ V (call such v good) we have

π_{vw}(ρ(w)) = ρ(v) ∀ (v, w) ∈ E.

Define F : W × Ω^{n} → Δ_{k} as follows: for every w ∈ W, F_{w} : Ω^{n} → Δ_{k} equals the dictatorship corresponding to ρ(w) ∈ {1, …, n}, i.e.,

F_{w} := f^{dict,ρ(w)}.

Lemma 5.7 ([7]). For a good v ∈ V we have F_{v} = f^{dict,ρ(v)}.

Thus the contribution of v in (39) is OBJ(f^{dict,ρ(v)}) ≥ R(B)^{2}− ε as observed in Equation (34). Since 1 − ε fraction of v ∈ V are good, (39) is at least (1 − ε) · (R(B)^{2} − ε) = R(B)^{2} − o(1).

Soundness

Suppose for the sake of contradiction that the value of (39) is at least C(B) + 2ε. As in [7], it can be proved that the Unique Games instance must have a labeling that satisfies at least a constant fraction of its edges, the constant depending on the parameter τ used in Theorem 5.4. This is a contradiction, provided the soundness of the Unique Games instance is chosen to be even lower to begin with. The proof is the same as in [7], by replacing the C(k) therein by C(B) ([7] focused on the case when B is the k × k identity matrix. The constant C(k) therein is same as our constant C(B) when B is the k × k identity matrix).

6 A concrete example

In this section we will use our results to evaluate the UGC hardness threshold of the problem of computing

Clust (A | (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & c \end{matrix})),  (40)

where A ∈ M_{n}( ) is centered, symmetric and positive semidefinite and c ∈ (0, ∞) is a parameter. The case c = 1, corresponding to B = I_{3} (the 3 × 3 identity matrix) was evaluated in [7], where it was shown that the UGC hardness threshold in this case equals \frac{16π}{27}.

For general c > 0 the optimization problem in (40) corresponds to the following question: given n random variables X_{1}, …, X_{n} the goal is to partition them into three sets S_{1}, S_{2}, S_{3} ⊆ {1, …, n} such that

∑_{i,j∈S_{1}} [X_{i}X_{j}]+ ∑_{i,j∈S_{2}} [X_{i}X_{j}]+ c ∑_{i,j∈S_{3}} [X_{i}X_{j}]  (41)

is maximized. Thus we wish to cluster the variables into three clusters so as to maximize the intra-cluster correlations, while the parameter c allows us to tune the relative importance of one of the clusters. We stress that we do not claim that this optimization problem is of particular intrinsic importance. We chose it as a way to concretely demonstrate our results for the simplest possible perturbation of the case of B = I_{3}. We remark that it is also possible to explicitly solve the case of general 3 × 3 diagonal matrices B, i.e., the case of a general weighting of the clusters in (41). The formula for the UGC hardness threshold for general 3 × 3 diagonal matrices turns out to be quite complicated, so we chose to deal only with (40) as a simple example for the sake of illustration. Note that for 3 × 3 matrices the characterization of C(B) in terms of planar conical partitions is particularly simple, and allows for explicit computations of the UGC hardness threshold in additional cases.

Denote B (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & c \end{matrix}) = (⟨v_{i}, v_{j}⟩)_{i,j=1}^{3} , where v_{1} = (1, 0, 0), v_{2} = (0, 1, 0), v_{3} = (0, 0, \sqrt{c}) ∈ ^{3}. The side

lengths of the triangle whose vertices are v_{1}, v_{2}, v_{3} are \{ℓ_{1} = \sqrt{1 + c}, ℓ_{2} = \sqrt{1 + c}, ℓ_{3} = \sqrt{2}\}. Note that this is an acute triangle, so its smallest bounding circle coincides with its circumcircle, and therefore its radius is given by [5]:

R(B)^{2} = \frac{ℓ_{1}^{2}ℓ_{2}^{2}ℓ_{3}^{2}}{(ℓ_{1} + ℓ_{2} + ℓ_{3})(−ℓ_{1} + ℓ_{2} + ℓ_{3})(ℓ_{1} − ℓ_{2} + ℓ_{3})(ℓ_{1} + ℓ_{2} − ℓ_{3})} = \frac{(1 + c)^{2}}{2 + 4c} .  (42)

We shall now compute C(B). By Lemma 2.3 the partition {A_{1}, A_{2}, A_{3}} of ^{2} at which C(B) is attained consists of disjoint cones of angles α_{1}, α_{2}, α_{3} ∈ [0, 2π] where α_{1} + α_{2} + α_{3} = 2π. A direct computation shows that for j ∈ {1, 2, 3} we have:

∥∫_{A_{j}} xdγ_{2}(x)∥_{2}^{2} = \frac{1}{2π} sin^{2} (\frac{α_{j}}{2} ).

Hence

C(B) = \frac{1}{2π} max_{\begin{matrix}α_{1},α_{2},α_{3}∈[0,2π] \\ α_{1}+α_{2}+α_{3}=2π \end{matrix}} (sin^{2} (\frac{α_{1}}{2} ) + sin^{2} (\frac{α_{2}}{2} ) + c sin^{2} (\frac{α_{3}}{2} )) .  (43)

Assume for the moment that the maximum in (43)is attained when α_{1}, α_{2}, α_{3} ∈ (0, 2π). Then using Lagrange multipliers we see that sinα_{1} = sinα_{2} = c sinα_{3}. This implies in particular that either α_{1} = α_{2} or (since α_{1}, α_{2}, α_{3} ∈ (0, 2π) and α_{1} + α_{2} + α_{3} = 2π) α_{1} + α_{2} = π. In the latter case α_{3} = π, and it follows from the Lagrange multiplier equations that sinα_{1} = sinα_{2} = 0, which forces one of {α_{1}, α_{2}} to vanish, contrary to our assumption. Hence we know that α_{1} = α_{2} α. Then α_{3} = 2π − 2α, and since α_{3} ∈ (0, 2π) we also know that α ∈ (0, π). The Lagrange multiplier equations imply that sinα = c sin(2π − 2α) = −2c sinα cosα. Thus cosα = −\frac{1}{2c}, and in particular we see that necessarily c ≥ \frac{1}{2}. It follows that

sin^{2} (\frac{α}{2}) = \frac{1 − cosα}{2} = \frac{2c + 1}{4c} ,

and

sin^{2} (\frac{α_{3}}{2} ) = sin^{2} (π − α) = 1 − cos^{2} α = 1 − \frac{1}{4c^{2}}.

Hence in this case:

sin^{2} (\frac{α_{1}}{2} ) + sin^{2} (\frac{α_{2}}{2} ) + c sin^{2} (\frac{α_{3}}{2} ) = 2\frac{2c + 1}{4c} + c\frac{4c^{2} − 1}{4c^{2}} = \frac{(2c + 1)^{2}}{4c} .  (44)

It remains to deal with the boundary case {α_{1}, α_{2}, α_{3}} ∩ {0, 2π} ∅, which as we have seen above is where the maximum in (43) is necessarily attained if c < \frac{1}{2}. If one of \{α_{1}, α_{2}, α_{3}\} equals 2π then the others must vanish, in which case sin^{2} (\frac{α_{1}}{2} )+ sin^{2} (\frac{α_{2}}{2} )+ c sin^{2} (\frac{α_{3}}{2} ) = 0. If one of \{α_{1}, α_{2}, α_{3}\} vanishes then in order to maximize sin^{2} (\frac{α_{1}}{2} )+ sin^{2} (\frac{α_{2}}{2} )+ c sin^{2} (\frac{α_{3}}{2} ) the other two must equal π, in which case the maximum value

of this quantity is max\{2, 1 + c\}. Since max\{2, 1 + c\} never exceeds the quantity \frac{(2c+1)^{2}}{4c} from (44) it follows that the maximum of sin^{2} (\frac{α_{1}}{2} )+ sin^{2} (\frac{α_{2}}{2} )+ c sin^{2} (\frac{α_{3}}{2} )over \{α_{1}+ α_{2}+ α_{3} = 2π ∧ α_{1}, α_{2}, α_{3} ∈ [0, 2π]\} equals

\frac{(2c+1)^{2}}{4c} when c ≥ \frac{1}{2} and equals 2 when c ≤ \frac{1}{2}. We therefore proved that

C(B) = \{ \begin{matrix}\frac{(2c+1)^{2}}{8πc} & if c ≥ \frac{1}{2}, \\ \frac{1}{π} & if c ≤ \frac{1}{2}. \end{matrix}  (45)

By combining (42) with (45) we conclude that the UGC hardness threshold for computing (40) is:

\frac{R(B)^{2}}{C(B)} = \{ \begin{matrix}\frac{4πc(1+c)^{2}}{(1+2c)^{3}} & if c ≥ \frac{1}{2}, \\ \frac{π(1+c)^{2}}{2+4c} & if c ≤ \frac{1}{2}. \end{matrix}  (46)

Remark 6.1. An inspection of the above argument, in combination with our algorithm that was presented in Section 4, shows that the phase transition in (46) at c = \frac{1}{2} corresponds to a qualitative change in the optimal algorithm: after shifting the vectors \{v_{1}, …, v_{k}\} so that w(B) = 0 and renormalizing by R(B), for c > \frac{1}{2} the algorithm projects the points obtained from the SDP to ^{2} and classifies them according to a partition of ^{2} into three cones of positive measure, while for c < \frac{1}{2} the partitioning is into two half-planes and the third set (the one weighted by c) is empty.

Acknowledgements

We are grateful to Uri Feige for several helpful suggestions.

References

[1] G. E. Andrews, R. Askey, and R. Roy. Special functions, volume 71 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1999.

[2] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[3] M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for unique games (extended abstract). In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 205–214, New York, 2006. ACM.

[4] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.

[5] R. A. Johnson. Advanced Euclidean geometry: An elementary treatise on the geometry of the triangle and the circle. Under the editorship of John Wesley Young. Dover Publications Inc., New York, 1960.

[6] S. Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 767–775 (electronic), New York, 2002. ACM.

[7] S. Khot and A. Naor. Approximate kernel clustering. In 49th Annual IEEE Symposium on Foundations of Computer Science, pages 561–570. IEEE Computer Society, 2008.

[8] S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2 − ϵ. J. Comput. System Sci., 74(3):335–349, 2008.

[9] E. Mossel, R. O’Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. In 46th Annual Symposium on Foundations of Computer Science, pages 21–30. IEEE Computer Society, 2005.

[10] G. Pisier. The volume of convex bodies and Banach space geometry, volume 94 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1989.

[11] P. Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 245–254, 2008.

[12] R. E. Rietz. A proof of the Grothendieck inequality. Israel J. Math., 19:271–276, 1974.

[13] V. I. Rotar′. Limit theorems for polylinear forms. J. Multivariate Anal., 9(4):511–530, 1979.

[14] L. Song, A. Smola, A. Gretton, and K. A. Borgwardt. A dependence maximization view of clustering. In Proceedings of the 24th international conference on Machine learning, pages 815 – 822, 2007.

[15] E. M. Stein. Harmonic analysis: real-variable methods, orthogonality, and oscillatory integrals, volume 43 of Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1993. With the assistance of Timothy S. Murphy, Monographs in Harmonic Analysis, III.