Approximate kernel clustering

Subhash Khot^{∗}

Courant Institute of Mathematical Sciences

          khot@cims.nyu.edu

Assaf Naor^{†} Courant Institute of Mathematical Sciences

                                               naor@cims.nyu.edu

Abstract

In the kernel clustering problem we are given a large n × n positive semi-definite matrix A = (a_{ij}) with ∑ _{i,j=1}^{n} a_{ij} = 0 and a small k × k positive semi-definite matrix B = (b_{ij}). The goal is to find a partition S_{1}, …, S_{k} of {1, …n} which maximizes the quantity

∑_{i,j=1}^{k} ( ∑_{(p,q)∈S_{i}×S_{j}} a_{pq})b_{ij}.

We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm for this problem, answering a question posed by Song, Smola, Gretton and Borgwardt. In some cases we manage to compute the sharp approximation threshold for this problem assuming the Unique Games Conjecture (UGC). In particular, when B is the 3 × 3 identity matrix the UGC hardness threshold of this problem is exactly \frac{16π}{27}. We present and study a geometric conjecture of independent interest which we show would imply that the UGC threshold when B is the k × k identity matrix is \frac{8π}{9} (1 − \frac{1}{k}) for every k ≥ 3.

1 Introduction

This paper is devoted to an investigation of the polynomial time approximability of a generic clustering problem which originates in the theory of machine learning. In doing so, we uncover a connection with a continuous geometric/analytic problem which is of independent interest. In [24] Song, Smola, Gretton and Borgwardt introduced the following framework for kernel clustering problems. Assume that we are given a centered kernel, i.e. an n × n positive semidefinite matrix A = (a_{ij}) with real entries such that ∑ _{i,j=1}^{n} a_{ij} = 0 (the assumption that the kernel is centered is a commonly used normalization in learning theory—see [23] for more information on this topic). Such matrices arise, for example, as correlation matrices of random variables (X_{1}, …, X_{n}) that measure attributes of certain empirical data, i.e. a_{ij} = [X_{i}X_{j}]. We think of n as very large, and our goal is to “cluster” the matrix A to a much smaller k × k matrix in such a way that certain features could still be extracted from the clustered matrix. Formally, given a partition of {1, …, n} into k sets S_{1}, …, S_{k}, define the clustering of A with respect to this partition to be the k × k matrix, whose (i, j)^{th} entry is

∑_{(p,q)∈S_{i}×S_{j}} a_{pq}.  (1)

∗Research supported in part by NSF CARREER award CCF-0643626, and a Microsoft New Faculty Fellowship.

†Research supported by NSF grants CCF-0635078 and DMS-0528387.

Let A(S_{1}, …, S_{k}) denote the k × k matrix given by (1). In the kernel clustering problem, we are given a positive semidefinite k × k matrix B = (b_{ij}), and we wish to find the clustering A(S_{1}, …, S_{k}) = C = (c_{ij}) of A, which is most similar to B in the sense that ∑ _{i,j=1}^{k} c_{ij}b_{ij}, i.e its scalar product with B, is as large as possible. In other words, our goal is to compute the number (and the corresponding partition):

Clust(A|B)  max { ∑_{i,j=1}^{k} ( ∑_{(p,q)∈S_{i}×S_{j}} a_{pq})b_{ij} : {S_{1}, …, S_{k}} is a partition of {1, …, n}}

= max { ∑_{i,j=1}^{k} A(S_{1}, …, S_{k})_{ij} · b_{ij} : {S_{1}, …, S_{k}} is a partition of {1, …, n}}

= max { ∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} : σ : {1, …, n} → {1, …, k}}.  (2)

The flexibility in the above formulation of the kernel clustering problem is clearly in the choice of comparison matrix B, which allows us to enforce a wide-range of clustering criteria. Using the statistical interpretation of (a_{ij}) as a correlation matrix, we can think of the matrix B as encoding our belief/hypothesis that the empirical data has a certain structure, and the kernel clustering problem aims to efficiently expose this structure.

Several explicit examples of useful “test matrices” B are discussed in [24], including hierarchical clustering and clustering data on certain manifolds. We refer to [24] for additional information which illustrates the versatility of this general clustering problem, including its relation to the Hilbert Schmidt Independence Criterion (HSIC) and various experimental results. In [24] it was asked if there is a polynomial time approximation algorithm for computing Clust(A|B). Here we obtain a constant factor approximation algorithm for this problem, and prove some computational hardness of approximation results.

Before stating our results in full generality we shall now present a few simple illustrative examples. If B = I_{k} is the k × k identity matrix, then thinking once more of a_{ij} as correlations [X_{i}X_{j}], our goal is to find a partition S_{1}, …, S_{k} of {1, …, n} which maximizes the quantity

∑_{i=1}^{k} ∑_{p,q∈S_{i}} [X_{p}X_{q}],

i.e. we wish to cluster the variables so as to maximize the total intra-cluster correlations. As we shall see below, our results yield a polynomial time algorithm which approximates Clust(A|I_{k}) up to a factor of \frac{8π}{9} (1 − \frac{1}{k}). In particular, when k = 3 we obtain a \frac{16π}{27} approximation algorithm, and we show that assuming the Unique Games Conjecture (UGC) no polynomial time algorithm can achieve an approximation guarantee which is smaller than \frac{16π}{27}. The Unique Games Conjecture was posed by Khot in [14], and it will be described momentarily. For the readers who are not familiar with this computational hypothesis and its remarkable applications to hardness of approximation, it suffices to say that this hardness result should be viewed as strong evidence that \frac{16π}{27} is the sharp threshold below which no polynomial time algorithm can solve the kernel clustering problem when B = I_{3}. Moreover, we conjecture that \frac{8π}{9} (1 − \frac{1}{k}) is the sharp approximability threshold (assuming UGC) for Clust(A|I_{k}) for every k ≥ 3. In this paper, we reduce this conjecture to a purely geometric/analytic conjecture, which we will describe in detail later, and prove some partial results about it.

Another illustrative example of the kernel clustering problem is the case

B = (\begin{matrix}1 & −1 \\ −1 & 1 \end{matrix}).

In this case, we clearly have

Clust (A |(\begin{matrix}1 & −1 \\ −1 & 1 \end{matrix}))= max \{ ∑_{i,j=1}^{n} : a_{ij}ε_{i}ε_{j} : ε_{1}, …, ε_{n} ∈ \{−1, 1\}\}.  (3)

The optimization problem in (3) is well known as the positive semi-definite Grothendieck problem and has several algorithmic applications (see [21, 19, 2, 6]). It has been shown by Rietz [21] that the natural semidefinite relaxation of (3) has integrality gap \frac{π}{2} (see also Nesterov’s work [19]). Our results imply that assuming the UGC \frac{π}{2} is the sharp approximation threshold for the positive-semidefinite Grothendieck problem. Note that without the assumption that A is positive semidefinite the natural semidefinite relaxation of (3) has integrality gap Θ(logn). See [18, 7, 1] for more information, and [3] for hardness results for this problem.

We can also view the problem (3) as a generalization of the MaxCut problem. Indeed, let G = (V = {1, …, n}, E) be an n-vertex loop-free graph. For every vertex i ∈ V let d_{i} denote its degree in G. Let A be the Laplacian of G, i.e. A is the n × n matrix given by

a_{ij} = \{ \begin{matrix}d_{i} & if i = j, \\ −1 & if i j ∧ ij ∈ E, \\ 0 & if i j ∧ ij E. \end{matrix}  (4)

Then A is positive semi-definite since it is diagonally dominant. For every ε_{1}, …, ε_{n} ∈ {−1, 1} let S ⊆ V be the set S {i ∈ V : ε_{i} = 1}. Then:

∑_{i,j=1}^{n} a_{ij}ε_{i}ε_{j} = ∑_{i=1}^{n} d_{i} − 2|E(S, S)| − 2|E(V \ S, V \ S)| + 2|E(S, V \ S)|

= 2|E| − 2 (|E| − |E(S, V \ S)|)+ 2|E(S, V \ S)| = 4|E(S, V \ S)|. (5)

Hence

Clust (A |(\begin{matrix}1 & −1 \\ −1 & 1 \end{matrix}))= 4MaxCut(G).

Using H�stad’s inapproximability result for MaxCut [12] it follows that if P NP there is no polynomial time algorithm which approximates (3) up to a factor smaller than \frac{17}{16}.

Our algorithmic results. For a fixed positive semidefinite matrix B, the approximability threshold for the problem of computing Clust(A|B) depends on B. It is therefore of interest to study the performance of our algorithms in terms of the matrix B. We do obtain bounds which depend on B (which are probably suboptimal in general)—the precise statements are contained in Theorem 2.1and Theorem 2.3. For the sake of simplicity, in the introduction we state bounds which are independent of B. We believe that the problem of computing the approximation threshold (perhaps under UGC) for each fixed B is an interesting problem which deserves further research.

If A is centered, i.e. ∑ _{i,j=1}^{n} a_{ij} = 0, then for every k × k positive semi-definite matrix B our algorithm achieves an approximation ratio of π (1 − \frac{1}{k}). If, in addition, B is centered and spherical, i.e. ∑ _{i,j=1}^{k} b_{ij} = 0 and b_{ii} = 1 for all i, then our algorithm achieves an approximation ratio of \frac{8π}{9} (1 − \frac{1}{k}). This ratio is also valid if B is the identity matrix, and as we mentioned above, we believe that this approximation guarantee cannot be improved assuming the UGC (and here we prove this conjecture for k = 3). When A is not necessarily centered (note that this case is of lesser interest in terms of the applications in machine learning) we obtain an algorithm which achieves an approximation ratio of 1 + \frac{3π}{2} (this is probably sub-optimal). All of our algorithms, which are described in Section 2, use semi-definite programming in a perhaps non-obvious way. The rounding algorithm of our semi-definite relaxation amounts to proving certain geometric inequalities which can be viewed as variants of the positive semi-definite Grothendieck inequality. This analysis is presented in Section 2. As a concrete example we state in this introduction the following Grothendieck-type inequality which corresponds to our \frac{8π}{9} (1 − \frac{1}{k}) algorithm:

Theorem 1.1. Let (a_{ij}) be an n × n positive semi-definite matrix with ∑ _{i,j=1}^{n} a_{ij} = 0. Then for every k ≥ 3 and v_{1}, …, v_{k} ∈ S^{k−1} with ∑ _{i=1}^{k} v_{i} = 0 we have

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

Inequality (6) is sharp when k = 3, and we conjecture that it is sharp for all k ≥ 4. This conjecture is related to a geometric conjecture which we describe below.

The Unique Games Conjecture, hardness of approximation, and the propeller problem. Our hardness result for kernel clustering problem is based on the Unique Games Conjecture which was put forth by Khot in [14]. We shall now describe this conjecture. A Unique Game is an optimization problem with an instance ℒ = ℒ (G(V, W, E), n, {π_{vw}}_{(v,w)∈W}). 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 to 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 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 ℒ with n labels satisfies OPT(ℒ) ≥ 1 − ε or OPT(ℒ) ≤ δ^{1}. 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 [5] for a description of known results), the unique games conjecture still stands.

Our UGC hardness result for kernel clustering, which is presented in Section 3, is based at heart on the “dictatorship vs. low-influence” paradigm that is recurrent in UGC hardness results (for example [14, 16]). In order to apply this paradigm one usually designs a probabilistic test on a given Boolean function on the Boolean hypercube and then analyzes the acceptance probability of this test in the two extremes of dictatorship functions and functions without influential variables. The gap between these two acceptance probabilities translates into the hardness of approximation factor. In our case, instead of a probabilistic test we need to design a positive semidefinite quadratic form on the truth table of the function. Our form is the sum of the squares of the Fourier coefficients of level 1. This already yields \frac{π}{2} UGC hardness when k = 2.

