Binary coarse nets, shifted signatures, and deterministic sweep rows
DefinitionStableMSR_Recovery_Supplement_CoarseScanalgorithmsclustering
Explicit operations compute separated centers, component representatives, and the equality classes of closed-ball signatures. Intermediate loops are bounded by the input lists.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_CoarseSweep
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
open BinaryVerifier
def scanDist (a : Input) (i j : ℕ) : ℚ := distAt a.1 a.2.2 i j
def nearScan (a : Input) (L : ℚ) (i : ℕ) : Block :=
(points a).filter fun j => decide (scanDist a j i ≤ L/16)
def admitCenter (e : ℕ × Block) (xs : Block) : Block :=
if e.2.any (fun z => xs.contains z) then xs else e.1 :: xs
def coarseScan (a : Input) (L : ℚ) (us : Block) : Block :=
(us.map (fun i => (i,nearScan a L i))).foldr admitCenter []
def scanClass (a : Input) (labels : List ℕ) (i : ℕ) : Block :=
(points a).filter fun j => decide (numAt labels i = numAt labels j)
def fits (a : Input) (s : ℚ) (w : Block) : Bool :=
w.all fun i => w.all fun j => decide (scanDist a i j ≤ s)
def shifted (a : Input) (b : ℚ) (labels : List ℕ) (i : ℕ) : ℕ :=
let w := scanClass a labels i
if fits a (2*b) w then w.head?.getD 0 else i
def scanKey (a : Input) (L b r : ℚ) (big fine : List ℕ) (i : ℕ) : Block :=
let w := scanClass a big i
numAt big i :: (if fits a L w then [] else
(coarseScan a L w).filter fun z => decide (scanDist a z (shifted a b fine i) ≤ r))
def vecEqual (v w : Block) : Bool :=
decide (v.length=w.length) && (List.range v.length).all fun i => decide (numAt v i=numAt w i)
def scanOwner (keys : List Block) (i : ℕ) : ℕ :=
keys.findIdx (fun u => vecEqual u (keys[i]?.getD []))
def scanCell (a : Input) (keys : List Block) (j : ℕ) : Block :=
(points a).filter fun i => decide (scanOwner keys i=j)
def keyFibers (a : Input) (keys : List Block) : Pack :=
((List.range keys.length).filter (fun j => !(scanCell a keys j).isEmpty)).map (scanCell a keys)
def coarseProgram (γ : ℚ) (z : SweepInput) : Pack :=
let a := z.1
let R := z.2.1
let L := z.2.2.1
let b := (γ-1)*R/4
let r := 3*L/32+(z.2.2.2:ℚ)*(L/(32*a.1))
let big := componentLabels a R
let fine := componentLabels a (2*b)
keyFibers a ((points a).map (scanKey a L b r big fine))
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Source
Refinement of the wide-component construction in S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix A.2–A.3, Lemma A.1. The coarse net and uniformly spaced deterministic radius argument are an alternative with a larger parameter-dependent split bound. https://arxiv.org/abs/2611.03547