PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering

Yordan P. Raykov, Max A. Little

arXiv:2609.30477v1math.STcs.LGstat.TH

TL;DR

Exact Euclidean K-means faces a combinatorial search over unlabelled partitions, and an SSE optimum need not match generating groups. The paper uses data-derived graph scaffolds to restrict an exact subset dynamic program while retaining the SSE objective. Under stated compact-support conditions, a logarithmic nearest-neighbour rank preserves an empirical optimum with probability tending to one; the paper also studies graph coverage and scaffold-guided mixture proposals.

  • Problem

    Exact Euclidean K-means is combinatorially difficult, and optimizing SSE is distinct from recovering the scientific groups of interest.

    Source: §1 · p. 2

  • Method

    The paper restricts subset dynamic programming to connected clusters in data-derived scaffolds and uses scaffold geometry to guide split-merge proposals without restricting the mixture posterior.

    Source: §1 · p. 3, §3.4 · p. 10, §6 · p. 24

  • Results

    Delaunay connectivity preserves a planar two-cluster SSE optimum; geometric split-merge proposals have higher acceptance, but matched-iteration posterior accuracy varies by model and summary.

    Source: §6 · p. 24

  • Takeaways & Limitations

    In a nested scaffold family, the first member preserving an unrestricted optimum has the smallest support among covering members; geometric proposals do not by themselves ensure more accurate posterior estimates.

    Source: §6 · p. 24

    A vanishing edge fraction does not imply polynomial subset-DP complexity, and compact-support coverage does not automatically extend to untruncated mixtures.

    Source: §4.2 · p. 16

Abstract

from arXiv · show

Exact Euclidean \(K\)-means partitions \(n\) observations into \(K\) unlabelled clusters, but the unrestricted search is generally exponential. We use data-derived geometric graphs to precondition an exact subset dynamic program: as a result only connected vertex subsets are admitted as clusters, while sum-of-squared-errors (SSE) loss is unchanged. A remaining-set recurrence minimises fixed-\(K\) or penalised SSE, with exact factorisation over the connected components of each remaining set. The central question we study is how much computational support can be removed while preserving an unrestricted optimum. Graph inclusion gives monotone coverage and support relations, and a bottleneck threshold identifies the first covering graph in a nested hierarchy. For fixed \(K\) and dimension, under compact ball support and density bounds, retaining \(q=O(\log n)\) nearest neighbours per observation preserves an empirical SSE optimum with probability tending to one, using an \(O(\log n/n)\) fraction of complete-graph edges. Truncated Gaussian mixtures with unequal weights and covariances satisfy these conditions. The rate we provide is a sufficient upper bound rather than a result implying polynomial optimisation complexity. Objective-matched synthetic and full-data comparisons assess coverage, compression, and reference-label agreement. As a secondary application, we illustrate how the proposed scaffold preconditioning can be utilized to improve the efficiency of split-merge proposals that preserve unrestricted mixture posteriors.

1 Introduction

Exact SSE clustering searches an enormous space of unlabelled partitions, and an SSE optimum need not recover the generating groups. The paper restricts candidate clusters using data-derived graphs while retaining the SSE criterion, then studies when this restriction preserves an unrestricted optimum.

1 Introduction

  • Exact Euclidean K-means is NP-hard in general, while common Lloyd-type methods depend on initialization and an SSE optimum may differ from generating mixture labels.The paper distinguishes optimizing a criterion from recovering scientific groups of interest.Source: §1 · p. 2
  • In one dimension, sorting makes optimal fixed-K clusters contiguous, so a Bellman recurrence combines interval costs with solved prefix problems.This gain comes from a geometrically justified restriction of candidate clusters, not a replacement of the loss.Source: §1 · p. 2
  • A geometric scaffold admits only connected vertex sets as clusters while leaving ordinary SSE unchanged; paths, trees, and complete graphs impose different restrictions.Because the graph varies with the observations, its effects on statistical estimation and computational difficulty can be studied together.Source: §1 · p. 2
  • The remaining-set DP selects the block containing the least-indexed remaining observation, reuses the smaller-set solution, and factors disconnected remaining sets into component problems.It supports fixed-K and cluster-count-penalized SSE.Source: §1 · p. 2
  • With fixed K and dimension, q=O(log n) nearest neighbours suffice to preserve an empirical SSE optimum with probability tending to one under compact-ball support and density bounds.The sufficient bound includes truncated Gaussian mixtures with unequal weights and covariances; it does not require agreement with generating labels.Source: §1 · p. 3
  • The empirical study assesses coverage and search reduction, while a complementary application tests scaffold-guided split-merge proposals without restricting the mixture posterior.The proposal application evaluates sampling efficiency without changing the inferential target.Source: §1 · p. 3

