Kmeans_SDP

Formulated K means clustering, as a semidefinite programming. And solves efficiently using PPXA

K-means clustering is traditionally treated as a non-convex, NP-hard problem often solved via Lloyd's algorithm, which frequently converges to local optima. To address this, the problem can be reformulated as a Semidefinite Programming (SDP) relaxation. By transforming the discrete clustering assignments into a continuous, convex matrix space, the objective becomes the minimization of the trace of the data scatter matrix under specific semidefinite and linear constraints. This relaxation provides a global lower bound and, under certain SNR conditions, guarantees the recovery of the ground-truth clustering.

To solve the resulting large-scale SDP efficiently, the Proximal Parallel Splitting Algorithm (PPXA) is employed. PPXA is a proximal splitting method designed for multi-objective optimization, allowing the complex SDP constraints (such as the semidefinite cone and the stochastic row-sum constraints) to be handled through separate proximal operators. By iteratively applying these operators in parallel, PPXA avoids the high computational cost of generic interior-point methods, making it scalable for the high-dimensional datasets common in modern signal processing.