4

Let $A_{ij}$ be a $n\times n$ random binary matrix with probability mass function $P(A)$ given by $$ \log P(A)=-\frac 12 \mathrm{tr}\left[\left(A-M\right)^TV\left(A-M\right)\right] + C, $$ where $M$ and $V$ are also $n\times n$ matrices, $\mathrm{tr}$ denotes the trace of a matrix, $A^T$ is the transpose of $A$, and $C$ is a normalisation constant.

If $A$ was a real matrix, it would follow a matrix normal distribution and could be sampled easily. However, $A$ is a binary matrix in this problem. Is the above a known distribution? Is it possible to draw samples from it efficiently? I would like to avoid sampling the matrix using a Gibbs sampler.

Xi'an
  • 90,397
  • 9
  • 157
  • 575
Till Hoffmann
  • 827
  • 5
  • 15
  • 3
    I doubt you will find a direct simulation method for this Ising-like distribution. E.g., the normalisation constant is most likely intractable. – Xi'an Mar 07 '16 at 16:12
  • 1
    The problem I'm facing with a Gibbs sampler is that the probability mass function is quite rough such that the sampler gets stuck in local equilibria. I'll have a look whether I can find an "annealed" Gibbs sampler to do the job. – Till Hoffmann Mar 07 '16 at 17:28

1 Answers1

5

The target probability mass function is of the form $$\begin{align}p(A)&\propto \exp\left\{-\frac 12 \mathrm{tr}\left[\left(A-M\right)^TV\left(A-M\right)\right]\right\}\\ &\propto \exp\left\{-\frac 12 \sum_{ij}(a_{ji}-\mu_{ji})\sum_{k} v_{jk} (a_{ki}-\mu_{ki})\right\}\\&\propto \exp\left\{-\frac 12 \sum_{ijk}v_{jk}a_{ji}a_{ki}+\frac 12 \sum_{ijk}v_{jk}a_{ji}\mu_{ki}+\frac 12 \sum_{ijk}v_{jk}\mu_{ji}a_{ki}\right\}\\ &\propto\exp\left\{-\frac 12 \sum_{ijk}v_{jk}a_{ji}a_{ki}+\frac 12 \sum_{ij}a_{ji}\left[\sum_k v_{jk}\mu_{ki}+ \sum_k v_{kj}\mu_{ki}\right]\right\}\\&\propto\exp\left\{-\frac 12 \sum_{ijk}v_{jk}a_{ji}a_{ki}+\frac 12 \sum_{ij}a_{ji}\sum_k \left[v_{jk}+ v_{kj}\right]\mu_{ki}\right\}\end{align}$$ if $M=(\mu_{ij})_{ij}$ and $V=(v_{ij})_{ij}$. It is therefore exactly an Potts model over $\{0,1\}^{n\times n}$ and there is no known exact simulation method (apart from perfect sampling).

Simulation by Gibbs sampling of the Potts model may indeed be quite slow. Accelerating techniques are the Swendsen–Wang algorithm, the Wolff algorithm and parallel tempering.

Xi'an
  • 90,397
  • 9
  • 157
  • 575
  • Thank you for the suggestions. Do you happen to know whether there are sensible (mean-field) variational approximations, or do they suffer from the same problems as the Gibbs sampler? – Till Hoffmann Mar 08 '16 at 09:48