Proof of Lemma 22.3: for symmetric W, vᵀLv = ½ ∑_{r,s} W_{r,s}(v_r − v_s)² for the unnormalized graph Laplacian L = D − W
ProvedUnderstandingML.laplacian_quadratic_formgraph-laplacianquadratic-formspectral-clustering
From the proof of Lemma 22.3. For any vector ,
Formally: for a symmetric , and every .
Preamble
import Definitions.Def_UnderstandingML_Clustering open MeasureTheory
Formal statement
namespace UnderstandingML
/-- **The Laplacian quadratic form** (proof of Lemma 22.3, p. 316): for a symmetric similarity
matrix `W` and every vector `v`, `vᵀ L v = ½ ∑_{r,s} W_{r,s} (v_r − v_s)²`. -/
theorem laplacian_quadratic_form {m : ℕ} (W : Matrix (Fin m) (Fin m) ℝ) (hW : W.IsSymm)
(v : Fin m → ℝ) :
dotProduct v ((laplacian W).mulVec v) = 1 / 2 * ∑ r, ∑ s, W r s * (v r - v s) ^ 2 := 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, the identity in the proof of Lemma 22.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.