Documentation

Averaging.OpportunisticOneStep

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):

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 β'.

noncomputable def Averaging.Opportunistic.cutCoef {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (x : V → ℝ) :

The coefficient β = ⟨x, χ⟩/n of x along the cut vector: y = Q₂ x = β χ.

Equations
Instances For
    noncomputable def Averaging.Opportunistic.restSq {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (x : V → ℝ) :

    ‖z‖² = ‖Q_{3⋯n} x‖².

    Equations
    Instances For
      theorem Averaging.Opportunistic.restSq_nonneg {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (x : V → ℝ) :
      0 ≤ restSq V₁ x
      theorem Averaging.Opportunistic.projCut_eq {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (x : V → ℝ) (v : V) :
      projCut V₁ x v = cutCoef V₁ x * cutVec V₁ v
      theorem Averaging.Opportunistic.eq_decomp {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (x : V → ℝ) (v : V) :
      x v = Dynamics.avg x + cutCoef V₁ x * cutVec V₁ v + projRest V₁ x v
      theorem Averaging.Opportunistic.cutWeight_eq {V : Type u_1} [DecidableEq V] {V₁ : Finset V} (u v : V) :
      ((cutVec V₁ u - cutVec V₁ v) / 2) ^ 2 = if v ∈ V₁ ↔ u ∉ V₁ then 1 else 0

      The weight ((χ_u - χ_v)/2)² of a pair: 1 across the cut, 0 inside a community.

      theorem Averaging.Opportunistic.IsClusteredRegular.d_real_pos {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) :
      0 < ↑d
      theorem Averaging.Opportunistic.IsClusteredRegular.sum_sq_projCut {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (x : V → ℝ) :
      ∑ v : V, projCut V₁ x v ^ 2 = ↑(Fintype.card V) * cutCoef V₁ x ^ 2
      theorem Averaging.Opportunistic.IsClusteredRegular.sum_sq_eq {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) :
      ∑ v : V, x v ^ 2 = ↑(Fintype.card V) * Dynamics.avg x ^ 2 + ↑(Fintype.card V) * cutCoef V₁ x ^ 2 + restSq V₁ x

      Pythagoras for the decomposition x = x_∥ + y + z.

      theorem Averaging.Opportunistic.IsClusteredRegular.cutCoef_sq_add_restSq_edgeAvg_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) (e : G.Dart) :
      ↑(Fintype.card V) * cutCoef V₁ (edgeAvg G x e) ^ 2 + restSq V₁ (edgeAvg G x e) ≤ ↑(Fintype.card V) * cutCoef V₁ x ^ 2 + restSq V₁ x

      n β² + ‖z‖² (the squared distance to the consensus) never increases.

      theorem Averaging.Opportunistic.IsClusteredRegular.card_mul_cutCoef_edgeAvg_sub {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) (e : G.Dart) :
      ↑(Fintype.card V) * (cutCoef V₁ (edgeAvg G x e) - cutCoef V₁ x) = (cutVec V₁ e.toProd.1 - cutVec V₁ e.toProd.2) * (x e.toProd.2 - x e.toProd.1) / 2

      The change of n β in one round: (χ_a - χ_b)(x_b - x_a)/2 on the dart (a, b).

      theorem Averaging.Opportunistic.IsClusteredRegular.avg_cutCoef_edgeAvg {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) :
      (Dynamics.avg fun (e : G.Dart) => cutCoef V₁ (edgeAvg G x e)) = (1 - 2 * ↑b / ↑d / ↑(Fintype.card V)) * cutCoef V₁ x

      E β' = (1 - λ₂/n) β.

      theorem Averaging.Opportunistic.IsClusteredRegular.sum_dart_cutWeight_fst {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (f : V → ℝ) :
      ∑ e : G.Dart, ((cutVec V₁ e.toProd.1 - cutVec V₁ e.toProd.2) / 2) ^ 2 * f e.toProd.1 = ↑b * ∑ v : V, f v

      Number of cut darts leaving each node: ∑_{(a,b)} w(a, b) f(a) = b ∑ f.

      theorem Averaging.Opportunistic.IsClusteredRegular.sum_dart_symm {V : Type u_1} [Fintype V] {G : SimpleGraph V} [DecidableRel G.Adj] (F : G.Dart → ℝ) :
      ∑ e : G.Dart, F e.symm = ∑ e : G.Dart, F e
      theorem Averaging.Opportunistic.IsClusteredRegular.sum_dart_cutWeight_snd {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (f : V → ℝ) :
      ∑ e : G.Dart, ((cutVec V₁ e.toProd.1 - cutVec V₁ e.toProd.2) / 2) ^ 2 * f e.toProd.2 = ↑b * ∑ v : V, f v
      theorem Averaging.Opportunistic.IsClusteredRegular.sum_dart_cutWeight_sq_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) :
      ∑ e : G.Dart, ((cutVec V₁ e.toProd.1 - cutVec V₁ e.toProd.2) / 2) ^ 2 * (x e.toProd.1 - x e.toProd.2) ^ 2 ≤ 8 * ↑(Fintype.card V) * ↑b * cutCoef V₁ x ^ 2 + 8 * ↑b * restSq V₁ x

      The cut darts against the decomposition: ∑ w (x_a - x_b)² ≤ 8 n b β² + 8 b ‖z‖².

      theorem Averaging.Opportunistic.IsClusteredRegular.avg_cutCoef_edgeAvg_sub_sq_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) :
      (↑(Fintype.card V) * Dynamics.avg fun (e : G.Dart) => (cutCoef V₁ (edgeAvg G x e) - cutCoef V₁ x) ^ 2) ≤ 4 * (2 * ↑b / ↑d) / ↑(Fintype.card V) ^ 2 * (↑(Fintype.card V) * cutCoef V₁ x ^ 2 + restSq V₁ x)

      Variance of β': n E (β' - β)² ≤ (4λ₂/n²)(n β² + ‖z‖²).

      The Laplacian form splits along the decomposition: xᵀ L x = 2 b n β² + zᵀ L z.

      theorem Averaging.Opportunistic.IsClusteredRegular.avg_restSq_edgeAvg_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (x : V → ℝ) :
      (Dynamics.avg fun (e : G.Dart) => restSq V₁ (edgeAvg G x e)) ≤ (1 - lam3 / ↑(Fintype.card V)) * restSq V₁ x + 2 * ↑b / ↑d * cutCoef V₁ x ^ 2

      Lemma C.3: E ‖z'‖² ≤ (1 - λ₃/n) ‖z‖² + λ₂ β².

      theorem Averaging.Opportunistic.IsClusteredRegular.avg_cutDev_edgeAvg_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x : V → ℝ) (γ : ℝ) :
      (Dynamics.avg fun (e : G.Dart) => ↑(Fintype.card V) * (cutCoef V₁ (edgeAvg G x e) - γ) ^ 2) ≤ (1 - 2 * ↑b / ↑d / ↑(Fintype.card V)) * (↑(Fintype.card V) * (cutCoef V₁ x - γ) ^ 2) + 2 * ↑b / ↑d * γ ^ 2 + 4 * (2 * ↑b / ↑d) / ↑(Fintype.card V) ^ 2 * (↑(Fintype.card V) * cutCoef V₁ x ^ 2 + restSq V₁ x)

      Lemma C.2 (in the form used here): for every reference coefficient γ, E n (β' - γ)² ≤ (1 - λ₂/n) n (β - γ)² + λ₂ γ² + (4λ₂/n²)(n β² + ‖z‖²).