Scalable second-order Riemannian optimization for K-means clustering

Clustering is a fundamental problem in unsupervised learning. The classical K-means formulation for clustering is a worst-case NP-hard discrete optimization problem. Despite being NP-hard, the SDP relaxation of the discrete formulation is guaranteed to recover the true cluster whenever it is statistically solvable. In this thesis, we propose to solve the relaxed K-means problem as an unconstrained optimization problem on a smooth manifold. The proposed manifold can be parametrized by a product manifold with simple structures, allowing the application of second-order Riemannian algorithms. We show how to efficiently implement the cubic-regularized Riemannian Newton method by exploiting the structure of the Hessian. Numerical results show that our proposed algorithm converges faster while achieving similar accuracy compared with existing methods.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Hou, Chun Ying

Contributors dc:contributor

• Zhang, Richard Y

• K-means clustering
• manifold optimization

Statement dc:rights

• Copyright 2025 Chun Ying Hou

Language dc:language

en

Handle dc:identifier

https://hdl.handle.net/2142/132799

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/132799