One round of averaging on a clustered regular graph (Lemmas C.1 to C.3) #
On an (n, d, b)-clustered regular graph write the state as x = x_∥ + y + z (equation (7)) with
y = β χ, β = ⟨x, χ⟩/n (cutCoef) and ‖z‖² = restSq. For one round of Averaging(1/2) on a
uniformly random dart (λ₂ = 2b/d, λ₃ ≥ lam3):
sum_sq_eq:‖x‖² = n α² + n β² + ‖z‖²(Pythagoras).cutCoef_sq_add_restSq_edgeAvg_le:n β² + ‖z‖²never increases.avg_cutCoef_edgeAvg:E β' = (1 - λ₂/n) β.avg_restSq_edgeAvg_le(Lemma C.3):E ‖z'‖² ≤ (1 - λ₃/n) ‖z‖² + λ₂ β².avg_cutDev_edgeAvg_le(Lemma C.2, in the form used here): for every referenceγ,E n (β' - γ)² ≤ (1 - λ₂/n) n (β - γ)² + λ₂ γ² + (4λ₂/n²)(n β² + ‖z‖²).
The proofs avoid the explicit eigen-decomposition: E‖W x‖² = xᵀ W̄ x (W is a symmetric
idempotent), Jensen for E β'², and a direct count over the cut darts for the variance of β'.
The coefficient β = ⟨x, χ⟩/n of x along the cut vector: y = Q₂ x = β χ.
Equations
- Averaging.Opportunistic.cutCoef V₁ x = Dynamics.avg fun (w : V) => Averaging.Opportunistic.cutVec V₁ w * x w
Instances For
‖z‖² = ‖Q_{3⋯n} x‖².
Equations
- Averaging.Opportunistic.restSq V₁ x = ∑ v : V, Averaging.Opportunistic.projRest V₁ x v ^ 2
Instances For
Pythagoras for the decomposition x = x_∥ + y + z.
n β² + ‖z‖² (the squared distance to the consensus) never increases.
The change of n β in one round: (χ_a - χ_b)(x_b - x_a)/2 on the dart (a, b).
E β' = (1 - λ₂/n) β.
Number of cut darts leaving each node: ∑_{(a,b)} w(a, b) f(a) = b ∑ f.
The cut darts against the decomposition: ∑ w (x_a - x_b)² ≤ 8 n b β² + 8 b ‖z‖².
Variance of β': n E (β' - β)² ≤ (4λ₂/n²)(n β² + ‖z‖²).
The Laplacian form splits along the decomposition: xᵀ L x = 2 b n β² + zᵀ L z.
Lemma C.3: E ‖z'‖² ≤ (1 - λ₃/n) ‖z‖² + λ₂ β².
Lemma C.2 (in the form used here): for every reference coefficient γ,
E n (β' - γ)² ≤ (1 - λ₂/n) n (β - γ)² + λ₂ γ² + (4λ₂/n²)(n β² + ‖z‖²).