0
$\begingroup$

I'm trying to refresh my memory on diffusion kernels, and am reading this paper. I don't understand the derivation of equation 11 on page 3.

EDIT: I don't understand how the two equations:

  1. $Z_i(t+1)=Z_i(t)+\alpha\sum_j \left[Z_j(t)-Z_i(t)\right]$
  2. $Z(t)=\left(1+\alpha H\right)^tZ(0)$

are equivalent. I actually thought I had proven them unequal (false proof included below for posterity) but Didier pointed out I made a mistake and I'm really interested in the more general question anyway.


They define $Z_i(t+1)=Z_i(t)+\alpha\sum_j \left[Z_j(t)-Z_i(t)\right]$. One property graph-invariant property of this is that if all $Z_k$ are equal, $Z_k(t+1)=Z_k(t)$.

Now it claims $Z(t)=\left(1+\alpha H\right)^tZ(0)$. I don't see how this maintains my observation, i.e. for some matrices $H$ it seems that $Z_i(t+1)\not=Z_i(t)$ even if all $Z_i(0)$ are equal.

I tried this out with a simple (directed) graph: $V=\{a,b,c\}$, $E=\left\{(a,b),(a,c),(c,b)\right\}$. From their definition, I think

$ H=\left( \begin{array}{ccc} -2 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & -1 \end{array} \right) $

Setting $Z(0)=(\begin{array}{ccc}1 & 1 & 1\end{array})^T$ I get that $Z(1)=(\begin{array}{ccc}3 & 0 & 2\end{array})^T$ using the definition of Z involving H, but $(\begin{array}{ccc}1 & 1 & 1\end{array})^T$ with the summation version.

Can anyone help me figure out what's going on?

  • 0
    @DidierPiau: If you think "Basic linear algebra question" or whatever will attract a better audience, please do edit the title.2012-01-29

1 Answers 1

1

Hint: Start by showing that equation 1. is the same as $Z(t+1)=(1+\alpha H) Z(t)$.

From the definition of the matrix $H$, we find that the $i$th coordinate of the vector $(1+\alpha H) Z(t)$ is $\begin{eqnarray*}Z_i(t)+\alpha\sum_j H_{ji} Z_j(t)&=&Z_i(t)+\alpha\sum_{j\sim i} Z_j(t)-\alpha d_i Z_i(t)\\ &=&Z_i(t)+\alpha\sum_{j\sim i} [Z_j(t)- Z_i(t)]. \end{eqnarray*}$

  • 0
    Haha wow... all that because I didn't understand the notation. Live and learn.2012-02-01