3 papers
cs.LG2020
Weighted Cheeger and Buser Inequalities, with Applications to Clustering and Cutting Probability Densities
Timothy Chu, Gary L. Miller, Noel J. Walkington +1
In this paper, we show how sparse or isoperimetric cuts of a probability density function relate to Cheeger cuts of its principal eigenfunction, for appropriate definitions of `spa…
math.OC2020
On convex hulls of epigraphs of QCQPs
Alex L. Wang, Fatma Kilinc-Karzan
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditi…
cs.LG2017
Clustering Stable Instances of Euclidean k-means
Abhratanu Dutta, Aravindan Vijayaraghavan, Alex Wang
The Euclidean k-means problem is arguably the most widely-studied clustering problem in machine learning. While the k-means objective is NP-hard in the worst-case, practitioners ha…