2 Clustering objectives and scaffold constraints

This section formulates clustering as optimization over unlabelled partitions and defines how a graph scaffold restricts admissible clusters. It distinguishes changing the feasible partition family from changing the SSE objective or making optimization efficient.

2 Clustering objectives and scaffold constraints

  • A partition is the estimation object: relabelling cluster labels leaves its equivalence classes and grouped observations unchanged.An allocation vector encodes the same partition, but label permutations do not change the partition.Source: §2 · p. 3
  • For fixed K≥2, S(n,K) ~ K^n/K!; when K varies, the partition family has size equal to the nth Bell number, not an optimization-cost lower bound.The fixed-K count follows by counting label allocations, excluding unused labels, and removing label permutations.Source: §2 · pp. 3–4
  • A scaffold is a graph that admits a cluster only when its induced subgraph is connected, leaving that cluster's SSE unchanged.A partition is H-realizable when every block induces a connected subgraph of H.Source: §2 · p. 4
  • The complete graph admits every partition; the formulation also considers fixed-cluster-count and penalized objectives.The chosen cluster count or penalty is retained when optimization is unrestricted.Source: §2 · p. 4
  • A scaffold changes the family over which the criterion is minimized, but preserving an unrestricted optimum is distinct from computing the restricted minimum efficiently.The criterion itself remains unchanged.Source: §2 · p. 4

3 Subset dynamic programming and scaffold preconditioning

The subset dynamic program optimizes partitions by reusing remaining-set subproblems, then restricts candidate clusters to connected sets on a scaffold without changing SSE. The paper studies when this restriction preserves an unrestricted optimum, how it reduces computational support, and how scaffold geometry can guide posterior-preserving proposals.

3.1 Exact optimization over unlabeled partitions

  • The first-block rule gives each unlabeled partition a unique sequence, and the recurrence reuses memoized remaining-set solutions to minimize fixed-K SSE.The first block contains the least-indexed remaining observation; the resulting subproblem is indexed by the remaining set and number of blocks required.Source: §3.1 · p. 5
  • Subset reuse replaces independent partition enumeration, but unrestricted SSE optimization remains exponential and is not made tractable by memoization alone.Source: §3.1 · p. 5

3.2 Scaffold preconditioning of subset dynamic programming

  • The scaffold-constrained recurrence admits only connected blocks while retaining the SSE loss, and its value is the exact optimum among partitions on that scaffold.Source: §3.2 · pp. 6–7
  • A disconnected remaining set factors over its graph components; the required cluster counts couple component fits, and feasibility conditions support the factorization.The method records componentwise minimizing allocations to recover a minimizing partition.Source: §3.2 · pp. 7–8

3.3 Computational support and the coverage-compression trade-off

  • Under scaffold inclusion, admissible blocks, reachable subproblems, and supported transitions are monotone, so the first covering graph in a nested family has the least computational support among covering members.Actual running time still depends on how support is explored and stored.Source: §3.3 · pp. 8–9
  • A path scaffold yields at most (n + 1)(K + 1) reached pairs, while equal edge counts need not imply equal numbers of connected blocks or computational support.The path and star each have n − 1 edges but different connected-block counts.Source: §3.3 · p. 9

3.4 The scaffold as proposal geometry for posterior partitions

  • Scaffold-guided split-merge moves can use graph structure in proposals while preserving the mixture posterior under the stated assumptions.For κ > 0, allocation favors the subcluster containing more of an observation’s scaffold neighbors; irreducibility and aperiodicity require additional sampler properties.Source: §3.4 · p. 10

