Lemma 22.3: for H_{i,j} = |C_j|^{ā1/2} š[i ā C_j], the columns of H are orthonormal and RatioCut(Cā,ā¦,C_k) = trace(HįµLH)
ProvedUnderstandingML.ratiocut_tracegraph-laplacianratiocutspectral-clustering
Lemma 22.3. Let be a clustering and let be the matrix such that . Then, the columns of are orthonormal to each other and .
Formally: symmetric, a partition of into nonempty clusters; orthonormality as .
Preamble
import Definitions.Def_UnderstandingML_Clustering open MeasureTheory
Formal statement
namespace UnderstandingML
/-- **Lemma 22.3** (p. 316). Let `Cā, ā¦, C_k` be a clustering and let `H ā ā^{mĆk}` be the matrix
with `H_{i,j} = |Cā±¼|^{ā1/2} š[i ā Cā±¼]`. Then the columns of `H` are orthonormal to each other and
`RatioCut(Cā, ā¦, C_k) = trace(Hįµ L H)`. For a symmetric `W` and a partition of `[m]` into
nonempty clusters. -/
theorem ratiocut_trace {m k : ā} (W : Matrix (Fin m) (Fin m) ā) (hW : W.IsSymm)
(C : Fin k ā Finset (Fin m)) (hC : IsPartition Finset.univ C) (hne : ā i, (C i).Nonempty) :
(clusterIndicator C).transpose * clusterIndicator C = 1 ā§
ratioCut W C = Matrix.trace ((clusterIndicator C).transpose * laplacian W * clusterIndicator C) := by sorry
end UnderstandingML
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §22.3.2 p. 316, Lemma 22.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.