A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
EGAE improves graph clustering by utilizing GAE's representations in a way consistent with relaxed k-means theory.
A new Wasserstein -means method for clustering probability distributions.
Efficient algorithms for -means clustering frequently converge to suboptimal partitions, and given a partition, it is difficult to detect -means optimality. In this paper, we develop an a posteriori certifier of approximate optimality for -means clustering. The certifier is a sub-linear Monte Carlo algorithm b…
Recently, Awasthi et al. introduced an SDP relaxation of the -means problem in . In this work, we consider a random model for the data points in which balls of unit radius are deterministically distributed throughout , and then in each ball, points are drawn according to a common ro…
We introduce a model-free relax-and-round algorithm for k-means clustering based on a semidefinite relaxation due to Peng and Wei. The algorithm interprets the SDP output as a denoised version of the original data and then rounds this output to a hard clustering. We provide a generic method for proving performance guar…
We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: -means and -median clustering. Motivations for focusing on convex relaxations are: (a) they come with a certificate of optimality, and…
We introduce the {\it diffusion -means} clustering method on Riemannian submanifolds, which maximizes the within-cluster connectedness based on the diffusion distance. The diffusion -means constructs a random walk on the similarity graph with vertices as data points randomly sampled on the manifolds and edges as …
Study finds the cutoff for exact recovery in Gaussian mixture models.
New method speeds up k-means clustering using sketch-and-solve.
New algorithm improves clustering accuracy without sacrificing scalability.
The K-means algorithm is arguably the most popular data clustering method, commonly applied to processed datasets in some "feature spaces", as is in spectral clustering. Highly sensitive to initializations, however, K-means encounters a scalability bottleneck with respect to the number of clusters K as this number grow…
This paper studies the optimality of kernel methods in high-dimensional data clustering. Recent works have studied the large sample performance of kernel clustering in the high-dimensional regime, where Euclidean distance becomes less informative. However, it is unknown whether popular methods, such as kernel k-means, …
Plain vanilla K-means clustering has proven to be successful in practice, yet it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outl…
A new framework improves fairness in clustering and Wasserstein Barycenter problems.
Finding the optimal -means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the -means objective. We first show how to extend Lloyd's batched relocation heuristic and Hartigan's single-point relocation heuristic to take into account empty-cluster and single-poin…
Clustering is one of the most important unsupervised problems in machine learning and statistics. Among many existing algorithms, kernel k-means has drawn much research attention due to its ability to find non-linear cluster boundaries and its inherent simplicity. There are two main approaches for kernel k-means: SVD o…
New algorithm solves large cardinality-constrained clustering problems.
Bayesian models offer great flexibility for clustering applications---Bayesian nonparametrics can be used for modeling infinite mixtures, and hierarchical Bayesian models can be utilized for sharing clusters across multiple data sets. For the most part, such flexibility is lacking in classical clustering methods such a…
A fast algorithm for -means clustering using subsampled SDP.
The current trend of pushing CNNs deeper with convolutions has created a pressing demand to achieve higher compression gains on CNNs where convolutions dominate the computation and parameter amount (e.g., GoogLeNet, ResNet and Wide ResNet). Further, the high energy consumption of convolutions limits its deployment on m…
The classical mixture of Gaussians model is related to K-means via small-variance asymptotics: as the covariances of the Gaussians tend to zero, the negative log-likelihood of the mixture of Gaussians model approaches the K-means objective, and the EM algorithm approaches the K-means algorithm. Kulis & Jordan (2012) us…
New clustering method for exponential family data.
Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly little theory about performance guarantees for spectral clustering. This issue is partly due to the…
Graph based clustering is one of the major clustering methods. Most of it work in three separate steps: similarity graph construction, clustering label relaxing and label discretization with k-means. Such common practice has three disadvantages: 1) the predefined similarity graph is often fixed and may not be optimal f…
Clustering is a fundamental problem in many scientific applications. Standard methods such as -means, Gaussian mixture models, and hierarchical clustering, however, are beset by local minima, which are sometimes drastically suboptimal. Recently introduced convex relaxations of -means and hierarchical clustering s…
Breathing k-means outperforms greedy k-means++ in clustering.
Data clustering is a fundamental problem with a wide range of applications. Standard methods, eg the -means method, usually require solving a non-convex optimization problem. Recently, total variation based convex relaxation to the -means model has emerged as an attractive alternative for data clustering. However…
Improved K-Means++ and K-Means with faster run-time.
For a certain class of distributions, we prove that the linear programming relaxation of -medoids clustering---a variant of -means clustering where means are replaced by exemplars from within the dataset---distinguishes points drawn from nonoverlapping balls with high probability once the number of points drawn a…
Local network community detection is the task of finding a single community of nodes concentrated around few given seed nodes in a localized way. Conductance is a popular objective function used in many algorithms for local community detection. This paper studies a continuous relaxation of conductance. We show that con…
A new -means method HT -means uses penalty for sparsity.
Modified K-means ensures local optimality with same complexity.
-means algorithm is one of the most classical clustering methods, which has been widely and successfully used in signal processing. However, due to the thin-tailed property of the Gaussian distribution, -means algorithm suffers from relatively poor performance on the dataset containing heavy-tailed data or outlie…
Clustering is a separation of data into groups of similar objects. Every group called cluster consists of objects that are similar to one another and dissimilar to objects of other groups. In this paper, the K-Means algorithm is implemented by three distance functions and to identify the optimal distance function for c…
Paper improves clustering risk bounds for kernel k-means.
Ball k-means reduces point-centroid distance computations for faster k-means clustering.
A new k-means variant minimizes pairwise distances within clusters.
TS-K-means improves financial data clustering with dynamic time warping.
Paper proposes a novel unsupervised feature selection method using K-means and ADMM.
A faster Wasserstein k-means algorithm for histogram data reduces computation and maintains clustering quality.
A new -means method improves clustering accuracy and robustness.
We show that -means (Lloyd's algorithm) is obtained as a special case when truncated variational EM approximations are applied to Gaussian Mixture Models (GMM) with isotropic Gaussians. In contrast to the standard way to relate -means and GMMs, the provided derivation shows that it is not required to consider Gau…
Two algorithms improve K-means clustering speed without sacrificing quality.
Motivated by the task of clustering either variables or points into groups, we investigate efficient algorithms to solve the Peng-Wei (P-W) -means semi-definite programming (SDP) relaxation. The P-W SDP has been shown in the literature to have good statistical properties in a variety of settings, but rem…
We address the problem of simultaneously learning a k-means clustering and deep feature representation from unlabelled data, which is of interest due to the potential of deep k-means to outperform traditional two-step feature extraction and shallow-clustering strategies. We achieve this by developing a gradient-estimat…
The paper provides guarantees for clustering validity without distributional assumptions.
The study investigates the consistency of -means clustering under finite expectation assumptions.
The paper assesses conditions for the uniqueness of k-means clustering.