Documentation

Averaging.OpportunisticFirstMoment

Averaging whenever you meet: the expected matrix and the first moment #

One round of the averaging process is x⁽ᵗ⁾ = W_t x⁽ᵗ⁻¹⁾ with the random matrix W_t of equation (1) of arXiv:1703.05045 (v3). Its expectation over a uniformly random edge is W̄ = I - L / (2m) (equation (2), Observation A.2), L = D - A the Laplacian and m the number of edges, a symmetric doubly stochastic matrix. Since the rounds are independent, the expected state evolves linearly: E[x⁽ᵗ⁾ | x⁽⁰⁾ = x] = W̄ᵗ x (equation (15)). Since W_t is symmetric and idempotent, the expected squared norm after one round is the quadratic form of W̄ (the identity behind Lemma C.1).

These are the matrices of the random sequential model of Averaging.Sequential (AVG-1): stepMatrix G d is Sequential.edgeMatrix d.fst d.snd, meanStepMatrix G is Sequential.meanMatrix G, and the averaging process avgRun is Sequential.seqRun (avgRun_eq_seqRun), so the statements below are those of AVG-1.

@[reducible, inline]
noncomputable abbrev Averaging.Opportunistic.stepMatrix {V : Type u_1} [DecidableEq V] (G : SimpleGraph V) (d : G.Dart) :

The random matrix W_t of one round on the active edge {d.fst, d.snd} (equation (1)): 1/2 on the diagonal at the two endpoints and at the two entries of the active edge, 1 on the rest of the diagonal, 0 elsewhere. It is I - (e_u - e_v)(e_u - e_v)ᵀ / 2, the step matrix Sequential.edgeMatrix of AVG-1.

Equations
Instances For
    @[reducible, inline]
    noncomputable abbrev Averaging.Opportunistic.meanStepMatrix {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :

    The expected matrix W̄ = I - L / (2m) of one round (equation (2)), where L = D - A is the Laplacian of G and m its number of edges: Sequential.meanMatrix of AVG-1.

    Equations
    Instances For

      One round as a matrix step #

      One round of averaging is the multiplication by AVG-1's step matrix W_t.

      theorem Averaging.Opportunistic.avgRun_eq_seqRun {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (x : V → ℝ) (l : List G.Dart) :

      The averaging process is AVG-1's sequential averaging x⁽ᵗ⁾ = W(t) ⋯ W(1) x⁽⁰⁾.

      theorem Averaging.Opportunistic.sum_sq_edgeAvg {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (x : V → ℝ) (d : G.Dart) :
      ∑ v : V, edgeAvg G x d v ^ 2 = ∑ v : V, x v ^ 2 - (x d.toProd.1 - x d.toProd.2) ^ 2 / 2
      theorem Averaging.Opportunistic.sum_dart_sq {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x : V → ℝ) :
      ∑ d : G.Dart, (x d.toProd.1 - x d.toProd.2) ^ 2 = 2 * x ⬝ᵥ (SimpleGraph.lapMatrix ℝ G).mulVec x

      Main statements #

      theorem Averaging.Opportunistic.stepMatrix_mulVec {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (d : G.Dart) (x : V → ℝ) :
      (stepMatrix G d).mulVec x = edgeAvg G x d

      W_t x is one round of averaging on the active edge.

      W_t is symmetric (proof of Lemma C.1).

      W_t is idempotent (proof of Lemma C.1).

      theorem Averaging.Opportunistic.avg_stepMatrix {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (i j : V) :
      (Dynamics.avg fun (d : G.Dart) => stepMatrix G d i j) = meanStepMatrix G i j

      Observation A.2, equation (2): over a uniformly random edge, E[W_t] = I - L / (2m).

      W̄ is symmetric (Section 3).

      theorem Averaging.Opportunistic.avg_edgeAvg {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (x : V → ℝ) (v : V) :
      (Dynamics.avg fun (d : G.Dart) => edgeAvg G x d v) = (meanStepMatrix G).mulVec x v

      Equation (2) applied to a state: the expected state after one round is W̄ x.

      theorem Averaging.Opportunistic.expList_avgRun {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (x : V → ℝ) (t : ℕ) (v : V) :
      (Dynamics.expList G.Dart t fun (l : List G.Dart) => avgRun G x l v) = (meanStepMatrix G ^ t).mulVec x v

      First-moment evolution, equation (15): E[x⁽ᵗ⁾ | x⁽⁰⁾ = x] = W̄ᵗ x over t i.i.d. uniform rounds.

      theorem Averaging.Opportunistic.avg_sum_sq_edgeAvg {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (x : V → ℝ) :
      (Dynamics.avg fun (d : G.Dart) => ∑ v : V, edgeAvg G x d v ^ 2) = x ⬝ᵥ (meanStepMatrix G).mulVec x

      Second moment of one round (proof of Lemma C.1): E‖W x‖² = xᵀ W̄ x, since W is symmetric and idempotent.