1As stated in [14], the conjecture says that it is NP-hard to distinguish between these two cases. However if one only wants to rule out polynomial time algorithms, the conjecture as stated here suffices.

For larger k we need to work with functions from {1, …, k}^{n} to {1, …, k}. The analysis of this approach leads to the “propeller problem” which we now describe. The details of this connection are explained in Section 3.

We believe that one of the interesting aspects of the present paper is that complexity considerations lead to geometric/analytic problems which are of independent interest. Similar such connections have been recently discovered in [15, 9]. In our case the reduction from UGC to kernel clusterings leads to the following question, which we call the “propeller problem” for reasons that will become clear presently. Let γ_{k−1} denote the standard Gaussian measure on ^{k−1}, i.e. the density of γ_{k−1} is (2π)^{−(k−1)/2}e^{−∥x∥_{2}^{2}/2}. Let A_{1}, …, A_{k} be a partition of ^{k−1} into measurable sets. For each i ∈ {1, …, k} consider the Gaussian moment of the set A_{i}, i.e. the vector

z_{i} ∫_{A_{i}}xdγ_{k−1}(x) ∈ ^{k−1}.

Our goal is to find the partition which maximizes the sum of the squared Euclidean lengths of the Gaussian moments of the elements of the partition, i.e. ∑ _{i=1}^{k} ∥z_{i}∥_{2}^{2}. Let C(k) denote the value of this maximum (in Section 3.1 we show that this is indeed a maximum and not just a supremum). In Section 3 we show that assuming the UGC there is no polynomial time algorithm which approximates Clust(A|I_{k}) to a factor smaller than \frac{1−1/k}{C(k)}. In Section 3.1we show that C(2) = \frac{2}{π} and C(3) = \frac{9}{8π}. The value of C(3) comes from the partition of the plane ^{2} into a “propeller”, i.e. three cones of angle \frac{2π}{3} with cusp at the origin. Most of Section 3.1 is devoted to the proof of the following theorem:

Theorem 1.2. C(k) is attained at a simplicial conical partition, i.e. a partition A_{1}, …, A_{k} of ^{k−1} which has the following form: let A_{1}, …, A_{m} be the elements of the partition which have positive measure. Then A_{j} = B_{j} × ^{k−m} where B_{j} ⊆ ^{m−1} is a cone with cusp at 0 whose base is a simplex.

It is tempting to believe that the optimal simplicial conical partition described in Theorem 1.2 occurs when the cones B_{1}, …, B_{m} are generated by the regular simplex. However, in Section 3.1 we prove that among such regular simplicial conical partitions the one which maximizes the sum of the squared lengths of its Gaussian moments is when m = 3.

We therefore conjecture that for every k ≥ 3 an optimal partition for the problem described above is actually {C_{1} × ^{k−3}, C_{2} × ^{k−3}, C_{3} × ^{k−3}}, where {C_{1}, C_{2}, C_{3}} is the propeller partition of ^{2}—see Figure 1. If this “propeller conjecture” holds true then it would follow that our \frac{8π}{9} (1 − \frac{1}{k}) approximation algorithm is optimal assuming the UGC for every k ≥ 4, and not just for k ∈ {2, 3}. The full propeller conjecture seems to be a challenging geometric problem of independent interest, not just due to the connection that we establish between it and the study of hardness of approximation for kernel clustering.

We end this introduction with an explanation of how our work relates to the recent result of Raghavendra [20] which shows that for any generalized constraint satisfaction problem^{2} (CSP) there is a generic way of writing a semidefinate relaxation that achieves an optimal approximation ratio assuming the Unique Games Conjecture. Our clustering problem fits in the framework of [20] as follows: we wish to compute

max { ∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} : σ : {1, …, n} → {1, …, k}},  (7)

2In a generalized CSP, every assignment to variables in a constraint has a real-valued (possibly negative) pay-off instead of a simple decision saying that the assignment is a satisfying assignment or not.

Figure 1: The conjectured optimal partition for the “sum of squares of Gaussian moments problem” described above consists of a partition of R^{k−1} into 3 parts, and the remaining k − 3 parts are empty. This partition corresponds to a planar 120^{∘} “propeller” multiplied by an orthogonal copy of ^{k−3}.

where (a_{ij}) is a centered positive semi-definite matrix and (b_{ij}) is a positive semi-definite matrix. One can think of this problem as a CSP (with an extra global constraint corresponding to the positive semidefiniteness) where the set of variables is {1, …, n} and we wish to assign each variable a value from the domain {1, …, k}. For every pair (i, j) ∈ {1, …, n} × {1, …, n}, there is a constraint with weight a_{ij}. We get a payoff of b_{st} if variables i and j are assigned s ∈ {1, …, k} and t ∈ {1, …, k} respectively.

Raghavendra shows that every integrality gap instance for his generic SDP relaxation can be translated into a UGC-hardness of approximation result with the hardness factor (essentially) the same as the integrality gap. We make here the non-trivial observation that in the reduction of [20], starting with an integrality gap instance for (the generic SDP relaxation of) the clustering problem (7), the matrix of the constraint weights (a_{ij}) indeed turns out to be positive semi-definite as required in the kernel clustering problem (this requires proof—the details are omitted since this is a digression from the topic of this paper). Thus Raghavendra’s result can be made to apply to the kernel clustering problem (i.e. the generic SDP achieves the optimum approximation ratio assuming UGC).

Nevertheless, it is also useful to look at different relaxations and rounding procedures for the following reasons. Firstly, for a given problem there could be an SDP relaxation that is more natural than the generic one and might be easier to work with. Secondly, Raghavendra’s result (that the integrality gap is same as the hardness factor) applies only when the integrality gap is a constant. This is a priori not clear for the kernel clustering problem. For instance, a priori the integrality gap could be Ω(logn) (as is the case for Grothendieck problem on a general graph—see [1]). So before applying the result of [20], one would need to show that the integrality gap of the generic SDP is indeed a constant. Thirdly, for CSPs with negative payoffs (as is the case in the kernel clustering problem), Raghavendra shows that the value computed by the generic SDP achieves the optimal approximation ratio (modulo UGC), but the paper does not give a rounding procedure. Finally, Raghavendra’s result does not really shed light on the exact hardness threshold in the sense that it shows how to translate integrality gap instances into a UGC hardness result, but gives no idea as to how to construct an integrality gap instance in the first place. Constructing the integrality gap instance in general amounts to answering certain isoperimetric type geometric question (naturally leading to a dictatorship test, or the other way round. In other words, the geometric question itself might be inspired by the dictatorship test that we have in mind). Thus as far as we know, we cannot avoid designing an explicit dictatorship test and answering an isoperimetric type question, whether or not we start with Raghavendra’s generic SDP that is guaranteed to be optimal. As mentioned before, in the clustering problem where B = (b_{st}) is centered and spherical, we show that the UGC-hardness threshold is at least \frac{1−1/k}{C(k)} and characterizing C(k) seems to be a challenging geometric question.

2 Constant factor approximation algorithms for kernel clustering

Let A ∈ M_{n}( ) and B ∈ M_{k}( ) be positive semidefinite matrices. Then there are u_{1}, …, u_{n} ∈ ^{n} and v_{1}, …, v_{k} ∈ ^{k} such that a_{ij} = ⟨u_{i}, u_{j}⟩ and b_{ij} = ⟨v_{i}, v_{j}⟩. Such vectors can be found in polynomial time (this is simply the Cholesky decomposition). The instance of the kernel clustering problem will be called centered if ∑ _{i,j=1}^{n} a_{ij} = 0, or equivalently ∑ _{i=1}^{n} u_{i} = 0. The instance will be called spherical if b_{ii} = 1 = ∥v_{i}∥_{2}^{2} for all i ∈ {1, …, k}. Let R(B) be the radius of the smallest Euclidean ball containing {v_{1}, …, v_{k}}. Note that R(B) is indeed only a function of B, i.e. it does not depend on the particular representation of B as a Gram matrix. Moreover, it is possible to compute R(B), and given the decomposition b_{ij} = ⟨v_{i}, v_{j}⟩ a vector w ∈ ^{k} such that max_{j∈{1,...,k}}∥v_{j} − w∥_{2} = R(B), in polynomial time (see [11]).

Our goal is to compute in polynomial time the quantity:

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

Our algorithm, which is based on semidefinite programming, proceeds via the following steps:

1. Compute a Cholesky decomposition of B, i.e. v_{1}, …, v_{k} ∈ ^{k} with b_{ij} = ⟨v_{i}, v_{j}⟩.

2. Compute (using for example [11]) R(B) and a vector w ∈ ^{k} such that

max_{j∈{1,...,k}}∥v_{j} − w∥_{2} = R(B).

3. Solve the semidefinite program

max { ∑_{i,j=1}^{n} a_{ij} · ⟨∥w∥_{2}u + R(B)x_{i}, ∥w∥_{2}u + R(B)x_{j}⟩ : u, x_{1}, …, x_{n} ∈ ^{n+1} ∧ ∥u∥_{2} = 1 ∧ ∀i ∥x_{i}∥_{2} ≤ 1} .

4. Choose p, q ∈ {1, …, k} such that ∥v_{p} − v_{q}∥_{2} = max_{i,j∈{1,...,k}}∥v_{i} − v_{j}∥_{2}. Let g_{1}, g_{2} ∈ ^{n+1} be i.i.d. standard Gaussian vectors and define σ : {1, …, n} → {1, …, k} by

σ(r) = \{ \begin{matrix}p & if ⟨g_{1}, x_{r}⟩ ≥ ⟨g_{2}, x_{r}⟩, \\ q & if ⟨g_{2}, x_{r}⟩ ≥ ⟨g_{1}, x_{r}⟩. \end{matrix}  (8)

5. Choose distinct α, β, γ ∈ {1, …, k} such that

∥v_{α} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2} + ∥v_{β} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2} + ∥v_{γ} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2}

is maximized among all such choices of α, β, γ. Let g_{1}, g_{2}, g_{3} ∈ ^{n+1} be i.i.d. standard Gaussian vectors and define τ : {1, …, n} → {1, …, k} by

