Pith. sign in

REVIEW 2 major objections 6 minor 40 references

Kernel $k$-Medoids as General Vector Quantization

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read KDE-based vector quantization is a special case of kernel k-medoids.

desk verdict Off-by-one in the main theorem, but the KDE-VQ / MED-VQ equivalence is real and repairable; worth a review. read the letter →

arxiv 2506.04786 v2 pith:GRPSLDUI submitted 2025-06-05 cs.LG quant-ph

classification cs.LGquant-ph
keywords vectorquantizationk-medoidskerneldensityestimationQUBOmaximummeandiscrepancynormalizedkernelsquantumannealingprototypeselection
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to show that two seemingly unrelated ways of compressing a dataset into representative prototypes are actually the same optimization. The first is $k$-medoids clustering, which picks central, mutually distant data points by minimizing distances; the second is kernel density estimation, which picks prototypes by minimizing the maximum mean discrepancy between the data distribution and the prototype distribution. Casting both as quadratic unconstrained binary optimization (QUBO) problems, the paper proves that the KDE formulation is a special case of the medoids formulation whenever the kernel is normalized, i.e., every data point is mapped to the unit sphere in feature space. If true, this unifies distance-based and density-based vector quantization and gives the heuristic weighting parameter in the medoids formulation a geometric meaning.

What carries the argument

The load-bearing object is the QUBO matrix of a binary quadratic program of the form $\min_z z^\top Q z$ with $z\in\{0,1\}^n$. The paper compares the medoids matrix $Q_{\mathrm{MED}}=-D+\lambda_{\mathrm{MED}}\mathbf{1}\mathbf{1}^\top+\operatorname{diag}[\gamma D\mathbf{1}-2\lambda_{\mathrm{MED}}k\mathbf{1}]$ with the KDE matrix built from the kernel matrix $K$ plus a cardinality penalty. The bridge identity is $D=\mathbf{1}\mathbf{1}^\top-K$, which holds because a normalized kernel satisfies $\|\phi(x)\|=1$, making squared feature-space distance proportional to $1-K(x,y)$. Substituting this identity and matching coefficients reduces the KDE objective to the medoids objective.

What would settle it

Take any small dataset with a normalized kernel and compare the diagonal entries of $Q_{\mathrm{MED}}$ with $\gamma=2k/n$ and $\lambda_{\mathrm{KDE}}=\lambda_{\mathrm{MED}}-1$ against $Q_{\mathrm{KDE}}$; equality holds under the corrected relation and fails under the paper's stated $\lambda_{\mathrm{KDE}}=\lambda_{\mathrm{MED}}+1$. A concrete counterexample with an unnormalized kernel whose diagonal values differ would show the normalized-kernel assumption is essential.

Watch

Extended reading notes

Core claim

The central claim is that the QUBO matrix for KDE-based vector quantization equals the QUBO matrix for $k$-medoids when the distance is induced by a normalized Mercer kernel through $D(x,y)=1-K(x,y)$ and the parameters are matched as $\gamma=2k/n$ and $\lambda_{\mathrm{KDE}}=\lambda_{\mathrm{MED}}-1$. The paper states the parameter relation as $\lambda_{\mathrm{KDE}}=\lambda_{\mathrm{MED}}+1$, but the proof's own substitution is consistent only with the corrected minus sign; the special-case claim survives the correction. Under this identification, minimizing the maximum mean discrepancy between the full dataset and the prototype subset is not a separate paradigm: it is the same binary quadratic program as selecting $k$ medoids, with diversity and centrality balanced in a specific kernel-induced geometry.

Load-bearing premise

The equivalence assumes every data point is mapped to a unit-length feature vector by the kernel, so that $D(x,y)=1-K(x,y)$ is a genuine distance; for unnormalized kernels the two QUBO matrices no longer coincide.

Editorial extensions