4 Coverage of an unrestricted SSE optimum

The section characterizes when graph-constrained partitions retain an unrestricted SSE optimum and gives a sufficient sparse-neighbour condition for that coverage. It also distinguishes coverage from successful restricted optimization and from recovery of reference labels.

4.1 Exact coverage and deterministic connectivity

  • The scaffold-restriction gap and restricted-search gap are distinct: exact scaffold optimization removes only the latter, while coverage makes the former vanish.ARI and NMI assess reference-label agreement and are not generally monotone in SSE.Source: §4.1 · p. 11
  • The first covering graph in a nested scaffold hierarchy is determined by the smallest connectivity threshold among unrestricted SSE optima.A partition becomes feasible when every block has a spanning tree in the scaffold; only one tied optimum needs to become feasible.Source: §4.1 · pp. 11–12
  • If an Euclidean MST connects every block of an unrestricted SSE optimum, that MST and every scaffold containing it preserve the optimum.The stated within-block connectivity condition is sufficient, not necessary, for MST coverage.Source: §4.1 · p. 12

4.2 Model-dependent exact q-NN coverage

  • For fixed dimension and K under compact support, q_n=O(log n) suffices for exact empirical-optimum coverage, with an O(log n/n) edge fraction almost surely.The theorem bounds coverage failure by localization, tail, empty-cell-neighbourhood, and excessive-neighbour-count terms.Source: §4.2 · pp. 15–16
  • For compactly supported finite Gaussian mixtures with positive weights and positive-definite covariances, the coverage conclusions do not require a unique population optimum or matching K to component count.The assumptions also allow unequal mixture weights and covariances.Source: §4.2 · p. 16
  • The logarithmic-rank guarantee is sufficient rather than sharp; mixture overlap alone does not order coverage, and density and geometric constants affect the required rank.Low within-cell density or narrow cells can increase the needed radius, while high ambient density raises the rank needed to retain connections.Source: §4.2 · p. 16
  • A vanishing edge fraction does not establish polynomial DP complexity, and the compact-support result does not automatically extend to untruncated mixtures.Allowing the ball radius to grow can reduce the tail term while worsening density and geometric constants.Source: §4.2 · p. 16

5 Experiments

The experiments test how scaffold choice affects computation, SSE-optimum coverage, and agreement with reference labels, then examine scaffold guidance for posterior proposals. Results distinguish exact optimization on a scaffold from unrestricted optimality and statistical agreement.

5.1 Objective-matched clustering comparisons

  • Gabriel and Delaunay matched the complete-graph optimum on all 120 samples; exact 2-NN-MST did so on 117, versus 113 for 20-restart k-means++.Mean relative SSE gaps were 0.032% for 2-NN-MST and 0.065% for 20-restart k-means++; their mean VI values were 0.825 bits for the unrestricted optimum and 0.813 bits for restarted k-means++.Source: §5.1 · p. 17, Figure 1 · p. 17
  • Removing edges can reduce candidate clusters and subproblems, but edge density alone does not determine reductions in connected blocks, supported transitions, or reachable remaining sets.The fixed-K coverage and support measures are normalized by the corresponding complete-recurrence counts; the table caption defines coverage across 120 data sets.Source: §5.1 · p. 17, Table 1 · p. 18
  • Appendix comparisons report exact factorization values and partition counts in all 32 paired evaluations, with fewer block inspections but not uniformly fewer stored values.Structural controls distinguish scaffold exclusion from local-search failure; the separability sweep assesses candidate connectivity, not unrestricted-optimum coverage.Source: §5.1 · p. 17

5.2 Scaffold restriction for nonconvex groups

  • On two moons, the intact MST permits 59 connected two-block partitions, whereas pruning its longest edge leaves only the forced two-component partition.Pruning reproduces single linkage at K = 2; the construction recovers the moons only when the edge-length separation is appropriate, and noise can reduce their agreement.Source: §5.2 · pp. 18, 20