τ(r) = \{ \begin{matrix}α & if ⟨g_{1}, x_{r}⟩ ≥ max\{⟨g_{2}, x_{r}⟩, ⟨g_{3}, x_{r}⟩\} , \\ β & if ⟨g_{2}, x_{r}⟩ ≥ max\{⟨g_{1}, x_{r}⟩, ⟨g_{3}, x_{r}⟩\} , \\ γ & if ⟨g_{3}, x_{r}⟩ ≥ max\{⟨g_{1}, x_{r}⟩, ⟨g_{2}, x_{r}⟩\} . \end{matrix}  (9)

6. Output σ if ∑ _{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} ≥ ∑ _{i,j=1}^{n} a_{ij}b_{τ(i)τ(j)}. Otherwise output τ.

Remark 2.1. The astute reader might notice that there is an obvious generalization of the above algorithm. Namely for every fixed integer s ∈ [2, k] we can choose a subset S ⊆ {1, .., k} of cardinality s which maximizes the quantity

∑_{i∈S} ∥v_{i} − \frac{1}{s} ∑_{j∈S} v_{j} ∥_{2}^{2} .

Then, we can choose s i.i.d. standard Gaussians {g_{i}}_{i∈S} ⊆ ^{n+1} and define σ_{s} : {1, …, n} → {1, …, k} analogously to the above, namely σ_{s}(r) = i if

⟨g_{i}, x_{r}⟩ = max_{j∈S}⟨g_{j}, x_{r}⟩.

Then, we can consider the assignments σ_{2}, σ_{3}, …, σ_{s} and choose the one which maximizes the objective ∑ _{i,j=1}^{n} a_{ij}b_{σ_{ℓ}(i)σ_{ℓ}(j)} . In spite of this flexibility, it turns out that the the rounding method described above does not improve if we take s ≥ 4. In order to demonstrate this fact we will proceed below to analyze the algorithm for general s, and then optimize over s.

Bounds on the performance of the above algorithm are contained in the following theorem:

Theorem 2.1. Assume that A is centered, i.e. that ∑ _{i,j=1}^{n} a_{ij} = 0. Let p, q, α, β, γ ∈ {1, …, k} and v_{1}, …, v_{k} be as in the description above. Then the algorithm outputs in polynomial time a random assignment λ : {1, …, n} → {1, …, k} satisfying

Clust(A|B)

≤ min \{ \frac{2πR(B)^{2}}{∥v_{p} − v_{q}∥_{2}^{2}}, \frac{16πR(B)^{2}}{9 (∥v_{α} − \frac{v_{α}+v_{β}+v_{γ}}{3} ∥_{2}^{2} + ∥v_{β} − \frac{v_{α}+v_{β}+v_{γ}}{3} ∥_{2}^{2} + ∥v_{γ} − \frac{v_{α}+v_{β}+v_{γ}}{3} ∥_{2}^{2})} \} [∑_{i,j=1}^{n} a_{ij}b_{λ(i)λ(j)} ]. (10)

In particular we always have

Clust(A|B) ≤ π (1 − \frac{1}{k}) [∑_{i,j=1}^{n} a_{ij}b_{λ(i)λ(j)} ],  (11)

and if B is centered and spherical, i.e. ∑ _{i,j=1}^{k} b_{ij} = 0 and b_{ii} = 1 for all i, then

Clust(A|B) ≤ \frac{8π}{9} (1 − \frac{1}{k}) [∑_{i,j=1}^{n} a_{ij}b_{λ(i)λ(j)} ].  (12)

The same bound in (12) holds true if B is the identity matrix.

We single out in the next theorem the case k ∈ {2, 3}, since in these cases we have matching UGC hardness results. Note that for general k we obtain a factor π approximation algorithm, answering positively the question posed by Song, Smola, Gretton and Borgwardt in [24].

Theorem 2.2. Assume that A is centered and B is a 2 × 2 matrix. Then our algorithm achieves a \frac{π}{2} approximation factor. Assuming the Unique Games Conjecture no polynomial time algorithm achieves an approximation guarantee smaller than \frac{π}{2} in this case.

Assume that A is centered, k = 3 and B is centered and spherical (since k = 3 this forces B to be the Gram matrix of the-degree three roots of unity in the complex plane). Then our algorithm achieves an approximation factor of \frac{16π}{27}. Assuming the Unique Games Conjecture no polynomial time algorithm achieves an approximation guarantee smaller than \frac{16π}{27} in this case.

In fact, we believe that the UGC hardness threshold for the kernel clustering problem when A is centered and B is spherical and centered is exactly

\frac{8π}{9} (1 − \frac{1}{k}) .

In Section 3 we describe a geometric conjecture which we show implies this tight UGC threshold for general k.

We end the discussion by stating a (probably suboptimal) constant factor approximation result when A is not necessarily centered (note that this case is of lesser interest in terms of the applications in machine learning). In this case the above algorithm gives a constant factor approximation. The slightly better bound on the approximation factor in Theorem 2.3 below follows from a variant of the above algorithm which will be described in its proof.

Theorem 2.3. For general A and B (not necessarily centered) there exists a polynomial time algorithm that achieves an approximation factor of

1 + \frac{2π}{∥v_{p} − v_{q}∥_{2}^{2}}· max_{i∈\{1,...,k\}}∥v_{i} − \frac{v_{p} + v_{q}}{2}∥_{2}^{2} ≤ 1 + \frac{3π}{2}.

The proof of Theorem 2.2 is contained in Section 3. We shall now proceed to prove Theorem 2.1. Before doing so we will show how the general bound in (10) implies the bounds (11) and (12). The proof of Theorem 2.3 is deferred to the end of this section.

To prove that (10) implies (11) let D denote the diameter of the set {v_{1}, …, v_{k}}, i.e. D = ∥v_{p} − v_{q}∥_{2}. A classical theorem of Jung [13] (see [8]) says that

R(B) ≤ D · \sqrt{\frac{k − 1}{2k}},

and (11) follows immediately by taking the first term in the minimum in (10).

We shall now show that (10) implies (12) when B is either centered and spherical or the identity matrix. Assume first of all that B is centered and spherical. Note that since v_{1}, …, v_{k} are unit vectors, R(B) ≤ 1. Hence, by considering the second term in the minimum in (10) we see that it is enough to show that there exist α, β, γ ∈ {1, …, k} for which

∥v_{α} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2} + ∥v_{β} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2} + ∥v_{γ} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2} ≥ \frac{2k}{k − 1}.

This follows from an averaging argument. Indeed,

\frac{1}{\binom{k}{3}} ∑_{\begin{matrix}α,β,γ∈\{1,...,k\} \\ α<β<γ \end{matrix}}(∥v_{α} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2} + ∥v_{β} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2} + ∥v_{γ} − \frac{v_{α} + v_{β} + v_{γ}}{3} ∥_{2}^{2})

= \frac{2}{k} ∑_{i=1}^{k} ∥v_{i}∥_{2}^{2} − \frac{2}{k(k − 1)} ∑_{\begin{matrix}i,j∈\{1,...,k\} \\ i j \end{matrix}}⟨v_{i}, v_{j}⟩ = \frac{2}{k} ∑_{i=1}^{k} b_{ii} − \frac{2}{k(k − 1)} (∑_{i,j=1}^{k} b_{ij} − ∑_{i=1}^{k} b_{ii}) = \frac{2k}{k − 1}.

This complete the proof of (12) when B is spherical and centered. The same bound holds true when B = I_{k} is the identity matrix since in this case if we denote by e_{1}, …, e_{k} the standard unit basis of ^{k} and e = \frac{1}{k} ∑ _{i=1}^{k} e_{i} then for every assignment λ : {1, …, n} → {1, …, k} we have

∑_{i,j=1}^{n} a_{ij}(I_{k})_{λ(i)λ(j)} = ∑_{i,j=1}^{n}⟨u_{i}, u_{j}⟩⟨e_{λ(i)}, e_{λ(j)}⟩

= ∑_{i,j=1}^{n}⟨u_{i}, u_{j}⟩⟨e_{λ(i)} − e, e_{λ(j)} − e⟩ + 2 ⟨∑_{i=1}^{n} u_{i}, ∑_{j=1}^{n} ⟨e, e_{λ(j)}⟩u_{j}⟩− ∥e∥_{2}^{2} ∥∑_{i=1}^{k} u_{i}∥_{2}^{2} . (13)

The last two terms in (13) vanish since A is centered. Thus

∑_{i,j=1}^{n} a_{ij}(I_{k})_{λ(i)λ(j)} = \frac{k − 1}{k} ∑_{i,j=1}^{n} a_{ij}c_{λ(i)λ(j)},

where C = (c_{ij}) = \frac{k}{k−1}(⟨e_{i} − e, e_{j} − e⟩) is spherical and centered. Thus the case of the identity matrix reduces to the previous analysis.

Proof of Theorem 2.1. Denote

SDP max ∑_{i,j=1}^{n} a_{ij} · ⟨∥w∥_{2}u + R(B)x_{i}, ∥w∥_{2}u + R(B)x_{j}⟩ ,

where the maximum is taken over all u, x_{1}, …, x_{n} ∈ ^{n+1} such that ∥u∥_{2} = 1 and ∥x_{i}∥_{2} ≤ 1 for all i. Observe that

SDP ≥ Clust(A|B).  (14)

Indeed, for every λ : \{1, …, n\} → \{1, …, k\} define u = \frac{w}{∥w∥_{2}} and x_{i} = \frac{v_{λ(i)}−w}{R(B)} and note that in this case

∑_{i,j=1}^{n} a_{ij} · ⟨∥w∥_{2}u + R(B)x_{i}, ∥w∥_{2}u + R(B)x_{j}⟩ = ∑_{i,j=1}^{n} a_{ij}b_{λ(i)λ(j)}.

Let u^{∗}, x_{1}^{∗}, …, x_{n}^{∗} be the optimal solution to the SDP. It will be convenient to think of the SDP solution as being split into two parts. So we rewrite

SDP = ∑_{i,j=1}^{n} a_{ij} · ⟨∥w∥_{2}u^{∗} + R(B)x_{i}^{∗}, ∥w∥_{2}u^{∗} + R(B)x_{j}^{∗}⟩

= ∑_{i,j=1}^{n}⟨u_{i}, u_{j}⟩ · ⟨∥w∥_{2}u^{∗} + R(B)x_{i}^{∗}, ∥w∥_{2}u^{∗} + R(B)x_{j}^{∗}⟩

= ∥∑_{i=1}^{n} u_{i} ⊗ (∥w∥_{2}u^{∗} + R(B)x_{i}^{∗})∥_{{2 \atop 2}}  (15)

= ∥(∥w∥_{2} (∑_{i=1}^{n} u_{i})⊗ u^{∗}) + (R(B) ∑_{i=1}^{n} u_{i} ⊗ x_{i}^{∗})∥_{2}^{2}
= ∥P + Q∥_{2}^{2},  (16)

where

P ∥w∥_{2} ∑_{i=1}^{n} u_{i} ⊗ u^{∗},  (17)

and

Q R(B) ∑_{i=1}^{n} u_{i} ⊗ x_{i}^{∗}.  (18)

Observe in passing that (16) implies that the objective function of the SDP is convex as a function of u, x_{1}, …, x_{n}, and therefore we may assume that ∥u^{∗}∥_{2} = 1 and ∥x_{i}^{∗}∥_{2} = 1 for all i.

We shall now proceed with the analysis of our algorithm while using the variant described in Remark 2.1. This will not create any additional complication, and will allow us to explain why there is no advantage in working with subsets of size s ≥ 4. Recall the setting: for a fixed integer s ∈ [2, k] we choose a subset S ⊆ {1, .., k} of cardinality s which maximizes the quantity

∑_{i∈S} ∥v_{i} − \frac{1}{s} ∑_{j∈S} v_{j} ∥_{2}^{2} .

Then, we choose s i.i.d. standard Gaussians {g_{i}}_{i∈S} ⊆ ^{n+1} and define σ : {1, …, n} → {1, …, k} by setting σ(r) = i if

⟨g_{i}, x_{r}^{∗}⟩ = max_{j∈S}⟨g_{j}, x_{r}^{∗}⟩.

Fix i, j ∈ {1, …, n}. As proved by Frieze and Jerrum in [10] (see Lemma 5 there), we have^{3}:

Pr[σ(i) = σ(j)] = ∑_{m=0}^{∞}R_{m}(s)⟨x_{i}^{∗}, x_{j}^{∗}⟩^{m},

3We are using here the fact that x_{1}^{∗}, …, x_{n}^{∗} are unit vectors.

where the power series converges on [−1, 1] and all the coefficients R_{m}(s) are non-negative. Moreover R_{0}(s) = \frac{1}{s} and

R_{1}(s) = \frac{1}{s − 1} ( [max_{j∈S}g_{j}])^{2} = \frac{1}{s − 1} (\frac{s}{(2π)^{s/2}} ∫ _{−∞}^{∞} xe^{−x^{2}/2} (∫ _{−∞}^{x} e^{−y^{2}/2}dy)^{s−1} dx)^{2} .

Note that conditioned on the event σ(i) = σ(j), the random index σ(i) is uniformly distributed over S. Also, conditioned on the event σ(i) σ(j), the pair (σ(i), σ(j)) is uniformly distributed over all s(s − 1) pairs of distinct indices in S. Thus

[b_{σ(i)σ(j)} ] = Pr[σ(i) = σ(j)] · (\frac{1}{s} ∑_{ℓ∈S} b_{ℓℓ})+ Pr[σ(i) σ(j)] · (\frac{1}{s(s − 1)} ∑_{\begin{matrix}ℓ,t∈S \\ ℓ t \end{matrix}}b_{ℓt}).

