# On Convergence of Epanechnikov Mean Shift

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2017.

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

- [Convergence Analysis of Mean Shift](https://mlsanity.com/paper/2305.08463/) (2023)
- [GridShift: A Faster Mode-seeking Algorithm for Image Segmentation and Object Tracking](https://mlsanity.com/paper/2206.02200/) (2022)
- [Sketch and shift: a robust decoder for compressive clustering](https://mlsanity.com/paper/2312.09940/) (2023)
- [Convergence Analysis of Blurring Mean Shift](https://mlsanity.com/paper/2402.15146/) (2024)
- [Incomplete Gamma Kernels: Generalizing Locally Optimal Projection Operators](https://mlsanity.com/paper/2205.01087/) (2022)
- [Local Averaging Accurately Distills Manifold Structure From Noisy Data](https://mlsanity.com/paper/2506.18761/) (2025)

## Abstract (arXiv)

Epanechnikov Mean Shift is a simple yet empirically very effective algorithm for clustering. It localizes the centroids of data clusters via estimating modes of the probability distribution that generates the data points, using the `optimal' Epanechnikov kernel density estimator. However, since the procedure involves non-smooth kernel density functions, the convergence behavior of Epanechnikov mean shift lacks theoretical support as of this writing---most of the existing analyses are based on smooth functions and thus cannot be applied to Epanechnikov Mean Shift. In this work, we first show that the original Epanechnikov Mean Shift may indeed terminate at a non-critical point, due to the non-smoothness nature. Based on our analysis, we propose a simple remedy to fix it. The modified Epanechnikov Mean Shift is guaranteed to terminate at a local maximum of the estimated density, which corresponds to a cluster centroid, within a finite number of iterations. We also propose a way to avoid running the Mean Shift iterates from every data point, while maintaining good clustering accuracies under non-overlapping spherical Gaussian mixture models. This further pushes Epanechnikov Mean Shift to handle very large and high-dimensional data sets. Experiments show surprisingly good performance compared to the Lloyd's K-means algorithm and the EM algorithm.