Approximate kernel clustering

DOI10.1112/S002557930000098XMaRDI QIDQ3400770zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Assaf Naor

Publication date 5 February 2010

Published in Mathematika (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0807.4626

zbMATH Keywords

clusteringpolynomial-time approximability

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: In the kernel clustering problem we are given a large $nimesn$ positive semi-definite matrix $A=(a_{ij})$ with $su{m}_{i,j=1}^n{a}_{ij}=0$ and a small $kimesk$ positive semi-definite matrix $B=(b_{ij})$. The goal is to find a partition $S_1,\mathrm{...},S_k$ of $1,\mathrm{...}n$ which maximizes the quantity ${\displaystyle }$ sum_{i,j=1}^k (sum_{(i,j)in S_i imes S_j}a_{ij})b_{ij}. ${\displaystyle }$ 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 $3imes3$ identity matrix the UGC hardness threshold of this problem is exactly $frac16pi27$. We present and study a geometric conjecture of independent interest which we show would imply that the UGC threshold when $B$ is the $kimesk$ identity matrix is $frac8pi9(1-frac1k)$ for every $kge3$.

Recommendations

• Sharp kernel clustering algorithms and their associated Grothendieck inequalities
• Sharp kernel clustering algorithms and their associated Grothendieck inequalities
• The UGC hardness threshold of the l_p Grothendieck problem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Approximating K‐means‐type Clustering via Semidefinite Programming

Cites work

• A proof of the Grothendieck inequality
• Approximating the Cut-Norm via Grothendieck's Inequality
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Limit theorems for polylinear forms
• Near-optimal algorithms for unique games
• On maximization of quadratic form over intersection of ellipsoids with common center
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Quadratic forms on graphs
• Semidefinite relaxation and nonconvex quadratic optimization
• Some optimal inapproximability results

Cited in

(11)

• Sharp kernel clustering algorithms and their associated Grothendieck inequalities
• Solution of the propeller conjecture in \(\mathbb{R}^3\)
• A complete gradient clustering algorithm formed with kernel estimators
• Grothendieck-type inequalities in combinatorial optimization
• KERNEL METHODS FOR CLUSTERING: COMPETITIVE LEARNING AND c-MEANS
• Standard simplices and pluralities are not the most noise stable
• scientific article; zbMATH DE number 7626745 (Why is no real title available?)
• Solution of the propeller conjecture in R^3
• Clustering by kernel density
• Hierarchical kernel spectral clustering
• UG-hardness to NP-hardness by losing half

This page was built for publication: Approximate kernel clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3400770)