Denote Φ = \frac{1}{s} ∑ _{ℓ∈S} b_{ℓℓ} and Ψ = \frac{1}{s(s−1)} ∑ \begin{matrix}ℓ,t∈S \\ ℓ t \end{matrix}b_{ℓt}. (note that Φ, Ψ depend on the matrix B as well as the

choice of the subset S ⊆ {1, …, k}. Thus

[b_{σ(i)σ(j)} ] = (∑_{m=0}^{∞}R_{m}(s)⟨x_{i}^{∗}, x_{j}^{∗}⟩^{m})· Φ + (1 − ∑_{m=0}^{∞}R_{m}(s)⟨x_{i}^{∗}, x_{j}^{∗}⟩^{m})· Ψ

= (Ψ + (Φ − Ψ)R_{0}(s)) + (Φ − Ψ) ∑_{m=1}^{∞}R_{m}(s)⟨x_{i}^{∗}, x_{j}^{∗}⟩^{m}. (19)

Write v \frac{1}{s} ∑ _{ℓ∈S} v_{ℓ}. Observe that

Ψ + (Φ − Ψ)R_{0}(s) = ∥v∥_{2}^{2}.  (20)

Indeed, since R_{0}(s) = 1/s we have

Ψ + (Φ − Ψ)R_{0}(s) = (1 − \frac{1}{s}) (\frac{1}{s(s − 1)} ∑_{\begin{matrix}ℓ,t∈S \\ ℓ t \end{matrix}}b_{ℓt})+ \frac{1}{s} (\frac{1}{s} ∑_{ℓ∈S} b_{ℓℓ})= \frac{1}{s^{2}} ∑_{ℓ,t∈S}b_{ℓt}= ∥\frac{1}{s} ∑_{ℓ∈S}^{s} v_{ℓ}∥_{2}^{2} = ∥v∥_{2}^{2}.

Moreover,

(s − 1)(Φ − Ψ) = ∑_{ℓ∈S} ∥v_{ℓ} − v∥_{2}^{2}.  (21)

In particular Φ − Ψ ≥ 0. To prove (21) we simply expand:

∑_{ℓ∈S} ∥v_{ℓ} − v∥_{2}^{2} = ∑_{ℓ∈S} ∥v_{ℓ}∥_{2}^{2} − s∥v∥_{2}^{2} = sΦ − \frac{1}{s} ∑_{ℓ,t∈S}b_{ℓt}= sΦ − \frac{1}{s} (sΦ + s(s − 1)Ψ) = (s − 1)(Φ − Ψ).

Multiplying both sides of equation (19) by a_{ij} and summing over i, j ∈ {1, …, n} while using (20) we get that

[∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} ]= ∥v∥_{2}^{2} ∑_{i,j=1}^{n} a_{ij} + (Φ − Ψ)R_{1}(s) ∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩ + (Φ − Ψ) ∑_{m=2}^{∞}R_{m}(s) ∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩^{m}. (22)

Note that for every m ≥ 1 we have

∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩^{m} = ∑_{i,j=1}^{n}⟨u_{i}, u_{j}⟩ ⟨(x_{i}^{∗})^{⊗m}, (x_{j}^{∗})^{⊗m}⟩= ∥∑_{i=1}^{n} u_{i} ⊗ (x_{i}^{∗})^{⊗m}∥_{2}^{2} ≥ 0.  (23)

Plugging (23) into (22), and using the fact that Φ − Ψ ≥ 0 and the positivity of _{m}(s), we conclude that

[∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} ]≥ ∥v∥_{2}^{2} ∑_{i,j=1}^{n} a_{ij} + (Φ − Ψ)R_{1}(s) ∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩.  (24)

We shall now use the fact that ∑ _{i,j=1}^{n} a_{ij} = 0 for the first time. In this case P = 0 (see equations (16) and (17)) so that

SDP = R(B)^{2} ∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩.  (25)

Hence, using (24) and (20) we get the bound

[∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} ]≥ \frac{R_{1}(s) ∑ _{ℓ∈S} ∥v_{ℓ} − v∥_{2}^{2}}{(s − 1)R(B)^{2}}· SDP ≥^{(14)} \frac{R_{1}(s) ∑ _{ℓ∈S} ∥v_{ℓ} − v∥_{2}^{2}}{(s − 1)R(B)^{2}}· Clust(A|B).  (26)

The term R_{1}(s) is studied in Section 3.1, where its geometric interpretation is explained. In particular, it follows from Corollary 3.6 and Corollary 3.4 that R_{1}(s) < R_{1}(3) for every s ≥ 4 and that R_{1}(2) = \frac{1}{π} and R_{1}(3) = \frac{9}{8π}. Hence the cases s ∈ \{2, 3\} in (26) conclude the proof of Theorem 2.1. Moreover, we see that for s ≥ 4 the lower bound in (26) is worse than the lower bound obtained when case s = 3. Indeed, we have already noted that in this case R_{1}(s) < R_{1}(3). In addition,

\frac{1}{\binom{s}{3}} ∑_{\begin{matrix}T⊆S \\ |T|=3 \end{matrix}} \frac{1}{2} ∑_{ℓ∈T} ∥v_{ℓ} − \frac{1}{3} ∑_{t∈T}v_{t}∥_{2}^{2} = \frac{1}{s} ∑_{ℓ∈S} ∥v_{ℓ}∥_{2}^{2} − \frac{1}{s(s − 1)} ∑_{\begin{matrix}ℓ,t∈S \\ ℓ t \end{matrix}}⟨v_{ℓ}, v_{t}⟩ = \frac{1}{s − 1} ∑_{ℓ∈S} ∥v_{ℓ} − \frac{1}{s} ∑_{t∈S} v_{t}∥_{2}^{2} .

This implies that there exists T ⊆ S with |T| = 3 for which

\frac{1}{2} ∑_{ℓ∈T} ∥v_{ℓ} − \frac{1}{3} ∑_{t∈T}v_{t}∥_{2}^{2} ≥ \frac{1}{s − 1} ∑_{ℓ∈S} ∥v_{ℓ} − v∥_{2}^{2},

so that when s ≥ 4 the lower bound in (26) is inferior to the same lower bound when s = 3.

It remains to deal with the case ∑ _{i,j=1}^{n} a_{ij} > 0, i.e. to prove Theorem 2.3.

Proof of Theorem 2.3. We slightly modify the algorithm that was studied in Theorem 2.1. Let v_{1}, …, v_{k} and p, q ∈ {1, …, k} be as before, that is b_{ij} = ⟨v_{i}, v_{j}⟩ and ∥v_{p} − v_{q}∥_{2} = max_{i,j∈{1,...,k}}∥v_{i} − v_{j}∥_{2} = D, the diameter of the set \{v_{1}, …, v_{k}\} ∈ ^{k}. Denote w′ \frac{v_{p}+v_{q}}{2} and

R′(B) max_{i∈{1,...,k}}∥v_{i} − w′∥_{2} .

We now consider the modified semidefinite program

SDP max ∑_{i,j=1}^{n} a_{ij} · ⟨∥w′∥_{2}u + R′(B)x_{i}, ∥w′∥_{2}u + R′(B)x_{j}⟩ ,

where the maximum is taken over all u, x_{1}, …, x_{n} ∈ ^{n+1} such that ∥u∥_{2} = 1 and ∥x_{i}∥_{2} ≤ 1 for all i. From now on we will use the notation of the proof of Theorem 2.1 with w replaced by w′ and R(B) replaced by R′(B) (this slight abuse of notation will not create any confusion). As before, we let g_{1}, g_{2} ∈ ^{n+1} be i.i.d. standard Gaussian vectors and define σ : {1, …, n} → {1, …, k} by

σ(r) = \{ \begin{matrix}p & if ⟨g_{1}, x_{r}⟩ ≥ ⟨g_{2}, x_{r}⟩, \\ q & if ⟨g_{2}, x_{r}⟩ ≥ ⟨g_{1}, x_{r}⟩. \end{matrix}  (27)

Note that the first place in the proof of Theorem 2.1 where the assumption that A is centered was used in equation (25). Hence, in the present setting we still have the bounds

Clust(A|B) ≤ SDP = ∥P + Q∥_{2}^{2} ≤ (∥P∥_{2} + ∥Q∥_{2})^{2} ,  (28)

where P and Q are defined in (17) and (18) (with w and R(B) replaced by w′and R′(B), respectively). Also, it follows from (24) that

[∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} ]≥ ∥v∥_{2}^{2} ∑_{i,j=1}^{n} a_{ij} + (∥v_{p} − v∥_{2}^{2} + ∥v_{q} − v∥_{2}^{2})R_{1}(2) ∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩,  (29)

where v = \frac{v_{p}+v_{q}}{2} = w′. Note that ∥v_{p} − v∥_{2}^{2} + ∥v_{q} − v∥_{2}^{2} = \frac{D^{2}}{2}, and recall that R_{1}(2) = \frac{1}{π}. Thus (29) becomes:

[∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} ]≥ ∥w′∥_{2}^{2} ∑_{i,j=1}^{n} a_{ij} + \frac{D^{2}}{2π} ∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩,  (30)

Note that

∥P∥_{2}^{2} = ∥w′∥_{2}^{2} · ∥∑_{i=1}^{n} u_{i} ⊗ u^{∗}∥_{2}^{2} = ∥w′∥_{2}^{2} · ∥u^{∗}∥_{2}^{2} ∑_{i,j=1}^{n}⟨u_{i}, u_{j}⟩ = ∥w′∥_{2}^{2} ∑_{i,j=1}^{n} a_{ij}.  (31)

and

∥Q∥_{2}^{2} = R′(B)^{2} · ∥∑_{i=1}^{n} u_{i} ⊗ x_{i}^{∗}∥_{2}^{2} = R′(B)^{2} ∑_{i,j=1}^{n} a_{ij}⟨x_{i}^{∗}, x_{j}^{∗}⟩.  (32)

Combining (28) and (30) with (31) and (32) we see that

Clust(A|B) ≤ \frac{(∥P∥_{2} + ∥Q∥_{2})^{2}}{∥P_{2}∥_{2}^{2} + c∥Q∥_{2}^{2}}· [∑_{i,j=1}^{n} a_{ij}b_{σ(i)σ(j)} ],  (33)

where c = \frac{D^{2}}{2πR′(B)^{2}}. The convexity of the function x → x^{2} implies that

(∥P∥_{2} + ∥Q∥_{2})^{2} = (\frac{c}{c + 1} · \frac{c + 1}{c} ∥P∥_{2}^{2} + (1 − \frac{c}{c + 1} ) (c + 1)∥Q∥_{2}^{2})^{2}

≤ \frac{c + 1}{c} ∥P∥_{2}^{2} + (c + 1)∥Q∥_{2}^{2} = (1 + \frac{1}{c}) (∥P∥_{2}^{2} + c∥Q∥_{2}^{2}).

Thus (33) implies that our algorithm achieves an approximation guarantee bounded above by

1 + \frac{1}{c} = 1 + \frac{2πR′(B)^{2}}{D^{2}} = 1 + \frac{2π}{∥v_{p} − v_{q}∥_{2}^{2}}· max_{i∈\{1,...,k\}}∥v_{i} − \frac{v_{p} + v_{q}}{2}∥_{2}^{2} .

It remains to note that for every i ∈ {1, …, k} we know that ∥v_{i} − v_{p}∥_{2}, ∥v_{i} − v_{q}∥_{2} ≤ D and therefore ∥v_{i} − w′∥_{2} ≤ ^{\frac{\sqrt{3}}{2}}D. This implies that our approximation guarantee is bounded from above by 1 + \frac{3π}{2}.

3 UGC hardness

3.1 Geometric preliminaries: Propeller problems

Let γ_{n} be the standard Gaussian measure on ^{n}. For any integer k ≥ 2 define

