Name
Title | ||
|---|---|---|
The surprising secret identity of the semidefinite relaxation of K-means: manifold learning. |
Abstract | ||
|---|---|---|
In recent years, semidefinite programs (SDP) have been the subject of interesting research in the field of clustering. In many cases, these convex programs deliver the same answers as non-convex alternatives and come with a guarantee of optimality. Unexpectedly, we find that a popular semidefinite relaxation of K-means (SDP-KM), learns manifolds present in the data, something not possible with the original K-means formulation. To build an intuitive understanding of its manifold learning capabilities, we develop a theoretical analysis of SDP-KM on idealized datasets. Additionally, we show that SDP-KM even segregates linearly non-separable manifolds. SDP-KM is convex and the globally optimal solution can be found by generic SDP solvers with polynomial time complexity. To overcome poor performance of these solvers on large datasets, we explore efficient algorithms based on the explicit Gramian representation of the problem. These features render SDP-KM a versatile and interesting tool for manifold learning while remaining amenable to theoretical analysis. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Learning | k-means clustering,Discrete mathematics,Nonlinear dimensionality reduction,Mathematics |
DocType | Volume | Citations |
Journal | abs/1706.06028 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mariano Tepper | 1 | 68 | 12.80 |
| Anirvan M Sengupta | 2 | 93 | 10.91 |
| Dmitri B. Chklovskii | 3 | 127 | 25.69 |