Approximate Kernel Clustering

In the kernel clustering problem we are given a large ntimesn positive semi-definite matrix A=(a ij ) with Sigma i, j n =1 a ij =0 and a small ktimesk positivesemi-definite matrix B=b ij. The goal is to find a partition S 1, .. S k of {1, .. .n} which maximizes the quantity Sigma i, j=1 k (Sigma (i, j)isinS i timesS j ). 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 forthis 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 3times3 identity matrix the UGC hardness threshold of this problem is exactly 16pi/27. We present and study a geometricconjecture of independent interest which we show would imply thatthe UGC threshold when B is the ktimesk identity matrix is 8pi/9(1-1/k) for every kges3.

Authors

• Subhash Khot
• Assaf Naor

Keywords

• Kernel
• User-generated content
• Machine learning
• Polynomials
• Computer science
• Computational complexity
• Algorithm design and analysis
• Approximation algorithms
• Clustering algorithms
• Machine learning algorithms
• Kernel Clustering
• Identity Matrix
• Estimation Algorithm
• Positive Matrix
• Positive Semidefinite Matrix
• Positive Semidefinite
• Clustering Problem
• Constant Approximation
• Machine Learning Theory
• Approximate Threshold
• Machine Learning Applications
• Polynomial-time Algorithm
• Cholesky Decomposition
• Approximate Ratio
• Standard Vector
• Semidefinite Programming
• Gram Matrix
• Standard Gaussian
• Partitioning Of Elements
• Hardness Results
• Approximation algorithm
• clustering
• inapproximability