C(n, k) sup {∑_{j=1}^{k} ∥∫_{^{n}} xf_{j}(x)dγ_{n}(x)∥_{2}^{2} : f_{1}, …, f_{k} ∈ L_{2}(γ_{n}) ∧ ∀j f_{j} ≥ 0 ∧ ∑_{j=1}^{k} f_{j} ≤ 1} .  (34)

We first observe that the supremum in (34)is attained at a k-tuple of functions which correspond to a partition of ^{n}:

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

∑_{j=1}^{k} ∥∫_{A_{j}} xdγ_{n}(x)∥_{2}^{2} = C(n, k).

Proof. Let H be the Hilbert space L_{2}(γ_{n}) ⊕ L_{2}(γ_{n}) ⊕ ⋯ ⊕ L_{2}(γ_{n}) (k times). Define K ⊆ H to be the set of all (f_{1}, …, f_{k}) ∈ H such that f_{j} ≥ 0 for all j and ∑ _{j=1}^{k} f_{j} ≤ 1. Then K is a closed convex and bounded subset of H, and hence by the Banach-Alaoglu it is weakly compact. The mapping ψ : K → given by

ψ(f_{1}, …, f_{k}) ∑_{j=1}^{k} ∥∫_{^{n}} xf_{j}(x)dγ_{n}(x)∥_{2}^{2} = ∑_{j=1}^{k} ∑_{i=1}^{n} (∫_{^{n}} x_{i}f_{j}(x)dγ_{n}(x))^{2}

is weakly continuous since the mapping (x_{1}, …, x_{n}) → x_{j} is in L_{2}(γ_{n}) for each j. Hence ψ attains its maximum on K, say at (f_{1}^{∗}, …, f_{k}^{∗}) ∈ K.

Define z_{j} ∫_{^{n}} xf_{j}^{∗}(x)dγ_{n}(x) ∈ ^{n} and let

w − ∑_{j=1}^{k} z_{j} = ∫_{^{n}} x (1 − ∑_{j=1}^{k} f_{j}^{∗}(x)) dγ_{n}(x).

Note that

\frac{1}{k} ∑_{i=1}^{k} ( ∑_{\begin{matrix}1≤j≤k \\ j i \end{matrix}} ∥z_{j}∥_{2}^{2} + ∥z_{i} + w∥_{2}^{2})= ∑_{j=1}^{k} ∥z_{j}∥_{2}^{2} + (1 − \frac{2}{k}) ∥w∥_{2}^{2} ≥ ∑_{j=1}^{k} ∥z_{j}∥_{2}^{2},

which implies the existence of i ∈ {1, …, k} for which

∑_{\begin{matrix}1≤j≤k \\ j i \end{matrix}} ∥z_{j}∥_{2}^{2} + ∥z_{i} + w∥_{2}^{2} ≥ ∑_{j=1}^{k} ∥z_{j}∥_{2}^{2}.

Hence, if we define for j ∈ {1, …, k},

g_{j} \{ \begin{matrix}f_{j}^{∗} & j i \\ f_{i}^{∗} + 1 − ∑ _{j=1}^{k} f_{j}^{∗} & j = i \end{matrix}

then (g_{1}, …, g_{k}) ∈ K, and

C(n, k) ≥ ∑_{j=1}^{k} ∥∫_{^{n}} xg_{j}(x)dγ_{n}(x)∥_{2}^{2} = ∑_{\begin{matrix}1≤j≤k \\ j i \end{matrix}} ∥z_{j}∥_{2}^{2} + ∥z_{i} + w∥_{2}^{2} ≥ ∑_{j=1}^{n} ∥z_{j}∥_{2}^{2} = C(n, k).

So

∑_{j=1}^{k} ∥∫_{^{n}} xg_{j}(x)dγ_{n}(x)∥_{2}^{2} = C(n, k).

Note that ∑ _{j=1}^{k} g_{j} = 1, so we can define a random partition A_{1}, …, A_{k} of ^{n} as follows: let {s_{x}}_{x∈ ^{n}} be independent random variables taking values in {1, …, k} such that Pr(s_{x} = j) = g_{j}(x), and define A_{j} {x ∈ n : s_{x} = j}. Then by convexity and the definition of C(n, k) we see that

∑_{j=1}^{k} ∥∫_{A_{j}} xdγ_{n}(x)∥_{2}^{2} ≥ ∑_{j=1}^{k} ∥∫_{^{n}} ( 1_{A_{j}}(x))xdγ_{n}(x)∥_{2}^{2} = ∑_{j=1}^{k} ∥∫_{^{n}} xg_{j}(x)dγ_{n}(x)∥_{2}^{2} = C(n, k).

It therefore follows that there exists a partition as required.

Lemma 3.2. If n ≥ k − 1 then C(n, k) = C(k − 1, k) and if n < k − 1 then C(n, k) = C(n, n + 1).

Proof. Assume first of all that n ≥ k − 1. The inequality C(n, k) ≥ C(k − 1, k) is easy since for every f_{1}, …, f_{k} ∈ L_{2}(γ_{k−1}) which satisfy f_{j} ≥ 0 for all j ∈ {1, …, k} and f_{1} + ⋯+ f_{k} ≤ 1 we can define f̃_{1}, …f̃_{k} : ^{n} = ^{k−1}× ^{n−k+1} → by f̃_{j}(x, y) = f_{j}(x). Then f̃_{1}, …f̃_{k} ∈ L_{2}(γ_{n}), f̃_{1}, …f̃_{k} ≥ 0, f̃_{1} +⋯ +f̃_{k} ≤ 1

and ∑ _{j=1}^{k} ∥∫_{^{k−1}} xf_{j}(x)dγ_{k−1}(x)∥_{2}^{2} = ∑ _{j=1}^{k} ∥∫_{^{n}} xf̃_{j}(x)dγ_{n}(x)∥_{2}^{2}. In the reverse direction, by Lemma 3.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

∑ _{j=1}^{k} ∥z_{j} ∥_{2}^{2} = C(n, k). Note that

∑_{j=1}^{k} z_{j} = ∫_{^{n}} (∑_{j=1}^{k} 1_{A_{j}} )xdγ_{n}(x) = ∫_{^{n}} xdγ_{n}(x) = 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} = 1, so that

C(k − 1, k) ≥ C(d, k) ≥ ∑_{j=1}^{k} ∥∫_{V}xg_{j}(x)dγ_{V}(x)∥_{2}^{2} = ∑_{j=1}^{k} ∥∫_{V}∫_{V^{⊥}} 1_{A_{j}}(x + y)xdγ_{V}(x)dγ_{V^{⊥}}(y)∥_{2}^{2}

= ∑_{j=1}^{k} ∥∫_{A_{j}} Proj_{V}(w)dγ_{n}(w)∥_{2}^{2} = ∑_{j=1}^{k} ∥Proj_{V}(z_{j})∥_{2}^{2} = ∑_{j=1}^{k} ∥z_{j} ∥_{2}^{2} = C(n, k).

We now pass to the case n < k − 1. The inequality C(n, n + 1) ≤ C(n, k) is trivial, so we need to show that C(n, k) ≤ C(n, n + 1). We observe that since k > n + 1 for every v_{1}, …, v_{k} ∈ ^{n} there exist two distinct indices i, j ∈ {1, …, k} such that ⟨v_{i}, v_{j}⟩ ≥ 0. The proof of this fact is by induction on n. If n = 1 then our assumption is that k ≥ 3, and therefore at least two of the real numbers v_{1}, …, v_{k} must have the same sign. For n > 1 we may assume that ⟨v_{1}, v_{j}⟩ < 0 for all j ≥ 2 (otherwise we are done). Consider the vectors

\{v_{j} − \frac{⟨v_{1},v_{j}⟩}{∥v_{1}∥_{2}^{2}}· v_{1}\}_{j=2}^{k}, i.e. the projections of v_{2}, …, v_{k} onto the orthogonal complement of v_{1}. By induction

there are distinct i, j ∈ {2, …, k} such that

0 ≤ ⟨v_{i} − \frac{⟨v_{1}, v_{i}⟩}{∥v_{1}∥_{2}^{2}}· v_{1}, v_{j} − \frac{⟨v_{1}, v_{j}⟩}{∥v_{1}∥_{2}^{2}}· v_{1}⟩= ⟨v_{i}, v_{j}⟩ − \frac{⟨v_{i}, v_{1}⟩⟨v_{j}, v_{1}⟩}{∥v_{1}∥_{2}^{2}} ≤ ⟨v_{i}, v_{j}⟩.

Now, let A_{1}, …, A_{k} be a partition of ^{n} as in Lemma 3.1 and denote z_{j} ∫_{A_{j}} xdγ_{n}(x) ∈ ^{n}. By the above argument there are distinct i, j ∈ {1, …, k} such that ⟨z_{i}, z_{j}⟩ ≥ 0. Hence

C(n, k − 1) ≥ ∑_{\begin{matrix}1≤ℓ≤k \\ ℓ \{i,j\} \end{matrix}}∥∫_{A_{ℓ}}xdγ_{n}(x)∥_{2}^{2} + ∥∫_{A_{i}∪A_{j}} xdγ_{n}(x)∥_{2}^{2} = ∑_{\begin{matrix}1≤ℓ≤k \\ ℓ \{i,j\} \end{matrix}}∥z_{ℓ}∥_{2}^{2} + ∥z_{i} + z_{j}∥_{2}^{2}

≥ ∑_{ℓ=1}^{k} ∥z_{ℓ}∥_{2}^{2} = C(n, k) ≥ C(n, k − 1).

So, C(n, k) = C(n, k − 1), and the required identity follows by induction.

In light of Lemma 3.2 we denote from now on C(k) C(k − 1, k). 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 3.3. Let A_{1}, …, A_{k} ⊆ ^{k−1} be a partition as in Lemma 3.1, i.e. if we set z_{j} ∫_{A_{j}} xdγ_{k−1}(x) then

C(k) = ∑ _{j=1}^{k} ∥z_{j}∥_{2}^{2}. Assume also that this partition is minimal in the sense that the number of elements of positive measure in this partition is minimal among all the possible partitions from Lemma 3.1. By relabeling we may assume without loss of generality that for some 1 ≤ ℓ ≤ k we have γ_{k−1}(A_{1}), …, γ_{k−1}(A_{ℓ}) > 0 and that γ_{k−1}(A_{ℓ+1}) = ⋯= γ_{k−1}(A_{k}) = 0. Then up to an orthogonal transformation z_{1}, …, z_{ℓ} ∈ ^{ℓ−1}, for any distinct i, j ∈ {1, …, ℓ} we have ⟨z_{i}, z_{j}⟩ < 0 and for each j ∈ {1, …, ℓ} we have A_{j} = P_{j}(z_{1}, …, z_{ℓ}) × ^{k−ℓ} up to sets of measure zero.

Proof. Since 1_{A_{1}} + ⋯+ 1_{A_{ℓ}} = 1 almost everywhere we have z_{1} + ⋯ z_{ℓ} = 0. Thus the dimension of the span of z_{1}, …, z_{ℓ} is at most ℓ − 1, and by applying an orthogonal transformation we may assume that z_{1}, …, z_{ℓ} ∈ ^{ℓ−1}. Also, if for some distinct i, j ∈ {1, …, ℓ} we have ⟨z_{i}, z_{j}⟩ ≥ 0 we may 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:

C(k) ≥ ∑_{\begin{matrix}1≤r≤k \\ ℓ \{i,j\} \end{matrix}}∥∫_{A_{r}}xdγ_{n}(x)∥_{2}^{2} + ∥∫_{A_{i}∪A_{j}} xdγ_{n}(x)∥_{2}^{2} = ∑_{\begin{matrix}1≤r≤k \\ ℓ \{i,j\} \end{matrix}}∥z_{r}∥_{2}^{2} + ∥z_{i} + z_{j}∥_{2}^{2} ≥ ∑_{r=1}^{k} ∥z_{r}∥_{2}^{2} = C(k).

This contradicts the minimality of the partition A_{1}, …, A_{k}.

