2
$\begingroup$

I have a probability transition matrix $P$ that contains some values very close to zero. I want to sparsify this matrix by taking the k largest values for each row and setting the others to zero. For instance, taking $k=2$

$$ P = \left( \begin{array}{cccc} 0.9 & 0.0999 & 0.0001 \\ 0.199 & 0.8 & 0.001 \\ 0.199 & 0.001 & 0.8 \end{array} \right)$$

and

$$ P_{\text{sparse}} = \left( \begin{array}{cccc} 0.9 & 0.1 & 0.0 \\ 0.2 & 0.8 & 0.0 \\ 0.2 & 0.0 & 0.8 \end{array} \right) .$$

What is the best way to measure the distance between $P$ and $P_{\text{sparse}}$?

  • Euclidean distance between $P$ and $P_{\text{sparse}}$?
  • KL divergence between the underlying stationary state distribution?
  • ...

I've look already at other questions (for instance https://mathoverflow.net/questions/225749/calculate-the-kl-divergence-between-two-transition-matrices) and articles (https://ieeexplore.ieee.org/document/1291741), but could not find a clear answer until now.

$\endgroup$
3
  • $\begingroup$ How about absolute difference? $\endgroup$ Jul 23 '19 at 6:55
  • $\begingroup$ I thought of it also, but I don't know if it makes sense when comparing these stochastic matrices. $\endgroup$ Jul 23 '19 at 12:18
  • $\begingroup$ can you put the question in a maximum likelihood framework? then the metric might become more obvious $\endgroup$
    – seanv507
    Dec 27 '20 at 14:16
0
$\begingroup$

Reduction of Markov Chains using a Value-of-Information-Based Approach

describes a process to measure exactly what you describe

The first is a means of comparing pairs of stationary chains on different state spaces, which is done via the negative Kullback-Leibler divergence defined on a model joint space

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.