If this is right

  • KDE-based vector quantization inherits every QUBO solver, penalty-tuning heuristic, and algorithm developed for $k$-medoids, since the two objective matrices coincide at the matched parameters.
  • The parameter $\gamma$, usually viewed as a heuristic balance between centrality and diversity, becomes a scaling factor of the kernel-induced geometry, so tuning it is a geometric choice rather than a magic constant.
  • Because RBF, Laplacian, and quantum kernels are normalized, the equivalence applies to standard and quantum feature spaces, allowing quantum annealing formulations of KDE-VQ to be treated as medoid problems.
  • On quantum-annealing hardware, $\gamma$ influences the spectral gap of the problem Hamiltonian, so it directly affects the time needed to reach the ground state; calibrating $\gamma$ becomes hardware-aware geometry selection.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The parameter relation in the theorem appears to be misprinted: the proof's algebra requires $\lambda_{\mathrm{KDE}}=\lambda_{\mathrm{MED}}-1$, not $+1$, and the matrix equality still goes through with the corrected sign.
  • An unnormalized kernel (where $\|\phi(x)\|$ varies) would break the identity $D=\mathbf{1}\mathbf{1}^\top-K$; replacing the all-ones term by the diagonal of the Gram matrix suggests a natural extension the paper does not develop.
  • If the equivalence is exact, standard medoid heuristics such as PAM-style local search should solve MMD-based prototype selection with no loss of objective fidelity, which is a testable practical prediction.
  • The unification implies that any dataset where distance-based medoid selection and MMD-based prototype selection visibly disagree must be one where the kernel's diagonal is effectively non-constant or the penalties are far from the matched values.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. This paper proposes a structural equivalence between two QUBO formulations of hard vector quantization: a heuristic k-medoids formulation (MED-VQ) and a kernel density estimation formulation based on MMD (KDE-VQ). The authors derive QUBO matrices for both problems, show that under normalized kernels the distance matrix can be written as D = 11^T − K, and state in Theorem 1 that the KDE-QUBO matrix equals the MED-QUBO matrix when γ = 2k/n and λKDE = λMED + 1. They interpret γ as a geometric scaling factor and discuss implications for quantum and Ising-machine optimization. The central claim is Theorem 1 and its corollary for the QBP formulations.

Significance. The claimed equivalence is conceptually attractive: it unifies two seemingly unrelated VQ paradigms and gives a principled interpretation of the balancing parameter γ in the k-medoids QUBO. The derivation is elementary and fully checkable by substitution; no numerical experiments are needed to validate the core algebra. The normalized-kernel assumption is explicitly stated and covers common kernels such as RBF, Laplacian, and quantum kernels. However, the main theorem contains an off-by-one algebraic error, and the QUBO matrix in Eq. (11) contains a typo; both must be corrected before the equivalence claim is valid.

major comments (2)
  1. [Section IV, Theorem 1] The stated parameter relation λKDE = λMED + 1 is algebraically incorrect. Substituting D = 11^T − K and γ = 2k/n into Eq. (6) gives QMED = K + (λMED − 1)11^T − 2 diag[(k/n)K1 + (λMED − 1)k1]. After correcting the typo in Eq. (11), QKDE = K + λKDE 11^T − 2 diag[(k/n)K1 + λKDE k1]. Equality therefore requires λKDE = λMED − 1, not λMED + 1. As written, Theorem 1 is false. The proof's final expression actually corresponds to setting λKDE = λMED, so the proof is internally inconsistent with the stated relation. Because Theorem 1 is the paper's only substantive result, this is a load-bearing error that must be fixed in revision.
  2. [Section III-B, Eq. (11)] The QUBO matrix written for Eq. (10) contains λMED in the diagonal term instead of λKDE. It should read QKDE = K + λKDE 11^T − 2 diag[(k/n)K1 + λKDE k1]. As printed, Eq. (11) is not the QUBO matrix of the objective in Eq. (10) and is inconsistent with the derivation leading to Eq. (10). This typo interacts with the off-by-one error in Theorem 1 and should be corrected in the same revision.
minor comments (6)
  1. [Section I, final paragraph] The text says 'In Sec. V, we state our main theoretical insights and discuss them in Sec. V'; the first reference should be to Sec. IV, where the main results actually appear.
  2. [Section III-A] The phrase 'a slightly different versions' should be 'a slightly different version'.
  3. [Section III-A] The phrase 'The foundation stone was layed' should use 'laid' instead of 'layed'.
  4. [Section V] The sentence 'could be particularly relevant NISQ devices' is missing the preposition 'for'.
  5. [Section IV, proof of Theorem 1] The expression '2 kn/n' in the third line of the proof is a typo; it should be '2k' (arising from nγ with γ = 2k/n).
  6. [Abstract and Introduction] The phrase 'mild assumption' understates the restriction: the equivalence requires normalized kernels, i.e., K(x,x)=1 for all data points, which does not hold for all Mercer kernels. The body of the paper states this correctly; consider adjusting the abstract to match.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the KDE-VQ/MED-VQ equivalence is a self-contained algebraic derivation; the off-by-one parameter relation in Theorem 1 is a sign error, not a circular step.