Note that the above reasoning implies in particular that the vectors z_{1}, …, z_{ℓ} are distinct, and therefore {P_{j}(z_{1}, …, z_{ℓ}) × ^{k−ℓ}}_{j=1}^{ℓ} is a partition of ^{k−1} (up to sets of measure 0). Assume for the sake of contradiction that these exist i ∈ {1, …, ℓ} such that

γ_{k−1} (A_{i} \ (P_{j}(z_{1}, …, z_{ℓ}) × ^{k−ℓ}))> 0.

Note that up to sets of measure 0 we have:

A_{i} \ (P_{j}(z_{1}, …, z_{ℓ}) × ^{k−ℓ}) = ⋃_{\begin{matrix}j∈\{1,...,ℓ\} \\ j i \end{matrix}}⋃_{m=1}^{∞}\{x ∈ A_{i} : ⟨x, z_{j}⟩ ≥ ⟨x, z_{i}⟩ + \frac{1}{m}\}.

Hence there exists m > 0 and j ∈ \{1, …, ℓ\} \ \{i\} such that if we denote E \{x ∈ A_{i} : ⟨x, z_{j}⟩ ≥ ⟨x, z_{i}⟩ + \frac{1}{m}\} 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(k) ≥ ∑_{r=1}^{k} ∥∫ Ã_{r}xdγ_{k−1}(x)∥_{2}^{2} = ∑_{\begin{matrix}1≤r≤k \\ r \{i,j\} \end{matrix}}∥z_{r}∥_{2}^{2} + ∥z_{i} − w∥_{2}^{2} + ∥z_{j} + w∥_{2}^{2} = ∑_{r=1}^{k} ∥z_{r}∥_{2}^{2} + 2∥w∥_{2}^{2} + 2⟨z_{j}, w⟩ − 2⟨z_{i}, w⟩

≥ C(k) + 2∥w∥_{2}^{2} + 2 ∫_{E} (⟨z_{j}, x⟩ − ⟨z_{i}, x⟩) dγ_{k−1}(x) ≥ C(k) + \frac{2γ_{k−1}(E)}{m} > C(k),

a contradiction.

Corollary 3.4. We have C(2) = \frac{1}{π} and C(3) = \frac{9}{8π}.

Proof. Note that Lemma 3.3 implies that for each k ≥ 2 there exists a partition A_{1}, …, A_{k} of ^{k−1} such that

each A_{j} is a cone and C(k) = ∑ _{j=1}^{k} ∥∫_{A_{j}} xdγ_{k−1}(x)∥_{2}^{2}. When k = 2 the only such partition of consists of the positive and negative half-lines. Thus

C(2) = 2 ( \frac{1}{\sqrt{2π}} ∫ _{0}^{∞} xe^{−x^{2}/2}dx)^{2} = \frac{1}{π}.

When k = 3 the partition A_{1}, A_{2}, A_{3} consists of disjoint cones of angles α_{1}, α_{2}, α_{3} ∈ [0, 2π], respectively, where α_{1} + α_{2} + α_{3} = 2π. Now, for j ∈ {1, 2, 3} we have

∥∫_{A_{j}} xdγ_{2}(x)∥_{2}^{2} = |\frac{1}{2π} ∫ _{0}^{∞} ∫ _{−α_{j}/2}^{α_{j}/2} e^{iθ}r^{2}e^{−r^{2}/2}drdθ|^{2} = \frac{sin^{2}(α_{j}/2)}{2π}.

Hence

C(3) = \frac{1}{2π} max\{sin^{2}(α_{1}/2) + sin^{2}(α_{2}/2) + sin^{2}(α_{3}/2) : α_{1}, α_{2}, α_{3} ∈ [0, π] ∧ α_{1} + α_{2} + α_{3} = 2π\}

= \frac{3}{2π} · sin^{2} (\frac{π}{3}) = \frac{9}{8π}, (35)

where (35) follows from a simple Lagrange multiplier argument.

It is tempting to believe that for every k ≥ 2, C(k) is attained at a regular simplicial partition, i.e. a partition of ^{k−1} of the form {P_{j}(v_{1}, …, v_{k})}_{j=1}^{k} where v_{1}, …, v_{k} are the vertices of the regular simplex in k−1. This was shown to be true for k ∈ {2, 3} in Corollary 3.4. We will now show that this is not the case for k ≥ 4.

Lemma 3.5. Let v_{1}, v_{2}, …, v_{k} ∈ ^{k−1} be vertices of a regular simplex in ^{k−1}, i.e. for each i ∈ {1, …, k} we have ∥v_{i}∥_{2} = 1 and for each distinct i, j ∈ \{1, …, k\} we have ⟨v_{i}, v_{j}⟩ = −\frac{1}{k−1}. Let

z_{i} ∫_{P_{i}(v_{1},...,v_{k})}x dγ_{k−1}(x).

Then

∑_{i=1}^{k} ∥z_{i}∥_{2}^{2} = \frac{1}{k − 1} ( [ max_{j∈\{1,...,k\}}g_{j}])^{2} ,

where g_{1}, g_{2}, …, g_{k} are independent standard Gaussian random variables.

Proof. By symmetry all the z_{i} have the same length r > 0 and z_{i} has the same direction as v_{i}. Thus for all i we have ⟨z_{i}, v_{i}⟩ = r and our goal is to compute kr^{2}. Now,

∑_{i=1}^{k} ⟨z_{i}, v_{i}⟩ = ∑_{i=1}^{k} ∫_{P_{i}(v_{1},...,v_{k})}⟨x, v_{i}⟩ dγ_{k−1}(x) = ∑_{i=1}^{k} ∫_{P_{i}(v_{1},...,v_{k})}( max_{j∈{1,...,k}}⟨x, v_{j}⟩)dγ_{k−1}(x)

= ∫_{^{k−1}} ( max_{j∈{1,...,k}}⟨x, v_{j}⟩)dγ_{k−1}(x) = [ max_{j∈{1,...,k}}h_{j}],

where h_{1}, …, h_{k} are standard Gaussian random variables with covariances [h_{i}h_{j}] = ⟨v_{i}, v_{j}⟩. Let h be a standard Gaussian which is independent of h_{1}, …, h_{k}. Then

[ max_{j∈\{1,...,k\}}h_{j}]= [ \frac{h}{\sqrt{k − 1}} + ( max_{j∈\{1,...,k\}}h_{j})] = [ max_{j∈\{1,...,k\}}( \frac{h}{\sqrt{k − 1}} + h_{j})] = [ max_{j∈\{1,...,k\}}h̃_{j}],  (36)

where we set h̃_{j} \frac{h}{\sqrt{k−1}} +h_{j} so that h̃_{j} are independent Gaussians with mean zero and variance \frac{k}{k−1}. The last

term in (36) is same as \sqrt{\frac{k}{k−1}} · [max_{j∈\{1,...,k\}}g_{j}] where g_{1}, …, g_{k} are independent standard Gaussians.

Corollary 3.6. For k ≥ 2 denote

R(k) \frac{1}{k − 1} ( [ max_{j∈\{1,...,k\}}g_{j}])^{2} = \frac{1}{k − 1} (\frac{k}{(2π)^{k/2}} ∫ _{−∞}^{∞} xe^{−x^{2}/2} (∫ _{−∞}^{x} e^{−y^{2}/2}dy)^{k−1} dx)^{2} .  (37)

Then for every integer k ∈ \{2, 4, 5, …\} we have R(k) < R(3) = \frac{9}{8π}. Thus, if v_{1}^{k}, …, v_{k}^{k} are the vertices of the regular simplex in ^{k−1} then for k ≥ 4 we have

∑_{j=1}^{k} ∥∫_{P_{j}(v_{1}^{k},...,v_{k}^{k})}xdγ_{k−1}(x)∥_{2}^{2} < ∑_{j=1}^{3} ∥∫_{P_{j}(v_{1}^{3},v_{2}^{3},v_{3}^{3})× ^{k−3}} xdγ_{k−1}(x)∥_{2}^{2} .

Proof. It follows from Corollary 3.4 that R(3) = C(3) = \frac{9}{8π}. We require a crude bound on R(k). An application of Stirling’s formula shows that for p ≥ 2 we have

( [|g_{1}|^{p}])^{1/p} = (\frac{2^{p/2}}{\sqrt{π}}Γ (\frac{p + 1}{2} ))^{1/p} ≤ \sqrt{\frac{p}{2}}.

Hence

R(k) ≤ \frac{1}{k − 1} ( [ max_{j∈\{1,...,k\}}|g_{j}|])^{2} ≤ \frac{1}{k − 1} [(∑_{j=1}^{k} |g_{j}|^{p})^{1/p}]^{2} ≤ \frac{1}{k − 1} (∑_{j=1}^{k} [|g_{j}|^{p}])^{2/p} ≤ \frac{1}{k − 1} · k^{2/p} · \frac{p}{2}.

Choosing p = 2 logk ≥ 2 log4 > 2 we see that

R(k) ≤ \frac{e logk}{k − 1}.  (38)

The function k → \frac{logk}{k−1} is decreasing on [4, ∞), and therefore a direct computation using (38) shows that R(k) < \frac{9}{8π} for k ≥ 26. For k ≤ 25 one can compute numerically (say, using Maple) the integral in (37) and get the following values:

R(4) = 0.3532045529, R(5) = 0.3381215916, R(6) = 0.3211623921, R(7) = 0.3047310600,
R(8) = 0.2895196903, R(9) = 0.2756580116, R(10) = 0.2630844408, R(11) = 0.2516780298,

R(12) = 0.2413075184, R(13) = 0.2318492693, R(14) = 0.2231929784, R(15) = 0.2152425349, R(16) = 0.2079150401, R(17) = 0.2011392394, R(18) = 0.1948538849, R(19) = 0.1890062248, R(20) = 0.1835506894, R(21) = 0.1784477705, R(22) = 0.1736630840, R(23) = 0.1691665868,

R(24) = 0.1649319261, R(25) = 0.1609358965.

Since R(3) = 0.3580986219 it follows that R(k) < R(3) for every integer k ∈ [4, 25] as well.

We conjecture that C(k) ≤ C(3) for every integer k ≥ 2. For future reference we end this section with the following alternative characterization of C(k):

Lemma 3.7. We have the following identity:

C(k) = sup \{ \frac{( [max_{j∈\{1,...,k\}}g_{j}])^{2}}{∑ _{j=1}^{k} [g_{j}^{2}]} : (g_{1}, …, g_{k}) ∈ ^{k} mean zero Gaussian vector\} .  (39)

Proof. First we show that C(k) is at most the right hand side of (39). We know that there exists a partition A_{1}, …, A_{k} of ^{k−1} such that if we write z_{i} ∫_{A_{i}}x dγ_{k−1}(x) then A_{j} = P_{j}(z_{1}, …, z_{k})for all j ∈ {1, …, k} and C(k) = ∑ _{j=1}^{k} ∥z_{j}∥_{2}^{2}. Now,

C(k) = ∑_{j=1}^{k} ∥z_{j}∥_{2}^{2} = ∑_{j=1}^{k} ∫_{P_{j}(z_{1},...,z_{k})}⟨x, z_{j}⟩ dγ_{k−1}(x) = ∑_{j=1}^{k} ∫_{P_{j}(z_{1},...,z_{k})}( max_{i∈{1,...,k}}⟨x, z_{i}⟩)dγ_{k−1}(x)

= ∫_{^{k−1}} ( max_{i∈{1,...,k}}⟨x, z_{i}⟩)dγ_{k−1}(x) = [ max_{j∈{1,...,k}}h_{j}], (40)

where in (40) h_{1}, …, h_{k} are mean-zero Gaussians with covariances [h_{i}h_{j}] = ⟨z_{i}, z_{j}⟩. Thus

C(k) = \frac{( [max_{j∈\{1,...,k\}} h_{j}])^{2}}{∑ _{j=1}^{k} [h_{j}^{2}]},