5.3 Clustering comparisons on UCI data

  • On the UCI data, exact MST fits improved Soybean SSE by 5.192% with perfect label agreement, but exact MST fits on Iris, Wine, and Breast Cancer had higher SSE and lower ARI/NMI than single-start baselines.On Vehicle, exact MST SSE improved on random Lloyd and one-start k-means++ by 2.858% and 3.000%, with ARI 0.106 and NMI 0.141; enriched Iris H2 remained above one-start k-means++ SSE.Source: Table 2 · p. 20, §5.3 · p. 21

5.4 Scaffold-informed posterior exploration

  • At 2,500 sweeps, 3-NN guidance raised split-merge acceptance from 1.950% to 2.540% for finite mixtures, 1.090% to 1.860% for DP, and 2.250% to 4.330% for NGGP.Permutation reduced acceptance below generic proposals throughout; posterior accuracy showed no uniform corresponding gain at matched iterations.Source: §5.4 · p. 22, Figure 3 · p. 23
  • For NGGP, guided samplers had final PSM RMSE about 1.300×10^-3, but values were similar to Gibbs at 1.283 × 10^-3 and the permuted control at 1.317 × 10^-3.Increasing guidance from 2-NN to 3-NN reduced DP PSM RMSE from 1.038 × 10^-3 to 8.104 × 10^-4, but increased finite-mixture RMSE from 1.771 × 10^-3 to 5.798 × 10^-3.Source: §5.4 · p. 22, Figure 3 · p. 23

6 Discussion

Scaffolds link admissible-cluster choice to exact-search support, and the required neighbour count can preserve an unrestricted SSE optimum under stated compact-support conditions. Exact optimization can separate criterion minimization from group recovery, while geometric proposals can improve acceptance without guaranteeing more accurate posterior estimates.

6 Discussion

  • For fixed d and K, qn = O(log n) neighbours suffice asymptotically for empirical SSE optimum preservation under compact-ball support and density bounds, though the search can remain exponential.The bound is sufficient; the conclusion does not require recovery of generating mixture labels.Source: §6 · p. 24
  • In the two-moons example, the generating partition is feasible on the MST but does not minimize SSE; pruning can recover it when within-group connectivity remains below between-group distance.Recovery deteriorates as noise closes that gap.Source: §6 · p. 24
  • Geometric split-merge proposals had higher acceptance across three mixture models, but relative posterior accuracy at matched iterations depended on model and summary.The proposal correction preserves the unrestricted mixture posterior; higher acceptance alone does not ensure more accurate estimates.Source: §6 · p. 24

A.1 Proof of Theorem 1

The proofs establish the subset recurrence by a first-block decomposition, factor partitions over connected components, and show that adding graph edges monotonically expands feasible blocks and preserves coverage.

A.1 Proof of Theorem 1

  • Each feasible partition has a unique first block containing the least-indexed observation, yielding the remaining-set recurrence; boundary and infeasible cases match the partition objective.The proof uses induction on the remaining-set size and block-additive SSE plus any cluster penalty.Source: §A.1 · p. 25

A.2 Proof of Proposition 1

  • Every connected block lies within one component of H[S], so partition optimization factors across components with cluster counts allocated among them.A feasible k-partition exists exactly when the number of components is at most k and k is at most |S|.Source: §A.2 · p. 26

A.3 Proof of Proposition 2

  • If EH ⊆ EH′, then connected-block dictionaries, reachable states, and feasible partitions are nested, and adding edges cannot worsen the optimum.Coverage by H implies coverage by H′, with equality of optima when H already covers an unrestricted optimum.Source: §A.3 · pp. 26–27

B Deterministic coverage proofs

For nested scaffolds, a lexicographic recurrence identifies the earliest graph covering an unrestricted optimum. MST connectivity and radius conditions provide deterministic routes to coverage by MST and nearest-neighbour graphs.

B.1 Nested thresholds and the lexicographic recurrence

  • The minimum bottleneck threshold among unrestricted SSE optima identifies the first covering scaffold in a nested hierarchy.A lexicographic remaining-set recurrence first minimizes SSE and then minimizes the maximum block threshold among tied optima.Source: §B.1 · pp. 27–28

