# Convex Programming Based Spectral Clustering

arXiv: https://arxiv.org/abs/1805.04246 · HTML: https://mlsanity.com/paper/1805.04246/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2018.

## Built on by (most cited first, 1 of 1)

- [Hyperspectral Image Data Reduction for Endmember Extraction](https://mlsanity.com/paper/2512.10506/) (2025)

## Abstract (arXiv)

Clustering is a fundamental task in data analysis, and spectral clustering has been recognized as a promising approach to it. Given a graph describing the relationship between data, spectral clustering explores the underlying cluster structure in two stages. The first stage embeds the nodes of the graph in real space, and the second stage groups the embedded nodes into several clusters. The use of the k-means method in the grouping stage is currently standard practice. We present a spectral clustering algorithm that uses convex programming in the grouping stage and study how well it works. This algorithm is designed based on the following observation. If a graph is well-clustered, then the nodes with the largest degree in each cluster can be found by computing an enclosing ellipsoid of the nodes embedded in real space, and the clusters can be identified by using those nodes. We show that, for well-clustered graphs, the algorithm can find clusters of nodes with minimal conductance. We also give an experimental assessment of the algorithm's performance.