Proof of Theorem 4.8, p. 23, with Β§3 p. 12 β the algorithm outputs one cluster per point of Dβπ‘ with prominence β₯ Ο and birth β₯ Ο
ProvedPersistClust.Count.proof_thm_4_8_algorithm_outputLet , let be a symmetric matrix with non-negative entries, let and , and let be any permutation sorting in non-decreasing order. Then the number of clusters output by the clustering algorithm (Procedures 1β2) with processing order equals the number of points of the -th persistence diagram of the upper-star Rips filtration, counted with multiplicity, such that
the essential points included.
This is the step "the algorithm discards and keeps only " of the main theorem: the union-find procedure with the prominence test and the output filter selects exactly the points of the diagram above both thresholds, whatever the tie-breaking of the sort.
Formalization Note The hypothesis is added: with the algorithm may keep equal-valued adjacent peaks whose diagram point has zero persistence and is not counted. The main theorem has . The paper asserts this step without proof.
import Mathlib import Definitions.Def_PersistClust_Count_Diagram import Definitions.Def_PersistClust_Count_Rips import Definitions.Def_PersistClust_Count_Algorithm
namespace PersistClust.Count
theorem proof_thm_4_8_algorithm_output
(n : β) (g : Fin n β β) (Dm : Fin n β Fin n β β)
(hDm : β i j, Dm i j = Dm j i) (hDm0 : β i j, 0 β€ Dm i j)
(Ξ΄ Ο : β) (hΞ΄ : 0 β€ Ξ΄) (hΟ : 0 < Ο)
(Ο : Fin n β Fin n) (hΟ : IsSortOrder g Ο) :
(numClusters g Dm Ξ΄ Ο Ο : ββ)
= {q : (EReal Γ EReal) Γ β | (q.2 : ββ) < ripsDiagram Dm g Ξ΄ q.1 β§
q.1.2 β€ q.1.1 - (Ο : EReal) β§ (Ο : EReal) β€ q.1.1}.encard := by sorry
end PersistClust.Count
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.