Transition matrix - swapped dimensions?

[mfalkiewicz]

Hi @satra,
in the current implementation, Markov matrix is calculated by taking sums along axis 1:

d_alpha = np.power(np.array(L_alpha.sum(axis=1)).flatten(), -1)

And multiplying each row by the respective inverse sum:
L_alpha = d_alpha[:, np.newaxis] * L_alpha

In this scenario, ROWS sum to 1.

However, as far as I understand the wiki: https://en.wikipedia.org/wiki/Markov_kernel, the normalization should happen along axis 0. Thus, the code should be:

d_alpha = np.power(np.array(L_alpha.sum(axis=0)).flatten(), -1) L_alpha = d_alpha[np.newaxis,:] * L_alpha

Here the COLUMNS sum to 1.

Is that correct?

[satra]

d_alpha will be exactly the same. since L_alpha is symmetric by requirement of the function.

and if alpha > 0 the normalization is also symmetric. so the implementation is correct as far as i can tell.

[mfalkiewicz]

The affinity matrix is symmetric, but the transition matrix is not.

import numpy as np
X = np.random.random((10,10))
X = (X * X.T)/2
d_alpha_row = np.power(np.array(X.sum(axis=1)).flatten(), -1)
np.allclose(np.sum(L_alpha_row, axis = 1),1)

True

np.allclose(np.sum(L_alpha_row, axis = 0),1)

False

(L_alpha_row == L_alpha_row.T).all()

False

The same thing happens if we do the same thing along the columns. The Markov matrix is not symmetrical. However, I checked other implementations — for example Maggioni's code provides an option to either normalize along rows (Markov), but also along both rows and columns (bimarkov). There are some other implementations that normalize along the columns ( Altenating diffusion ). I am not sure what is the practical difference between them.

[satra]

@mfalkiewicz - ok, i was looking at the wrong place. i think you are talking about step 3 in the code:

https://github.com/satra/mapalign/blob/master/mapalign/embed.py#L98

if you see the wikipedia page: https://en.wikipedia.org/wiki/Diffusion_map

D_alpha is column sums (sums over j) - see the section on the diffusion process.

and then in step 3,

the inverse of that diagonal matrix is applied to L_alpha