which implies the desired upper bound on C(k).

For the other direction fix a mean zero Gaussian vector (g_{1}, …, g_{k}) ∈ ^{k} and let v_{1}, v_{2}, …, v_{k} ∈ ^{k} be vectors such that [g_{i}g_{j}] = ⟨v_{i}, v_{j}⟩ for all i, j ∈ {1, …, k}. For i ∈ {1, …, k} let w_{i} ∫_{P_{i}(v_{1},...,v_{k})}x dγ_{k−1}(x). Now,

\sqrt{{(∑_{i=1}^{k} ∥w_{i}∥_{2}^{2}) \atop (∑_{i=1}^{k} ∥v_{i}∥_{2}^{2})}}≥ ∑_{i=1}^{k} ⟨w_{i}, v_{i}⟩ = ∑_{i=1}^{k} ∫_{P_{i}(v_{1},...,v_{k})}⟨x, v_{i}⟩ dγ_{k−1}(x)

= ∑_{i=1}^{k} ∫_{P_{i}(v_{1},...,v_{k})}( max_{j∈{1,...,k}}⟨x, v_{j}⟩)dγ_{k−1}(x) = ∫_{^{k−1}} ( max_{j∈{1,...,k}}⟨x, v_{j}⟩)dγ_{k−1}(x) = E [ max_{j∈{1,...,k}}g_{j}].

Therefore,

C(k) ≥ ∑_{i=1}^{k} ∥w_{i}∥^{2} ≥ \frac{( [max_{j∈\{1,...,k\}} g_{j}])^{2}}{∑ _{j=1}^{k} ∥v_{j}∥_{2}^{2}} = \frac{( [max_{j∈\{1,...,k\}} g_{j}])^{2}}{∑ _{j=1}^{k} [g_{j}^{2}]}.

This completes the proof of (39).

3.2 Dictatorships vs. functions with small influences

In what follows all functions are assumed to be measurable and we use the notation [k] {1, …, k}. In this section we will associate to every function from {1, …, k}^{n} to

Δ_{k} {x ∈ ^{k} : x_{i} ≥ 0 ∧ ∀ i ∈ [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(k) = sup_{f: ^{k−1}→Δ_{k}} ∑_{i=1}^{k} ∥∫_{^{k−1}} xf_{i}(x)dγ_{k−1}(x)∥_{2}^{2} ,

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

C(k) = sup_{f: ^{n}→Δ_{k}} ∑_{i=1}^{k} ∥∫_{^{n}} xf_{i}(x)dγ(x)∥_{2}^{2} .

Let (Ω = [k], μ) be a probability space, μ being the uniform measure. Let (Ω^{n}, μ^{n}) be the product space. We will be analyzing functions f : Ω^{n} → Δ_{k} (and more generally into ^{k}). Fix a basis of orthonormal random variables on Ω where one of them is the constant 1, i.e. {X_{0}, X_{1}, …, X_{k−1}} where ∀ i, X_{i} : Ω → , X_{0} ≡ 1 and _{ω∈Ω} [X_{i}(ω)X_{j}(ω)] = 0 for i j and equal to 1 if i = j. 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 1 ≤ i ≤ n, 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_{σ} := ∏ _{i∈[n],σ_{i} 0} x_{i,σ_{i}} on a set of n(k − 1) indeterminates {x_{ij} | i ∈ [n], j ∈ {1, 2, …, k − 1}}, and also a random variable X_{σ} : Ω^{n} → as

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

It is easy to see that 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 ∈ [n], 1 ≤ j ≤ 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 [22, 17] say that if f : Ω^{n} → [0, 1] is a function with all low influences, 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 : Ω^{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 semi-definite quadratic form on the table of values of f. 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} ∑_{σ: |σ|=1} f̂_{i}(σ)^{2}.  (41)

In words, OBJ(f) is the total “Fourier mass” of all functions {f_{i}}_{i=1}^{k} at level 1. Note that there are n(k − 1) multi-indices σ such that |σ| = 1.

The objective value for dictatorships

For ℓ ∈ [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.  (42)

In other words, when one writes f^{dict,ℓ} = (f_{1}, f_{2}, …, f_{k}), f_{i} is {0, 1}-valued and f_{i}(ω) = 1 iff ω_{ℓ} = i. It is easy to see that the Fourier expansion of f_{i} is

f_{i}(ω) = \frac{1}{k} ∑_{σ: σ_{j}=0 ∀j ℓ} X_{σ_{ℓ}}(i) X_{σ}(ω).  (43)

Indeed, the right hand side of (43) equals

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

The Fourier mass of f_{i}^{dict,ℓ}at level 1 equals

∑_{1≤σ_{ℓ}≤k−1} (\frac{X_{σ_{ℓ}}(i)}{k})^{2} = − (\frac{X_{0}(i)}{k})^{2} + ∑_{0≤σ_{ℓ}≤k−1} (\frac{X_{σ_{ℓ}}(i)}{k})^{2} = −\frac{1}{k^{2}} + \frac{k}{k^{2}} = \frac{k − 1}{k^{2}}.

Summing the Fourier mass of all f_{i}^{dict,ℓ}’s at level 1, we get

OBJ(f^{dict,ℓ}) = 1 − \frac{1}{k}.  (44)

The objective value for functions with low influences

For f : Ω^{n} → , j ∈ [n] and m ∈ denote

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

For every η > 0 we will use the smoothing operator:

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

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

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

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

we have,

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

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 n(k−1) indeterminates {x_{jℓ} | j ∈ [n], ℓ ∈ [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 on [17]). Note that R_{i} has range [0, 1] and S_{i} has range . It will follow however from [17] that S_{i} is with high probability 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(k).

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

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

= (1 − δ)^{2} ∑_{i=1}^{k} ∥∫_{^{n(k−1)}} x Q_{i}(x)dγ_{n(k−1)}(x)∥_{2}^{2}

= ∑_{i=1}^{k} ∥∫_{^{n(k−1)}} x (T_{1−δ}Q_{i})(x)dγ_{n(k−1)}(x)∥_{2}^{2}

= ∑_{i=1}^{k} ∥∫_{^{n(k−1)}} x S_{i}(x)dγ_{n(k−1)}(x)∥_{2}^{2} .  (45)

We bound the last term by C(k) + 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}

For every subset I ⊆ [k], let Q_{I} := ∑ _{i∈I} Q_{i}. Since every Q_{i} has small low-degree influence, so does every Q_{I}. Let R_{I} ∑ _{i∈I}(T_{1−δ}Q_{i})(X), and S_{I} ∑ _{i∈I}(T_{1−δ}Q_{i})(G). Note that R_{{i}}= R_{i} and S_{{i}}= S_{i}. Applying Theorem 3.20 in [17] to the polynomial Q_{I}, it follows that (provided τ is sufficiently small compared to δ and η),

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

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

S_{i}^{∗}(x) := \{ \begin{matrix}chop(S_{i})(x) & if ∑ _{i=1}^{k} chop(S_{i})(x) ≤ 1, \\ \frac{chop(S_{i})(x)}{(∑ _{i=1}^{k} chop(S_{i})(x))} & if ∑ _{i=1}^{k} chop(S_{i})(x) > 1. \end{matrix}

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

0 ≤ chop(S_{i}) − S_{i}^{∗} ≤ ∑_{j=1}^{k} (chop(S_{j}) − S_{j}^{∗}) ≤ max (0, ∑_{j=1}^{k} chop(S_{j}) − 1) ≤ ∑_{I⊆[k]} |S_{I} − chop(S_{I})| ,

where the last inequality holds since for every x, by defining I = I(x) = {j | S_{j}(x) ≥ 0},

∑_{j=1}^{k} chop(S_{j})(x) − 1 = ∑_{j∈I} chop(S_{j})(x) − 1 ≤ ∑_{j∈I} S_{j}(x) − 1 ≤ |S_{I}(x) − chop(S_{I})(x)| .

It follows that

∥chop(S_{i}) − S_{i}^{∗}∥_{2} ≤ ∑_{I⊆[k]} ∥S_{I} − chop(S_{I})∥_{2} ≤ 2^{k} \sqrt{η},

where we used (46). Finally,

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

Now write

∫_{^{n(k−1)}} x S_{i}(x)dγ_{n(k−1)}(x) = ∫_{^{n(k−1)}} x S_{i}^{∗}(x)dγ_{n(k−1)}(x) + ∫_{^{n(k−1)}} x (S_{i}(x) − S_{i}^{∗}(x))dγ_{n(k−1)}(x).  (48)

The norm of second integral is bounded by (2^{k} + 1) \sqrt{η} using (47) and Lemma 3.9 below. Since ∥S_{i}^{∗}∥_{2} ≤ 1, the norm of first integral is bounded by 1, and thus

∥∫_{^{n(k−1)}} x S_{i}(x)dγ_{n(k−1)}(x)∥_{2}^{2} ≤ ∥∫_{^{n(k−1)}} x S_{i}^{∗}(x)dγ_{n(k−1)}(x)∥_{2}^{2} + 2(2^{k} + 1) \sqrt{η} + (2^{k} + 1)^{2}η.

Returning to the estimation in Equation (45) and noting that ∑ _{i=1}^{k} S_{i}^{∗} ≤ 1,

∑_{i=1}^{k} ∥∫_{^{n(k−1)}} x S_{i}(x)dγ_{n(k−1)}(x)∥_{2}^{2} ≤ ∑_{i=1}^{k} (∥∫_{^{n(k−1)}} x S_{i}^{∗}(x)dγ_{n(k−1)}(x)∥_{2}^{2} + 2(2^{k} + 1)^{2} \sqrt{η})

≤ sup_{f: ^{n(k−1)}→Δ_{k}} (∑_{i=1}^{k} ∥∫_{^{n(k−1)}} x f_{i}(x)dγ_{n(k−1)}(x)∥_{2}^{2})+ 2(2^{k} + 1)^{3} \sqrt{η}
= C(k) + 2(2^{k} + 1)^{3} \sqrt{η}.

It follows that OBJ(f) ≤ \frac{C(k)+2(2^{k}+1)^{3} \sqrt{η}}{1−δ^{2}} ≤ C(k) + ε, provided that η and δ are small enough.

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

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

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.

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 UGC-hardness result. The hardness factor (as usual) turns out to be the ratio of the objective value when the function is a dictatorship versus the function has all low influences, i.e.

\frac{1 − 1/k}{C(k) + o(1)} = \frac{1 − 1/k}{C(k)} − o(1).

3.3 The reduction from unique games to kernel clustering

Given a Unique Games Instance L(G(V, W, E), [n], {π_{vw}: [n] → [n]}_{(v,w)∈E}), we construct an instance of the clustering problem. We first reformulate the kernel clustering problem for the ease of presentation.

Reformulation of the problem

Given an instance of the kernel clustering problem (A = (a_{st}), B = (b_{ij})) where A and B are N × N and k × k PSD matrices respectively, we note that

max_{σ:[N]→[k]} ∑_{s,t} a_{st} b_{σ(s),σ(t)} = max_{F:[N]→Δ_{k}} ∑_{s,t} a_{st} ∑_{ij} b_{ij}F(s)_{i}F(t)_{j}  (49)
= max_{F:[N]→Δ_{k}} ∑_{i,j} b_{ij} ∑_{s,t} a_{st}F_{i}(s)F_{j}(t)  (50)
= max_{F:[N]→Δ_{k}} ∑_{i,j} b_{ij}Q_{A}(F_{i}, F_{j})  (51)

where on line (49), instead of choosing a label σ(s) ∈ [k], we allow a distribution over the k labels F(s) ∈ Δ_{k}. The equality follows since any such probabilistic labeling F yields a labeling σ with the same expected objective value by picking, for every s ∈ [N], a label i with probability F(s)_{i}. On line (50) we interchanged the order of summation and interpreted the i^{th}co-ordinate of F(s) (i.e. F(s)_{i}) as the value of a function F_{i} :

[N] → [0, 1] at index s (i.e. F_{i}(s)). Thus F = (F_{1}, F_{2}, …, F_{k}). On line (51) we rewrote ∑ _{s,t}a_{st}F_{i}(s)F_{j}(t) as a PSD quadratic form Q_{A}(F_{i}, F_{j}) on the tables of values of functions F_{i} and F_{j}.

This enables us to reformulate the clustering problem as: Given a PSD matrix B, and a PSD quadratic form Q(·, ·) on ^{N} × ^{N}, find F : [N] → Δ_{k}, F = (F_{1}, F_{2}, …, F_{k}), so as to maximize ∑ _{ij} b_{ij}Q(F_{i}, F_{j}).

The clustering problem instance

Given a Unique Games instance

ℒ (G(V, W, E), [n], {π_{vw}: [n] → [n]}_{(v,w)∈E}),

the clustering problem is to find F : W × Ω^{n} → Δ_{k} so as to maximize ∑ _{i=1}^{k} Q(F_{i}, F_{i}) where Q is a suitably defined PSD quadratic form. Thus the matrix B is the k × k identity matrix. For notational convenience, we let

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

Also, for every v ∈ V, we let

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

We used the following notation: for any function g : Ω^{n} → Δ_{k} and π : [n] → [n], g ∘ π : Ω^{n} → Δ_{k} denotes a 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}). 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}}  ∑_{i=1}^{k} _{v∈V} [ ∑_{σ:|σ|=1} F̂_{v,i}(σ)^{2}] .  (52)

