{"id":"6440ef32-2587-43cd-8eb4-781774826178","arxiv_id":"2506.04786","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"KDE-based vector quantization QUBO is a special case of k-medoids QUBO when the kernel is normalized, and the balancing parameter gamma is 2k/n.","lead":"The authors show that a QUBO formulation for kernel density estimation based vector quantization is a special case of a QUBO formulation for k-medoids, under normalized kernels. This unifies prototype selection frameworks and reinterprets the k-medoids balancing parameter as a geometric scaling factor.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Off-by-one error in Theorem 1 is real and needs a precise fix; the stated λKDE = λMED + 1 does not make Eq. (6) and Eq. (11) equal as written.","rationale":"The reader correctly identifies an off-by-one error in Theorem 1 and proposes the corrected relation λKDE = λMED − 1, which matches my direct re-derivation after correcting the internal λMED typo in Eq. (11). I partially disagree on the precise statement: the equality fails for the stated λKDE = λMED + 1, and the proof hides the discrepancy by inconsistently mixing λMED and λKDE in the final lines. The paper's weaker assumption—the restriction to normalized kernels—is explicitly acknowledged and is not the core problem; the off-by-one error is more concrete and undermines the paper's central theorem as stated. Since the underlying equivalence is recoverable with the corrected parameter relation, a conditional verdict requiring correction is appropriate rather than rejection.","tokens_in":8202,"tokens_out":1910,"duration_ms":20435,"concrete_test":"Run a short numerical check for a concrete normalized kernel (e.g., RBF on n = 5 points, k = 2, fixed bandwidth). Compute QMED from Eq. (6) with D = 11ᵀ − K and QKDE from Eq. (11) (with its λMED corrected to λKDE) for λKDE = λMED + 1 and for λKDE = λMED − 1. Report max|QMED − QKDE| for each. Equality should be zero for exactly one of the two relations, settling which off-by-one correction is correct.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim is Theorem 1, which asserts equality between the QUBO matrices in Eq. (6) and Eq. (11) under γ = 2k/n and λKDE = λMED + 1. Direct computation with D = 11ᵀ − K gives QMED = K + (λMED − 1)11ᵀ + diag[γn1 − γK1 − 2λMEDk1]. With γ = 2k/n this becomes QMED = K + (λMED − 1)11ᵀ + diag[2k1 − (2k/n)K1 − 2λMEDk1] = K + (λMED − 1)11ᵀ − 2 diag[(k/n)K1 + (λMED − 1)k1]. Meanwhile, correcting the evident typo in Eq. (11) (its internal λMED should be λKDE), QKDE = K + λKDE11ᵀ − 2 diag[(k/n)K1 + λKDEk1]. Equating the two requires λKDE = λMED − 1, not λMED + 1. The reader's off-by-one diagnosis is correct: the paper's stated relation fails, and its proof contains a compensating algebraic slip. This is load-bearing because Theorem 1 is the paper's only substantive result. The equivalence is repairable, but the paper as written states a relation that does not hold.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8473,"tokens_out":10429,"duration_ms":103688,"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":[{"comment":"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.","section":"Section IV, Theorem 1"},{"comment":"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.","section":"Section III-B, Eq. (11)"}],"minor_comments":[{"comment":"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.","section":"Section I, final paragraph"},{"comment":"The phrase 'a slightly different versions' should be 'a slightly different version'.","section":"Section III-A"},{"comment":"The phrase 'The foundation stone was layed' should use 'laid' instead of 'layed'.","section":"Section III-A"},{"comment":"The sentence 'could be particularly relevant NISQ devices' is missing the preposition 'for'.","section":"Section V"},{"comment":"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).","section":"Section IV, proof of Theorem 1"},{"comment":"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.","section":"Abstract and Introduction"}],"recommendation":"major_revision","confidential_remarks":"The paper is short and its main contribution is a single algebraic equivalence. The off-by-one error and the typo in Eq. (11) are easily repairable, but as stated the central theorem is false, so a major revision is appropriate rather than a minor one. The paper's scope fits a machine-learning or quantum-optimization venue, and the self-citations are not excessive. I would be willing to review a corrected version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper's one substantive result—that the KDE-based VQ QUBO is a special case of the k-medoids QUBO under normalized kernels—is true, but Theorem 1 states the parameter relation with the wrong sign. The correct relation is λKDE = λMED − 1, not λMED + 1. The proof as written slips twice: it inserts λKDE into the medoids matrix rather than comparing like with like, and Eq. (11) has a typo (λMED inside the diagonal should be λKDE). All of this is fixable, and the central claim survives the correction.\n\nWhat's genuinely new: the explicit QUBO-matrix equivalence under the unit-norm feature-map assumption, and the reading of γ as a geometric scaling factor in kernel-induced feature space. The derivation is elementary, self-contained, and doesn't fit any free parameter to data. For people working on QUBO formulations of VQ for Ising or quantum-annealing hardware, this is a useful unification: it turns a heuristic balancing weight into a principled quantity and gives a parameter mapping between two formulations that have so far lived separate lives. The contribution is niche—it won't change classical clustering or compression practice—but within the niche it's a genuine conceptual step.\n\nSoft spots, in order of severity. First, Theorem 1 is wrong as stated. With D = 11ᵀ − K and γ = 2k/n, direct computation gives QMED = K + (λMED − 1)11ᵀ − 2 diag[(k/n)K1 + (λMED − 1)k1]. Setting that equal to QKDE (with the Eq. (11) typo fixed) forces λKDE = λMED − 1. The paper's proof ends with an expression whose λ-coefficients are λMED, which only matches QKDE if λKDE = λMED; the claimed +1 never enters correctly. Second, Eq. (11) has the internal λMED/λKDE typo. Third, the proof's starting point is not quite the right comparison—substituting λKDE into the medoids matrix is at best a confusing way to derive the equality. Minor: the intro references Section V where the theorem actually appears in Section IV.\n\nThe assumption that kernels are normalized (unit-norm feature maps) is real and clearly stated; it covers RBF, Laplacian, and quantum kernels, so it's adequate for the target audience, but the generality claim shouldn't overshoot.\n\nBottom line: a small, honest theory note with a repairable algebraic error. The authors know how to fix it—it's an off-by-one sign flip. I'd send it to review, ask for a corrected theorem, clean proof, and fixed typo, and then accept it as a credible contribution to the QUBO-VQ literature. The right audience is researchers using QUBO formulations of vector quantization on quantum-inspired hardware, not the general clustering or compression community.","headline":"Off-by-one in the main theorem, but the KDE-VQ / MED-VQ equivalence is real and repairable; worth a review.","tokens_in":8949,"tokens_out":7491,"would_cite":true,"duration_ms":74071,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"KDE-based vector quantization is a special case of kernel k-medoids.","keywords":["vector quantization","k-medoids","kernel density estimation","QUBO","maximum mean discrepancy","normalized kernels","quantum annealing","prototype selection"],"falsifier":"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.","tokens_in":8001,"feed_emoji":"🎯","tokens_out":8339,"duration_ms":86953,"temperature":0.7,"pith_summary":"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.","feed_headline":"Density-based vector quantization is just kernel k-medoids","feed_subtitle":"When kernels are normalized, one QUBO objective covers both approaches — medoid weighting gets a geometric meaning.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduced the QUBO formulation of the k-medoids problem used here as the MED-QUBO baseline, giving the matrix in Eq. (6).","marker":"[25]"},{"why":"Derived the MMD/KDE-based vector quantization objective that the paper reformulates as the KDE-QUBO, giving the matrix in Eq. (11).","marker":"[26]"},{"why":"Fisher's analysis of variance justifies splitting the k-medoids objective into centrality and diversity terms that underlie the MED-QUBO.","marker":"[34]"},{"why":"Mercer's theorem supplies the feature map used to write kernels as inner products, which is what makes the normalized-kernel distance argument work.","marker":"[39]"},{"why":"Maximum mean discrepancy is the divergence whose minimization defines the KDE-VQ objective in Eq. (8).","marker":"[40]"},{"why":"Provides the quantum kernels used in the paper as examples of normalized kernels for which the equivalence holds.","marker":"[28]"}],"fun_headline_variants":["KDE vector quantization is a special case of kernel k-medoids","Kernel k-medoids is the general framework for VQ","KDE-VQ is just kernel k-medoids","One QUBO: KDE-VQ and k-medoids are identical","Kernel k-medoids unifies density-based VQ"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["KDE vector quantization is a special case of kernel k-medoids","Kernel k-medoids is the general framework for VQ","KDE-VQ is just kernel k-medoids","One QUBO: KDE-VQ and k-medoids are identical","Kernel k-medoids unifies density-based VQ"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000715,"raw_usage":{"total_tokens":3184,"prompt_tokens":882,"completion_tokens":2302,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":2215}},"tokens_in":498,"tokens_out":2302,"duration_ms":19988,"temperature":1.0,"reasoning_tokens":2215,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:34:33.772706+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A QUBO formulation of the k-medoids problem","cited_arxiv_id":null,"evidence_quote":"Introduced the QUBO formulation of the k-medoids problem used here as the MED-QUBO baseline, giving the matrix in Eq. (6)."},{"cited_title":"Hopfield networks for vector quantization","cited_arxiv_id":null,"evidence_quote":"Derived the MMD/KDE-based vector quantization objective that the paper reformulates as the KDE-QUBO, giving the matrix in Eq. (11)."},{"cited_title":"On the” probable error","cited_arxiv_id":null,"evidence_quote":"Fisher's analysis of variance justifies splitting the k-medoids objective into centrality and diversity terms that underlie the MED-QUBO."},{"cited_title":"Functions of positive and negative type, and their connection the theory of integral equations","cited_arxiv_id":null,"evidence_quote":"Mercer's theorem supplies the feature map used to write kernels as inner products, which is what makes the normalized-kernel distance argument work."},{"cited_title":"A kernel two-sample test","cited_arxiv_id":null,"evidence_quote":"Maximum mean discrepancy is the divergence whose minimization defines the KDE-VQ objective in Eq. (8)."},{"cited_title":"Supervised learning with quantum-enhanced feature spaces","cited_arxiv_id":null,"evidence_quote":"Provides the quantum kernels used in the paper as examples of normalized kernels for which the equivalence holds."}],"review_version":1}