3
$\begingroup$

Suppose that you have a topological space $\Omega \subset \mathbb R^n$ accompanied a measure $\mu$ and you're running an iterative sampling algorithm like Metropolis-Hastings. To sample you choose a random element $x_1$ of $\Omega$ and then assign a measure $s$ on $\Omega$ conditional on $x_1$ (typically $s$ is just a gaussian distribution centered on $x_1$, where the distance is just the distance in $\mathbb R^n$) and then choose high probability point locally and do it again.

It seems to me that this process is subtly decomposing $\Omega$ into a bunch of local spaces which look like $R^m \subset R^n$ with a continuous group action on them, like a lie group with a Haar measure (that happens to be equivalent to $s$) and you're moving along the geodesic lines of the lie group.

I know this is a super vague question, because this is definitely just an analogy, but I was wondering if there is work on something like this? The case I can imagine being workable is $\Omega$ being a discrete space because then it would locally look like lattice and then this sampling procedure might look like optimization on an orbifold. I have no idea for the continuous case, however. Is there any work that sort of looks at this? Or a general area I should look into?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Let's think about the simpler situation $\Omega = \{1,\dots,n\} =: [n]$. For some proposal $j \in [n]$, Metropolis-Hastings corresponds to a particular simple (I hesitate to say "natural") choice of sparse matrix in the Lie algebra of the Lie group preserving the target distribution, as arxiv.org/abs/1901.08606 points out. As to the decomposition you suggest, nothing immediately comes to mind, but this is probably just a deficit of my own imagination at the moment. $\endgroup$
    – Steve Huntsman
    Commented Apr 6, 2021 at 14:22
  • 1
    $\begingroup$ Not sure--maybe? I don't really think of it that way. I think of it as there is a Lie group that encodes the residual freedom of any MCMC acceptance criterion. Practical acceptance criteria correspond to "tractable" elements of the Lie group. Two threads I did not really pull on are what happens if you allow negative entries and/or trying to do something a bit more elaborate along the lines at the end of section 4. Re: the latter, a decent computer algebra system will highlight some alternative if lengthy expressions that might be salient/useful. $\endgroup$
    – Steve Huntsman
    Commented Apr 6, 2021 at 16:20
  • 1
    $\begingroup$ Also maybe relevant: mathoverflow.net/a/36037/1847 $\endgroup$
    – Steve Huntsman
    Commented Apr 6, 2021 at 16:24
  • 1
    $\begingroup$ Are you aware of random walks on groups? mathoverflow.net/questions/158210/… googling also found me these notes: math.u-bordeaux.fr/~jquint/publications/CoursChili.pdf $\endgroup$
    – NWMT
    Commented Apr 7, 2021 at 11:01
  • 1
    $\begingroup$ The process $x_i \to x_{i+1}$ you describe could be achieved by sampling some element $g_i$ from a symmetry group of $\Omega$ from a probability distribution $p_i$ and then $x_{i+i}=g_i\cdot x_i$. $\endgroup$
    – NWMT
    Commented Apr 7, 2021 at 11:11

0

Reset to default

You must log in to answer this question.