full rationale

The paper's central claim, Theorem 1, asserts equality of the QUBO matrices in Eq. (6) and Eq. (11) when γ = 2k/n and λKDE = λMED + 1. The derivation is purely algebraic: it substitutes D = 11^T − K (from Proposition 1) into the MED-QUBO and compares the resulting expression to the KDE-QUBO. Both QUBO formulations are explicitly defined in the paper (Eqs. (5)–(6) and Eqs. (10)–(11)), so the claimed equivalence is not assumed as input; it is derived from the definitions of the two objectives. No parameter is fitted to data, and no external benchmark is involved. The self-citations to [25] and [26] merely attribute the original QUBO formulations; the paper restates and proves the necessary expansions itself, so these citations are not load-bearing. The theorem does contain a genuine mathematical error: direct computation gives QMED = K + (λMED − 1)11^T − 2 diag[(k/n)K1 + (λMED − 1)k1], while the KDE matrix is K + λKDE 11^T − 2 diag[(k/n)K1 + λKDE k1]; equality requires λKDE = λMED − 1, not λKDE = λMED + 1 as stated. The proof's intermediate line drops the '+1' from the diagonal term. This is a correctness defect in the stated parameter relation, but it is not circularity: the structural result that KDE-VQ is a special case of MED-VQ remains valid under the corrected relation. The paper therefore contains no self-referential or construction-based circular step, and the appropriate circularity score is 0.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claim rests on a kernel normalization assumption and on standard QUBO penalty machinery; no new entities are introduced, and the only parameter choices are derived from coefficient matching rather than fitted to data.

free parameters (2)
  • gamma (MED-VQ balancing weight) = 2k/n
    Set to 2k/n to match the KDE-VQ objective; derived by coefficient matching, not fitted to data.
  • penalty parameter offset = lambda_KDE = lambda_MED - 1 (corrected); paper claims lambda_MED + 1
    The relationship between penalty parameters is derived from algebra; the paper's stated relation is wrong.
assumptions (3)
  • standard math Mercer's theorem: every Mercer kernel has a feature map φ such that K(x,y) = φ(x)ᵀφ(y)
    Used in Section III-B to rewrite KDE and MMD in inner-product form.
  • domain assumption Normalized kernel assumption: ∥φ(x)∥ = 1 for all x, so K(x,x) = 1 and D(x,y) = 1 - K(x,y) is a distance
    Proposition 1 and Theorem 1 require this; holds for RBF, Laplacian, and normalized quantum kernels.
  • domain assumption QUBO penalty reformulation: for sufficiently large λ, the constrained QBP is equivalent to the penalized QUBO
    Assumed in Section III when passing from Eq. (4) to Eq. (5) and Eq. (9) to Eq. (10).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Kernel $k$-Medoids as General Vector Quantization." pith.science (2026). https://pith.science/paper/GRPSLDUI

@misc{pith2026250604786,
  author       = {Pith},
  title        = {Pith review of: Kernel $k$-Medoids as General Vector Quantization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GRPSLDUI}},
  note         = {Machine review of arXiv:2506.04786}
}
abstract

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    Vector quantization and signal compression

    Allen Gersho and Robert M Gray. Vector quantization and signal compression . Springer Science & Business Media, 2012

  2. [2]

    Learning vec- tor quantization

    Teuvo Kohonen and Teuvo Kohonen. “Learning vec- tor quantization”. In: Self-Organizing Maps (2001), pp. 245–261

  3. [3]

    The coming of age of inter- pretable and explainable machine learning models

    Paulo JG Lisboa et al. “The coming of age of inter- pretable and explainable machine learning models”. In: Neurocomputing 535 (2023), pp. 25–39

  4. [4]

    The importance of interpretability and visualization in machine learning for applications in medicine and health care

    Alfredo Vellido. “The importance of interpretability and visualization in machine learning for applications in medicine and health care”. In: Neural Computing and Applications 32.24 (2020), pp. 18069–18083

  5. [5]

    Interpretable learning for self-driving cars by visualizing causal attention

    Jinkyu Kim and John Canny. “Interpretable learning for self-driving cars by visualizing causal attention”. In: Proceedings of the 2017 International Conference on Computer Vision (ICCV) . IEEE, 2017, pp. 2942–2950

  6. [6]

    Unsupervised word embeddings capture latent knowledge from materials science litera- ture

    Vahe Tshitoyan et al. “Unsupervised word embeddings capture latent knowledge from materials science litera- ture”. In: Nature 571.7763 (2019), pp. 95–98

  7. [7]

    Mean shift, mode seeking, and clus- tering

    Yizong Cheng. “Mean shift, mode seeking, and clus- tering”. In: IEEE Transactions on Pattern Analysis and Machine Intelligence 17.8 (1995), pp. 790–799

  8. [8]

    Some methods for classification and analysis of multivariate observations

    James MacQueen. “Some methods for classification and analysis of multivariate observations”. In: Proceed- ings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. V ol. 5. University of Califor- nia Press. 1967, pp. 281–298