B.2 MST, radius, and nearest-neighbour connectivity

  • An unrestricted optimum whose blocks have within-block connectivity radii below between-block distances is covered by any Euclidean MST and its supergraphs.For a block A, its MST longest-edge threshold determines when a radius graph on A becomes connected; a bound on radius-neighbour counts transfers coverage to q-nearest-neighbour graphs.Source: §B.2 · p. 28

C Probabilistic nearest-neighbour coverage proofs

The probabilistic argument localizes empirical optima, uniformly ensures sample points within their fitted cells, and bounds neighbour counts to obtain exact scaffold coverage. Under compact-support conditions it yields a logarithmic neighbour count; the untruncated case retains an explicit assumption not verified by the compact-support argument.

C.1 Population regularity and fitted-cell geometry

  • Under compact ball support and positive lower density, fitted centres and cells have regularity margins that localize empirical minimizers near population optima.A uniform risk discrepancy below the population risk gap places every empirical minimizer in that neighbourhood.Source: §C.1 · p. 29

C.2 Uniform sampling within fitted cells

  • A uniform sampling bound ensures every relevant fitted-cell region of probability at least ηr contains an observation, despite the fitted centres being selected from the same sample.The proof controls a parameterized family of cell-ball intersections using its finite-set membership-pattern growth and a double-sampling η-net bound.Source: §C.1 · p. 29, §C.2 · pp. 29–30

C.3 Uniform neighbour counts

  • Binomial Bernstein concentration and a union bound control the maximum radius-neighbour count MX(r) without assuming the counts are independent.The conditional exceedance probability is at most e^-u, and the density upper bound controls each count's mean.Source: §C.3 · p. 31

C.4 Exact empirical coverage

  • When the risk, sampling, and neighbour-count events hold, the fitted partition is connected within a sufficiently large q-neighbour scaffold and attains the unrestricted empirical SSE optimum.The constructed K-block partition has the same SSE as the unrestricted optimum.Source: §C.4 · p. 31

C.5 Compact support and the Gaussian-mixture specialization

  • For fixed dimension and K, compact-support density bounds yield qn = O(log n) and an O(log n/n) fraction of complete-graph edges, with coverage probability tending to one.The result also applies to truncated Gaussian mixtures with positive unequal weights and positive-definite covariances; for untruncated mixtures, optimal-centre conditions remain explicit assumptions.Source: §C.5 · pp. 32–33

D.1 Proof of Proposition 3

The split-merge construction pairs each eligible path with a reverse path to establish detailed balance and invariance. The unknown-K comparisons use exact recurrences matched to penalized SSE or collapsed-MAP objectives, whose optimized scores need not track generating-label agreement.

D.1 Proof of Proposition 3

  • Reversal is an involutive bijection between split and merge traces, and positive reverse support follows for eligible moves on the target-positive state space.Summing paired-path balance over the reversal bijection proves off-diagonal detailed balance; the diagonal identity then gives reversibility and invariance.Source: §D.1 · pp. 33–34
  • The guided split-merge kernel preserves the joint target when composed with target-preserving allocation and auxiliary-variable kernels; irreducibility and aperiodicity require separate checks.The NGGP update is verified separately in Appendix G.2.Source: §D.1 · p. 34

E.1 Objective-matched selection of the number of clusters

  • Unknown-K comparisons match each comparator to its own objective: DP-means to penalized SSE and MAP-DP to the collapsed NIW likelihood with a CRP prior.The complete recurrence exactly minimizes the penalized SSE objective; three-restart MAP-DP coordinate ascent is compared with exact recurrences for the same collapsed posterior score.Source: §E.1 · p. 34, Table 3 · p. 35
  • Delaunay matched the complete recurrence on all 120 data sets for both objectives, while improved optimization of collapsed posterior score did not necessarily improve VI to generating labels.Table 3 reports gaps only against the oracle for the corresponding objective; VI is not part of either optimized objective.Source: §E.1 · p. 34, Table 3 · p. 35

