Lemma A.4: few large clusters or an enumerated dyadic scale
ProvedStableMSR.Recovery.clustering_scale_selectionclusteringperturbation-stabilitysum-of-radii
Let a finite metric space of points be partitioned into nonempty clusters, and let . Write for the largest cluster radius, , for the clusters of radius at least , , and . With and , one of the following holds:
- and .
- There is an integer with such that, for ,
This is the deterministic scale-selection portion of Lemma A.4. It identifies either the bounded enumeration branch or a scale in Algorithm 1's finite list. The probabilistic partition guarantee is a separate obligation. The numerical argument needs feasibility and metricity, but no optimality or stability assumption.
Preamble
import Definitions.Def_StableMSR_Recovery_Geometry import Definitions.Def_StableMSR_Recovery_Parameters set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery
theorem clustering_scale_selection {n k : ℕ} (d : Point n → Point n → ℝ)
(hd : IsMetricArray d) (O : Partition n) (hO : Feasible Finset.univ k O)
(hkn : k < n) (ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1) :
(densityScale d O ε < sigma * largestRadius d O ∧
(largeClusters d O ε).card ≤ fewBound ε) ∨
(∃ j : ℕ, 9 ≤ j ∧ j ≤ ⌈Real.logb 2 (n : ℝ)⌉₊ ∧
sigma * largestRadius d O ≤ (2 : ℝ) ^ j * largestRadius d O ∧
(2 : ℝ) ^ j * largestRadius d O ≤ densityScale d O ε ∧
densityScale d O ε < 2 * ((2 : ℝ) ^ j * largestRadius d O) ∧
largeMass d O ε / ((2 : ℝ) ^ j * largestRadius d O) < 8 / ε) := by sorry
end StableMSR.Recovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, https://arxiv.org/html/2611.03547v1, Lemma A.4, first two assertions and their proof; Table 2 for the exact constants.