Show all 40 references
  1. [9]

    Least squares quantization in PCM

    Stuart P Lloyd. “Least squares quantization in PCM”. In: IEEE Transactions on Information Theory 28.2 (1982), pp. 129–137

  2. [10]

    Clustering by means of medoids

    Leonard Kaufman and Peter J Rousseeuw. “Clustering by means of medoids”. In: Proceedings of the First International Conference on Statistical Data Analysis Based on the L1-Norm (1987), pp. 405–416

  3. [11]

    Infor- mation theoretic vector quantization with fixed point updates

    Sudhir Rao, Seungju Han, and Jose Principe. “Infor- mation theoretic vector quantization with fixed point updates”. In: 2007 International Joint Conference on Neural Networks (IJCNN). IEEE. 2007, pp. 1020–1024

  4. [12]

    A reproducing kernel Hilbert space framework for information-theoretic learning

    Jian-Wu Xu et al. “A reproducing kernel Hilbert space framework for information-theoretic learning”. In: IEEE Transactions on Signal Processing 56.12 (2008), pp. 5891–5902

  5. [13]

    NP-hardness of Euclidean sum- of-squares clustering

    Daniel Aloise et al. “NP-hardness of Euclidean sum- of-squares clustering”. In: Machine learning 75 (2009), pp. 245–248

  6. [14]

    The quadratic unconstrained bi- nary optimization problem

    Abraham P Punnen. The quadratic unconstrained bi- nary optimization problem . Springer, 2022

  7. [15]

    Ising machines as hardware solvers of combinatorial optimization problems

    Naeimeh Mohseni, Peter L McMahon, and Tim Byrnes. “Ising machines as hardware solvers of combinatorial optimization problems”. In: Nature Reviews Physics 4.6 (2022), p. 363

  8. [16]

    Quantum computation and quantum information

    Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge Uni- versity Press, 2010

  9. [17]

    Quantum annealing in the transverse Ising model

    Tadashi Kadowaki and Hidetoshi Nishimori. “Quantum annealing in the transverse Ising model”. In: Physical Review E 58.5 (1998), p. 5355

  10. [18]

    Adiabatic quan- tum computation

    Tameem Albash and Daniel A Lidar. “Adiabatic quan- tum computation”. In: Reviews of Modern Physics 90.1 (2018), p. 015002

  11. [19]

    Quantum computing in the NISQ era and beyond

    John Preskill. “Quantum computing in the NISQ era and beyond”. In: Quantum 2 (2018), p. 79

  12. [20]

    Towards bundle adjustment for satellite imaging via quantum machine learning

    Nico Piatkowski et al. “Towards bundle adjustment for satellite imaging via quantum machine learning”. In: Proceedings of the 25th International Conference on Information Fusion (FUSION) . IEEE, 2022, p. 1

  13. [21]

    Quantum optimization for FPGA- placement

    Thore Gerlach et al. “Quantum optimization for FPGA- placement”. In: Proceedings of the 2024 IEEE In- ternational Conference on Quantum Computing and Engineering (QCE). IEEE, 2024, pp. 637–647

  14. [22]

    Optimum-preserving QUBO parameter compression

    Sascha M ¨ucke, Thore Gerlach, and Nico Piatkowski. “Optimum-preserving QUBO parameter compression”. In: Quantum Machine Intelligence 7.1 (2025), p. 1

  15. [23]

    Hybrid quantum-classical multi- agent pathfinding

    Thore Gerlach et al. “Hybrid quantum-classical multi- agent pathfinding”. In: Proceedings of the 42nd In- ternational Conference on Machine Learning (ICML) . PMLR, 2025

  16. [24]

    Dynamic range reduction via branch-and-bound

    Thore Gerlach and Nico Piatkowski. “Dynamic range reduction via branch-and-bound”. In: Proceedings of the 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) . IEEE, 2025

  17. [25]

    A QUBO formulation of the k-medoids problem

    Christian Bauckhage et al. “A QUBO formulation of the k-medoids problem”. In: Proceedings of the Conference on “Lernen, Wissen, Daten, Analysen” (LWDA). CEUR- WS.org, 2019, p. 54

  18. [26]

    Hopfield networks for vector quantization

    C. Bauckhage, R. Ramamurthy, and R. Sifa. “Hopfield networks for vector quantization”. In: Proceedings of the 29th International Conference on Artificial Neural Networks (ICANN). Springer, 2020, p. 192

  19. [27]

    Quadratic binary programming with application to capital-budgeting problems

    DJ Laughhunn. “Quadratic binary programming with application to capital-budgeting problems”. In: Opera- tions research 18.3 (1970), p. 454

  20. [28]

    Supervised learning with quantum-enhanced feature spaces

    V ojt ˇech Havl ´ıˇcek et al. “Supervised learning with quantum-enhanced feature spaces”. In: Nature 567.7747 (2019), pp. 209–212

  21. [29]

    Quantum-hybrid neural vector quantization–a mathematical approach

    Thomas Villmann and Alexander Engelsberger. “Quantum-hybrid neural vector quantization–a mathematical approach”. In: Proceedings of the 21st International Conference on Artificial Intelligence and Soft Computing (ICAISC) . Springer. 2021, pp. 246–257

  22. [30]

    Steps forward to quantum learning vector quantization for classification learning on a theoretical quantum computer

    Alexander Engelsberger, Ronny Schubert, and Thomas Villmann. “Steps forward to quantum learning vector quantization for classification learning on a theoretical quantum computer”. In: Proceedings of the 14th Inter- national Workshop on Self-Organizing Maps (WSOM) . Springer. 2...

  23. [31]

    Quantum-Inspired Learning Vector Quantization for Classification Learning

    Thomas Villmann et al. “Quantum-Inspired Learning Vector Quantization for Classification Learning.” In: Proceedings of the 28th European Symposium on Ar- tificial Neural Networks (ESANN) . 2020, pp. 279–284

  24. [32]

    Quantum ap- proaches for medoid clustering

    Thom Sijpesteijn and Frank Phillipson. “Quantum ap- proaches for medoid clustering”. In: Proceedings of the 23rd International Conference on Innovations for Com- munity Services (I4CS) . Springer. 2023, pp. 222–235

  25. [33]

    Quantum-ready vector quantization: Prototype learning as a binary optimization problem

    Alexander Engelsberger and Thomas Villmann. “Quantum-ready vector quantization: Prototype learning as a binary optimization problem”. In: Proceedings of the 31st European Symposium on Artificial Neural Networks (ESANN) . 2023

  26. [34]

    On the” probable error

    Ronald A Fisher. “On the” probable error” of a coeffi- cient of correlation deduced from a small sample”. In: Metron 1 (1921), pp. 3–32

  27. [35]

    Alleviating the quantum Big-M problem

    Edoardo Alessandroni et al. “Alleviating the quantum Big-M problem”. In: arXiv preprint arXiv:2307.10379 (2023)

  28. [36]

    The Cauchy–Schwarz divergence and Parzen windowing: Connections to graph theory and Mercer kernels

    Robert Jenssen et al. “The Cauchy–Schwarz divergence and Parzen windowing: Connections to graph theory and Mercer kernels”. In: Journal of the Franklin In- stitute 343.6 (2006), p. 614

  29. [37]

    On informa- tion and sufficiency

    Solomon Kullback and Richard A Leibler. “On informa- tion and sufficiency”. In: The Annals of Mathematical Statistics 22.1 (1951), p. 79

  30. [38]

    Vector quantization using information theoretic concepts

    Tue Lehn-Schiøler et al. “Vector quantization using information theoretic concepts”. In: Natural Computing 4.1 (2005), p. 39

  31. [39]

    Functions of positive and negative type, and their connection the theory of integral equations

    James Mercer. “Functions of positive and negative type, and their connection the theory of integral equations”. In: Philosophical Transactions of the Royal Society of London 209 (1909), p. 415

  32. [40]

    A kernel two-sample test

    Arthur Gretton et al. “A kernel two-sample test”. In: The Journal of Machine Learning Research13.1 (2012), p. 723

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.