E.2 Component-factorization ablation

The experiments test whether scaffold-constrained exact evaluation preserves objective optima, how scaffold choice affects label recovery, and what computational work the methods require. They also assess component factorization and use scaffold information in mixture-posterior split-merge proposals.

E.2 Component-factorization ablation

  • All 32 paired factorization evaluations agree with basic subset-DP in objective value and feasible partition count, but factorization does not uniformly reduce stored values.Eight evaluations retain more state-count pairs, including all four 5-NN-MST cases; the reported counts are not total-memory or runtime speedups.Source: §E.2 · pp. 35–36

E.3 Structural controls and candidate connectivity

  • In the chain control, a radius-1.35 graph recovers stipulated labels but excludes every unrestricted SSE optimum; in the offset-column control, 3-NN-MST and Delaunay recover both optimum and labels in every sample.These controls distinguish criterion mismatch from local-search failure.Source: §E.3 · p. 36, Figure 4 · p. 36
  • At n = 60, candidate coverage usually rises with separation but is not monotonic, and checking a fitted candidate partition does not certify coverage of an unknown unrestricted optimum.Changing component centres also changes the fitted Voronoi allocation and which boundary observations must be joined.Source: §E.3 · p. 36, Figure 5 · p. 37

E.4 Two-moons construction and noise sensitivity

  • For two-moons data with n = 60 and K = 2, Table 5 reports means over five paired realizations at each noise level; the pruned-MST fit is identical to single linkage and shown once.Source: Table 5 · p. 38

E.5 UCI computation and supporting comparisons

  • Across 100 exact samples, MST, union 2-NN, and union 5-NN cover 75, 94, and 100 unrestricted optima, respectively.The exact-coverage study uses stratified n = 15 samples and a complete-recurrence oracle; these results are not pooled with the full-data comparisons.Source: §E.5 · p. 40, Table 8 · p. 40

E.6 Posterior protocol and validation

  • For this single simulated case, all 15 target-sampler combinations pass evaluation thresholds—max bR ≤1.05 and minimum bulk ESS at least 100—at each of three checkpoints; Table 9 reports the final checkpoint.No uncertainty intervals across data sets are reported.Source: §E.6 · p. 42

F.1 Component-factorized evaluation of remaining-set problems

  • Component factorization evaluates disconnected remaining sets by combining component solutions; its complete-graph worst case is unchanged because no nontrivial split occurs.The decomposition is cached by remaining set, while component subproblem solutions remain indexed by (S, k); hybrid work should be reported separately from basic recurrence transition counts.Source: §F.1 · pp. 43–44

F.2 Dictionary-free evaluation, block generation, and caching

The dictionary-free evaluator generates feasible scaffold-connected blocks as needed, applies a remaining-set recurrence, and memoizes selected subproblems. Its feasibility rules make block generation exhaustive, while bounded storage and on-demand work do not remove the possibility of exponential cost.

F.2 Dictionary-free evaluation, block generation, and caching

  • A candidate first block must contain the least-indexed observation, be connected, and leave a complement with between k − 1 components and k − 1 vertices.These conditions are necessary and sufficient for the complement to admit k − 1 connected nonempty blocks.Source: §F.2 · p. 44
  • The evaluator computes the minimum SSE for exactly k scaffold-connected blocks, returning a minimizing partition when feasible and +∞ otherwise.Its initial call yields OPT(H, K) if the search completes.Source: §F.2 · p. 45
  • The block generator branches on including or excluding frontier vertices and prunes infeasible choices using remaining size, connectivity, and component counts.Every feasible block follows one unique branch sequence, so the depth-first generator is exhaustive and duplicate-free without storing prior outputs.Source: §F.2 · pp. 45–46
  • Completed solutions are memoized only for connected (S, k) with 1 < k < |S|; disconnected sets are solved by component convolution, while boundary cases are direct.Auxiliary caches reuse component decompositions and block SSE values; eviction causes recomputation rather than changing results.Source: §F.2 · p. 47
  • On-demand generation and selective storage preserve recurrence values and feasible-partition counts, but neither removes the possibility of exponential computation or memory use.When a state, search-node, or time limit is reached, the search is reported as incomplete, with no fitted partition or exactness claim.Source: §F.2 · p. 47

