0 .

By combining Eqs. (\[vdec\]) and (\[asquareform\]), we obtain $$\begin{aligned}
V(x) - V(Ax) & =&  (x - \bar{x} {\bf 1})^T
\Big(\sum_{i<j} w_{ij} (e_i - e_j) (e_i - e_j)^T\Big) (x-\bar{x}{\bf 1}) \nonumber \\
& = &  \sum_{i<j} w_{ij} (x_i - x_j)^2. $$

Note that the entries $w_{ij}(k)$ of $A(k)^T A(k)$ are nonnegative, because the weight matrix $A(k)$ has nonnegative entries. In view of this, Lemma \[vl\] implies that $$V(x(k+1))\le V(x(k))\qquad \hbox{for all }k.$$ Moreover, the amount of variance decrease is given by $$V(x(k)) - V(x(k+1)) = \sum_{i<j} w_{ij}(k) (x_i(k) - x_j(k))^2.$$ We will use this result to provide a lower bound on the amount of decrease of the sample variance $V(x(k))$ in between iterations.

Since every positive entry of $A(k)$ is at least $\eta$, it follows that every positive entry of $A(k)^T A(k)$ is at least $\eta^2$. Therefore, it is immediate that $$\hbox{if }\quad w_{ij}(k) > 0, \quad\hbox{then }\quad w_{ij}{(k)} \geq \eta^2.$$ In our next lemma, we establish a stronger lower bound. In particular, we find it useful to focus not on an individual $w_{ij}$, but rather on all $w_{ij}$ associated with edges $(i,j)$ [that]{} cross [a particular]{} cut in the graph $(N,\E(A^TA))$. For such groups of $w_{ij}$, we prove 