A Semi-Definite Programming approach to low dimensional embedding for unsupervised clustering
This work addresses clustering challenges for high-dimensional data analysis, but it appears incremental as it builds on existing methods with specific optimizations.
The paper tackles the problem of unsupervised clustering in high-dimensional data by proposing a Semi-Definite Programming variant to estimate cluster matrices, deducing a clustering-oriented embedding with theoretical guarantees and demonstrating performance via Monte Carlo experiments and comparisons.
This paper proposes a variant of the method of Guédon and Verhynin for estimating the cluster matrix in the Mixture of Gaussians framework via Semi-Definite Programming. A clustering oriented embedding is deduced from this estimate. The procedure is suitable for very high dimensional data because it is based on pairwise distances only. Theoretical garantees are provided and an eigenvalue optimisation approach is proposed for computing the embedding. The performance of the method is illustrated via Monte Carlo experiements and comparisons with other embeddings from the literature.