G.1 Collapsed targets and proposal specification

The appendix specifies collapsed mixture targets and scaffold-guided proposals, then develops recurrence and geometric results supporting exact clustering and coverage claims.

G.1 Collapsed targets and proposal specification

  • The appendix defines EPPFs by block-size probabilities and gives finite-mixture, DP, and NGGP prior factors alongside the collapsed Gaussian likelihood setup.The finite-mixture expression integrates symmetric Dirichlet weights and sums over injective assignments of occupied blocks to component labels.Source: §G.1 · pp. 47–48
  • Scaffold split-merge proposals select eligible seed pairs by partition membership, orient them by index, and order remaining observations by scaffold distance for reversible allocation.Splits are disabled at the finite-mixture component limit; when neither move is available, the proposal is the identity kernel.Source: §G.1 · p. 49

G.2 NGGP auxiliary-variable update

  • The NGGP auxiliary update uses a strictly concave log-coordinate slice target and stepping-out and shrinkage sampling to preserve the required conditional distribution.A numerical evaluation limit raises an error rather than returning an approximate update; composition preserves the joint target when each constituent kernel does.Source: §G.2 · pp. 49–50

H.1 One-dimensional segmentation

  • In one dimension, sorted observations admit an unrestricted SSE optimum with contiguous blocks, and the segmentation recurrence evaluates O(nK) prefix states.The path has n(n + 1)/2 connected blocks, distinct from the number of stored dynamic-programming values.Source: §H.1 · p. 50

H.2 SSE identities

  • The SSE identities show that block means minimize assigned SSE and that the disjoint-block decomposition yields the cached subset weight; its merge term is Ward cost.These identities require no hierarchical merge path.Source: §H.2 · p. 50

H.3 Voronoi cells and Delaunay adjacency

  • Nearest-centre assignment and recentering are nonincreasing SSE steps when all K cells remain nonempty, while planar Delaunay adjacency is dual to shared Voronoi edges.The Delaunay graph has O(n) edges, but this sparsity alone does not bound its connected-subset count.Source: §H.3 · p. 51

I.1 Planar proximity graphs and Delaunay coverage

  • For planar data in general position, the Delaunay graph realizes at least one global two-cluster SSE minimizer, so its constrained and unrestricted optima agree.The supporting argument uses connectivity of triangulation vertices inside half-planes.Source: §I.1 · p. 51

I.1.1 Half-plane connectivity in a triangulation

  • Every nonempty half-plane intersection of a triangulation’s vertices induces a connected subgraph, enabling the Delaunay coverage argument for optimal two-cluster cells.The proof connects vertices by following a path through adjacent triangles and choosing vertices from each crossed edge that lie in the half-plane.Source: §I.1.1 · pp. 51–52

I.1.2 Proof of Theorem 3

The proof constructs nonempty nearest-centroid cells from an unrestricted two-cluster optimum and uses planar half-plane connectivity to establish Delaunay realizability; it also distinguishes empirical coverage from latent-component recovery.

I.1.2 Proof of Theorem 3

  • The proof ensures both reassigned cells are nonempty by comparing the unrestricted two-block optimum with a singleton-versus-rest competitor and then applying nearest-centroid assignment and recentering.General position supplies an observation distinct from the overall mean, making the competitor strictly better than the one-block partition.Source: §I.1.2 · p. 52
  • The proof concludes that the Delaunay graph contains a two-cluster partition attaining the unrestricted optimum, by applying half-plane connectivity to the reassigned cells.The cells are intersections of the observations with complementary open and closed half-planes.Source: §I.1.2 · p. 53

J Scaffold gaps and population risk

  • Exact optimization removes the search term and coverage removes the scaffold’s empirical approximation term, but SSE-optimal groups are not thereby identified with latent mixture components.Source: J Scaffold gaps and population risk · p. 53
Loading 2609.30477v1…