Scalable second-order Riemannian optimization for K-means clustering
Hou, Chun Ying
This item's files can only be accessed by the System Administrators group.
Permalink
https://hdl.handle.net/2142/132799
Description
Title
Scalable second-order Riemannian optimization for K-means clustering
Author(s)
Hou, Chun Ying
Issue Date
2025-12-10
Director of Research (if dissertation) or Advisor (if thesis)
Zhang, Richard Y
Department of Study
Electrical & Computer Eng
Discipline
Electrical & Computer Engr
Degree Granting Institution
University of Illinois Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
K-means clustering
manifold optimization
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
