Lemma 3 (iv) —
ProvedEffResSparsify.Sampling.lemma_3_iveffective-resistancep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projectionspectral-graph-theory
Let be a connected weighted graph with positive edge weights and . For every edge , the diagonal entry of at equals the squared Euclidean norm of the -th column of :
Since , this bounds the length of the column sampled by Sparsify, which is the norm bound fed into the matrix concentration inequality (Lemma 5).
Preamble
import Mathlib import Definitions.Def_EffResSparsify_Sampling_Defs
Formal statement
namespace EffResSparsify.Sampling
open Matrix
/-- Lemma 3 (iv), p. 6: `Π(e,e) = ‖Π(·,e)‖²`, the squared Euclidean norm of the `e`-th column. -/
theorem lemma_3_iv {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : WGraph V E) (hG : G.IsConnected) (e : E) :
G.projPi e e = ∑ e' : E, (G.projPi e' e) ^ 2 := by sorry
end EffResSparsify.Sampling
Source
Spielman, Srivastava, Graph Sparsification by Effective Resistances, arXiv:0803.0929v4, p. 6, Lemma 3 (iv)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.