Rice Header
CAAM Header

Graduate Seminar - 11/15, 12:00PM Duncan Hall 1064

Yuchen Yang

"Clustering by Subspace Matching: Convergence Analysis and More"

Data clustering is a fundamental unsupervised machine learning problem. The most widely used method of data clustering over the decades has been k-means. Recently, a newly proposed algorithm called KindAP, based on the idea of subspace matching and a semi-convex relaxation scheme, outperforms k-means in many aspects, such as no random replication and insensitivity to initialization. Unlike k-means, empirical evidence suggests that KindAP can correctly identify well-separated globular clusters even when the number of clusters is large, but a rigorous theoretical analysis is necessary. This study improves the algorithm design and establishes the first-step theory for KindAP. KindAP is actually a two-layered alternating projection procedure applied to two non-convex sets. The inner loop solves an intermediate model via a semi-convex relaxation scheme that relaxes one more complicated non-convex set while keeping the other intact. We first derive a convergence result for this inner loop. Then under the "ideal data" assumption where n data points are exactly located at k positions, we prove that KindAP converges globally to the global minimum with the help of outer loop. Further work is ongoing to extend this analysis from the ideal data case to more general cases.

Department of Computational and Applied Mathematics
6100 Main MS-134   Houston, TX 77005   713.348.4805

Rice University   |   School of Engineering   |   J. Joyce Young Memorial Fund   |   Pearlman Memorial Fund   |   Weiser Memorial Fund   |   Contact