Completeness.

We will show that if the Unique Games instance has an almost satisfying labeling, then the objective value of the clustering problem is (1 − o(1)) · (1 − 1/k). So, let ρ : V ∪ W → [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 for ρ(w) ∈ [n], i.e.

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

Lemma 3.10. f^{dict,j} ∘ π = f^{dict,π(j)}.

Proof. f^{dict,π(j)}(ω) equals e_{ℓ} if ω_{π(j)} = ℓ. On the other hand

(f^{dict,j} ∘ π)(ω) = f^{dict,j}(ω_{π(1)}, ω_{π(2)}, …, ω_{π(n)}),

which equals e_{ℓ} since ω_{π(j)} = ℓ.

Lemma 3.11. For a good v ∈ V, F_{v} = f^{dict,ρ(v)}.

Proof. For a good v, π_{vw}(ρ(w)) = ρ(v) for every (v, w) ∈ E. Thus

F_{v} = _{(v,w)∈E}[ F_{w} ∘ π_{vw}] = _{(v,w)∈E}[ f^{dict,ρ(w)}∘ π_{vw}]

= _{(v,w)∈E}[ f^{dict,π_{vw}(ρ(w))}] = _{(v,w)∈E}[ f^{dict,ρ(v)}] = f^{dict,ρ(v)}

Thus the contribution of v in (52) is OBJ(f^{dict,ρ(v)}) = 1 − 1/k as observed in Equation (44). Since 1 − ε fraction of v ∈ V are good, (52) is at least (1 − ε) · (1 − 1/k).

Soundness

Suppose on the contrary that the value of (52) is at least C(k) + 2ε. We will prove that the Unique Games instance must have a labeling that satisfies at least \frac{ετ^{2}}{4k log(1/τ)} fraction of its edges, reaching a contradiction, provided its soundness is chosen to be lower to begin with.

We define a labeling as follows. First we define a not-too-large set of labels L(w) ⊆ [n] for every w ∈ W. Let τ be as in Theorem 3.8.

L(w) := {j ∈ [n] | ∃ i ∈ [k], Inf_{j}^{≤log(1/τ)}(F_{w,i}) ≥ τ/2}

Clearly, |L(w)| ≤ \frac{2k log(1/τ)}{τ} since each F_{w,i} has range [0, 1] and therefore the sum of all degree-log(1/τ) influences is at most log(1/τ).

Now assume that the value of (52) is at least C(k) + 2ε. By an averaging argument, for at least ε fraction of v ∈ V (call such v nice), OBJ(F_{v}) ≥ C(k) + ε. Applying Theorem 3.8, we conclude that there exists i_{0} ∈ [k], j_{0} ∈ [n] such that Inf_{j_{0}}^{≤log(1/τ)}(F_{v,i_{0}}) ≥ τ. Observe that

τ ≤ Inf_{j_{0}}^{≤log(1/τ)}(F_{v,i_{0}})
= Inf_{j_{0}}^{≤log(1/τ)}(E_{(v,w)∈E}[F_{w,i_{0}} ∘ π_{vw}])
≤ E_{(v,w)∈E}[Inf_{j_{0}}^{≤log(1/τ)} (F_{w,i_{0}} ∘ π_{vw})]  Using Lemma 3.12 below
= _{(v,w)∈E}[Inf_{π_{vw}^{−1}(j_{0})}^{≤log(1/τ)} (F_{w,i_{0}})]  Using Lemma 3.14 below

This implies that for at least \frac{τ}{2} fraction of w such that (v, w) ∈ E, we have \frac{τ}{2} ≤ Inf_{π_{vw}^{−1}(j_{0})}^{≤log(1/τ)} (F_{w,i_{0}}). Thus π_{vw}^{−1}(j_{0}) ∈ L(w) by the definition of L(w). Define j_{0} to be the label of v. Finally, for every w ∈ W, select a random label from L(w) (or an arbitrary label if L(w) = ∅). Noting that ε fraction of v ∈ V are nice, and |L(w)| ≤ \frac{2k log(1/τ)}{τ}, it follows that the labeling satisfies ε · \frac{τ}{2} · \frac{1}{2kτ^{−1} log(1/τ)} = \frac{ετ^{2}}{4k log(1/τ)} fraction of the edges of the Unique Games instance.

Lemma 3.12. Suppose C is a class of functions g : Ω^{n} → and h := _{g∈C}[g]. Then for any j ∈ [n] and integer d,

Inf_{j}(h) ≤ E_{g∈C}[Inf_{j}(g)], Inf_{j}^{≤d}(h) ≤ E_{g∈C}[Inf_{j}^{≤d}(g)].

Proof. We prove the first inequality, the second is similar by restricting summations to multi-indices |σ| ≤ d.

Inf_{j}(h) := ∑_{σ:σ_{j} 0} ĥ(σ)^{2} = ∑_{σ:σ_{j} 0} ( _{g∈C}[ĝ(σ)])^{2} ≤ ∑_{σ:σ_{j} 0} _{g∈C}[ĝ(σ)^{2}] = _{g∈C}[Inf_{j}(g)].

Lemma 3.13. Suppose g : Ω^{n} → , π : [n] → [n] and let σ be a multi-index. Then

ĝ ∘ π(σ) = ĝ(π^{−1}(σ)).

Proof. The proof is a straightforward computation which we omit.

Lemma 3.14. Suppose g : Ω^{n} → , π : [n] → [n] and j ∈ [n]. Then

Inf_{j}(g ∘ π) = Inf_{π^{−1}(j)}(g), Inf_{j}^{≤d}(g ∘ π) = Inf_{π^{−1}(j)}^{≤d}(g).

Proof. We prove the first equality, the second is similar by restricting summations to multi-indices |σ| ≤ d.

Inf_{j}(g ∘ π) := ∑_{σ:σ_{j} 0} ĝ ∘ π(σ)^{2} = ∑_{σ:σ_{j} 0} ĝ(π^{−1}(σ))^{2} = ∑_{\overline{σ}:\overline{σ}_{π^{−1} (j)} 0} ĝ(\overline{σ})^{2} = Inf_{π^{−1}(j)}(g).

Acknowledgements

We thank Alex Smola for bringing the problem of approximation algorithms for kernel clustering to our attention and for encouraging us to publish our results.

Added in proof

At the useful request of a referee we wish to address here the relation between the kernel clustering problem when B = I_{k} and the Correlation Clustering problem of Bansal, Blum and Chawla [4]. Apart from the fact that both problems are clustering problems, and that the best-known algorithms for the Maximum Correlation problem in Correlation Clustering involve the use of Grothendieck-type inequalities [7, 1], the Correlation Clustering problem seems only superficially and semantically similar to the problem of approximating Clust(A|I_{k}). In the Correlation Clustering problem you are given a graph with labels ±1 on the edges (there are obvious extensions to other numerical labels). The goal is to partition the vertex set into an unspecified number of clusters so as to maximize the similarity of this partition with the labels: an agreement between the labels and the partition is when two vertices are in the same cluster and are joined by an edge with a + sign, or when two vertices are in different clusters and are joined by an edge with a − sign. One can define a disagreement between the clustering and the labels similarly, and goal would be to find a partition which maximizes the number of agreements, minimizes the number of disagreements, or maximizes the number of agreements minus the number of disagreements (the last problem is called the Maximum Correlation problem). A key point here is that the number of clusters in the partition is not pre-specified and is “discovered” by the algorithm. Thus the case B = I_{k} of the kernel clustering problem does not correspond to the Correlation Clustering problem since we are restricting the number of clusters to be at most k (note that our approximation ratios indeed depend on k). What can be said is that when B = I_{n} (but note that in kernel clustering we really think of n being much larger than k), and we think of the labels between vertices as being of the form ⟨v_{i}, v_{j}⟩ for some vectors v_{i}, then the problem of computing Clust(A|B) becomes perhaps somewhat similar to Correlation Clustering: it isn’t really the same since in Correlation Clustering one counts as an agreement inter-cluster negative pairs, while in the kernel clustering problem with B = I_{n} we completely ignore inter-cluster pairs but do sum negative values within each cluster.

References

[1] N. Alon, K. Makarychev, Y. Makarychev, and A. Naor. Quadratic forms on graphs. Invent. Math., 163(3):499–522, 2006.

[2] N. Alon and A. Naor. Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput., 35(4):787–803 (electronic), 2006.

[3] S. Arora, E. Berger, G. Kindler, E. Hazan, and S. Safra. On non-approximability for quadratic programs. In 46th Annual Symposium on Foundations of Computer Science, pages 206–215. IEEE Computer Society, 2005.

[4] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. In 43rd Symposium on Foundations of Computer Science, pages 238–247, 2002.

[5] 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.

[6] M. Charikar, K. Makarychev, and Y. Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. In SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 62–68, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics.

[7] M. Charikar and A. Wirth. Maximizing quadratic programs: extending Grothendieck’s inequality. In 45th Annual Symposium on Foundations of Computer Science, pages 54–60. IEEE Computer Society, 2004.

[8] L. Danzer, B. Grünbaum, and V. Klee. Helly’s theorem and its relatives. In Proc. Sympos. Pure Math., Vol. VII, pages 101–180. Amer. Math. Soc., Providence, R.I., 1963.

[9] U. Feige, G. Kindler, and R. O’Donnell. Understanding parallel repetition requires understanding foams. In IEEE Conference on Computational Complexity, pages 179–192. IEEE Computer Society, 2007.

[10] A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISEC-TION. Algorithmica, 18(1):67–81, 1997.

[11] P. Gritzmann and V. Klee. Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom., 7(3):255–280, 1992.

[12] J. H�stad. Some optimal inapproximability results. J. ACM, 48(4):798–859 (electronic), 2001.

[13] H. W. E. Jung. über die kleinste kügel, die einerumliche figureinschlisst. J. Reine Angew. Math., 123:241–257, 1901.

[14] 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.

[15] S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? In 45th Annual Symposium on Foundations of Computer Science, pages 146–154. IEEE Computer Society, 2004.

[16] S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357 (electronic), 2007.

[17] 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.

[18] A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic form over intersection of ellipsoids with common center. Math. Program., 86(3, Ser. A):463–473, 1999.

[19] Y. Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw., 9(1-3):141–160, 1998.

[20] 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.

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

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

[23] B. Scholkopf and A. J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA, 2001.

[24] 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.