# Kernel k-Medoids as General Vector Quantization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 40 references that are in the map.
- First posted on arXiv 5 Jun 2025.

## Builds on (most cited first, 5 of 5)

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Interpretable Learning for Self-Driving Cars by Visualizing Causal Attention](https://mlsanity.com/paper/1703.10631/) (2017)
- [Towards Bundle Adjustment for Satellite Imaging via Quantum Machine Learning](https://mlsanity.com/paper/2204.11133/) (2022)
- [Dynamic Range Reduction via Branch-and-Bound](https://mlsanity.com/paper/2409.10863/) (2024)
- [Hybrid Quantum-Classical Multi-Agent Pathfinding](https://mlsanity.com/paper/2501.14568/) (2025)

## Abstract (arXiv)

Vector Quantization (VQ) is a widely used technique in machine learning and data compression, valued for its simplicity and interpretability. Among hard VQ methods, k-medoids clustering and Kernel Density Estimation (KDE) approaches represent two prominent yet seemingly unrelated paradigms -- one distance-based, the other rooted in probability density matching. In this paper, we investigate their connection through the lens of Quadratic Unconstrained Binary Optimization (QUBO). We compare a heuristic QUBO formulation for k-medoids, which balances centrality and diversity, with a principled QUBO derived from minimizing Maximum Mean Discrepancy in KDE-based VQ. Surprisingly, we show that the KDE-QUBO is a special case of the k-medoids-QUBO under mild assumptions on the kernel's feature map. This reveals a deeper structural relationship between these two approaches and provides new insight into the geometric interpretation of the weighting parameters used in QUBO formulations for VQ.