Geodesic slice sampling on the sphere

This paper introduces efficient, parameter-free geodesic slice sampling algorithms for generating samples from probability distributions on the sphere, proving their uniform ergodicity and demonstrating superior performance over standard methods like random-walk Metropolis-Hastings and Hamiltonian Monte Carlo in challenging directional data scenarios.

The Gist

Imagine you are trying to find the highest peak in a vast, foggy mountain range, but there's a catch: you can only walk along the surface of a giant, invisible balloon.

This is the world of the paper "Geodesic Slice Sampling on the Sphere." It's about a new way for computers to explore complex shapes (like spheres) to find the most important information hidden inside them.

Here is the breakdown of the problem and the solution, using simple analogies.

The Problem: The Foggy Balloon

In many scientific fields (like figuring out how proteins fold in biology or how to align 3D maps in robotics), data doesn't live on a flat sheet of paper (like a standard graph). It lives on the surface of a sphere (like the Earth).

Scientists use computers to "sample" this data—basically, sending out a digital explorer to wander around the sphere and map out where the "good stuff" (high probability areas) is.

The old methods had two big flaws:

1. The Random Drunkard (Random Walk Metropolis-Hastings): Imagine a person walking on the balloon who takes tiny, random steps. They might stumble into a small hill and get stuck there for hours, never realizing there is a massive mountain nearby. They move too slowly and get trapped in local "valleys."
2. The Over-Engineered Hiker (Hamiltonian Monte Carlo): Imagine a hiker with a high-tech GPS and a jetpack. They can move fast, but they need to know the exact slope of the ground at every single step. If the terrain is weird or bumpy, they crash or get confused. Plus, they need a lot of manual tuning (like adjusting the jetpack's fuel) to work right.

The Solution: The "Slice" and the "Great Circle"

The authors propose a new method called Geodesic Slice Sampling. Think of it as a smart, automated way to explore the balloon without needing a manual map or a jetpack.

Here is how it works, step-by-step:

1. The "Great Circle" (The Highway)

On a sphere, the straightest line you can draw is a Great Circle (like the Equator or a line of longitude).

• The Old Way: The explorer would take tiny, wobbly steps.
• The New Way: The explorer picks a random Great Circle passing through their current spot and decides to travel along that entire highway. It's like switching from walking on a sidewalk to driving on a highway.

2. The "Slice" (The Level Set)

Imagine the surface of the balloon has hills and valleys representing the data. The "height" of the hill is how likely that spot is to be the answer.

• The computer picks a random "height" (a slice) that is lower than where the explorer is currently standing.
• It then looks at the Great Circle and asks: "Where on this highway is the terrain higher than my chosen slice?"
• This creates a "safe zone" or a segment of the highway where the explorer is allowed to jump.

3. The Jump

The explorer picks a random spot within that "safe zone" on the highway and jumps there.

• Why this is smart: Instead of taking 1,000 tiny steps to get across the mountain, they can jump directly to a new, high-quality spot in one go. This helps them escape "traps" (local peaks) and find the global best answer much faster.

The Two Versions: "Ideal" vs. "Shrinkage"

The paper introduces two flavors of this method:

1. The Ideal Version (The Rejection Method):

   • Analogy: You pick a spot on the highway. If it's in the "safe zone," you go there. If not, you throw it away and pick another spot.
   • Pros: It's mathematically perfect and explores everything thoroughly.
   • Cons: If the "safe zone" is very small (a narrow peak), you might throw away 99 out of 100 guesses. It's wasteful.

2. The Shrinkage Version (The Smart Squeeze):

   • Analogy: Imagine you are looking for a needle in a haystack. Instead of throwing away the whole haystack every time you miss, you start with a big box. If you miss, you shrink the box to exclude the empty space you just checked. You keep shrinking the box until you find the needle.
   • Pros: It's much more efficient. It rarely wastes time checking empty spots. It's the "workhorse" of the two.

Why Does This Matter? (The Real-World Impact)

The authors tested this on some very difficult problems:

• Aligning Proteins: Imagine trying to fit two 3D shapes together (like a lock and key) to see how a drug interacts with a virus. The shapes can twist in millions of ways. The new method found the perfect fit much faster than the old methods, which kept getting stuck in "almost right" positions.
• Mixing Flavors: Imagine a smoothie with 5 different flavors mixed in. The computer needs to taste all 5 flavors equally to understand the recipe. The old methods only tasted one flavor and got stuck. The new method tasted all 5 perfectly.

The Bottom Line

This paper gives scientists a new, automatic, and efficient tool to explore complex, curved data.

• No Tuning: You don't need to fiddle with knobs or settings. The algorithm figures out the best path on its own.
• Speed: It moves faster and gets stuck less often than the standard tools.
• Simplicity: It uses the natural geometry of the sphere (great circles) to make the job easier.

In short, if the old methods were like a drunkard stumbling in the dark or a hiker needing a complex map, this new method is like a smart drone that flies along the most efficient paths, automatically avoiding dead ends to find the treasure hidden on the sphere.

Technical Summary

Here is a detailed technical summary of the paper "Geodesic Slice Sampling on the Sphere" by Habeck, Hasenpflug, Kodgirwar, and Rudolf.

1. Problem Statement

The paper addresses the challenge of efficiently sampling from probability distributions defined on the Euclidean unit sphere, $S^{d-1} \subset \mathbb{R}^d$. These distributions are critical in various fields, including:

• Directional Statistics and Shape Analysis: Modeling data with directional properties.
• Bayesian Inverse Problems: Specifically in astrophysics and geophysics where parameters lie on a sphere (e.g., $S^2$).
• Rigid Registration: Determining optimal 3D rotations (mapped to $S^3$ via unit quaternions) to align point clouds.
• Density Estimation: Approximating infinite-dimensional posteriors by truncating dimensions.

The Core Challenge: Standard MCMC methods often struggle on manifolds.

• Random Walk Metropolis-Hastings (RWMH) suffers from diffusive behavior and poor mixing, especially in high dimensions or multimodal settings.
• Hamiltonian Monte Carlo (HMC) requires gradient information and can get trapped in local modes or struggle with the specific geometry of the sphere if not carefully tuned.
• Existing methods often require significant manual tuning of step sizes or assume specific reference measures (e.g., angular Gaussian) that may not align with the target density's natural volume measure.

The goal is to develop a tuning-free, efficient MCMC algorithm that leverages the intrinsic geometry of the sphere to explore the state space effectively.

2. Methodology

The authors propose two variants of Geodesic Slice Sampling (GeoSSS), which adapt the slice sampling paradigm to the geometry of the sphere. Instead of moving in straight lines (as in Euclidean space), the algorithms move along great circles (geodesics).

Key Geometric Concepts

• Great Circles: For a current state $x \in S^{d-1}$ and a direction $v$ (chosen uniformly from the "equator" $S^{d-2}_x$ orthogonal to $x$), a great circle is defined as $\gamma_{(x,v)}(\theta) = \cos(\theta)x + \sin(\theta)v$.
• Level Sets: Given an unnormalized density $p(x)$, a level $t$ is chosen such that $0 < t < p(x)$. The algorithm restricts sampling to the intersection of the great circle and the superlevel set$L(t) = {x \mid p(x) > t}$.

The Two Algorithms

1. Ideal Geodesic Slice Sampler:

   • Mechanism: Selects a random great circle and a random level $t$. It then samples a new point uniformly from the intersection of the great circle and the level set $L(t)$.
   • Implementation: Uses an acceptance/rejection scheme where candidates are drawn uniformly from the entire great circle and accepted only if they fall within the level set.
   • Pros: Theoretically clean; directly mimics the ideal slice sampling transition.
   • Cons: Can be computationally expensive due to a high rejection rate, especially when the level set is small relative to the great circle.

2. Geodesic Shrinkage Slice Sampler:

   • Mechanism: A modification of the ideal sampler that replaces the global acceptance/rejection step with a shrinkage procedure.
   • Implementation:
     1. Proposes a point on the great circle.
     2. If rejected, the proposal interval is "shrunk" to exclude the rejected point, creating a nested interval that still contains the current state.
     3. New proposals are drawn from this shrinking interval until a point within the level set is found.
   • Pros: Significantly reduces the number of rejections per iteration compared to the ideal version, improving computational efficiency while maintaining the same theoretical properties.

Theoretical Properties

• Reversibility: Both kernels are proven to be reversible with respect to the target distribution $\pi$, provided the density $p$ is lower semicontinuous.
• Uniform Ergodicity: The authors prove that under mild boundedness conditions, both samplers are uniformly ergodic. They provide explicit convergence rates in total variation distance, showing that the convergence depends on the "size" of the level sets relative to the dimension $d$.

3. Key Contributions

1. Novel Algorithms: Introduction of the first slice sampling methods specifically designed for the sphere using geodesic (great circle) movements, including both an ideal and a computationally efficient shrinkage variant.
2. Tuning-Free Operation: Unlike HMC or RWMH, these algorithms do not require manual tuning of step sizes or proposal variances. The "step size" is implicitly determined by the geometry of the level sets.
3. Theoretical Guarantees: Rigorous proofs of reversibility and uniform ergodicity for lower semicontinuous densities, including explicit bounds on the convergence rate.
4. Geometric Integration: Theoretical development of the "Liouville measure" invariance on the sphere to prove that the transition mechanisms preserve the target distribution.

4. Numerical Results

The authors tested GeoSSS against RWMH, HMC, and a custom mixture-MH on three challenging scenarios:

A. Rigid Registration of Biomolecular Structures ($S^3$)

• Task: Aligning two protein structures (Adenylate Kinase) by finding the optimal rotation (unit quaternion).
• Challenge: The posterior is highly multimodal with a very narrow global peak.
• Result:
  • GeoSSS (Shrink): Achieved a 100% success rate in finding the global mode within 1500 iterations.
  • GeoSSS (Reject): Reached 100% success in just 200 iterations but required more computation time per step due to rejections.
  • RWMH & HMC: Failed to escape local modes, achieving success rates of only 3–7% even after 2000 iterations.
  • Conclusion: GeoSSS is vastly superior for multimodal, high-concentration problems.

B. Mixture of von Mises-Fisher Distributions ($S^9$)

• Task: Sampling from a mixture of 5 vMF distributions with high concentration ($\kappa=100$).
• Result:
  • Mixing: GeoSSS variants explored all 5 modes effectively, whereas RWMH got stuck in one mode and HMC missed two modes.
  • ESS (Effective Sample Size): GeoSSS (Reject) achieved the highest ESS, though GeoSSS (Shrink) offered a better balance between ESS and computational cost (fewer rejections).
  • Robustness: As concentration $\kappa$ increased, all methods struggled, but GeoSSS remained the most robust.

C. Curved Distributions ($S^2$ and $S^5$)

• Task: Sampling from a distribution concentrated along a curved path on the sphere.
• Result:
  • In low dimensions ($d=3$), GeoSSS and HMC performed similarly well.
  • In higher dimensions ($d=5$), HMC outperformed GeoSSS, maintaining consistent ESS as dimension increased, while GeoSSS performance degraded. This suggests HMC is better suited for very high-dimensional, narrow, curved manifolds, while GeoSSS excels in moderate dimensions and multimodal landscapes.

5. Significance and Conclusion

• Practical Impact: The proposed Geodesic Shrinkage Slice Sampler offers a robust, "plug-and-play" alternative for Bayesian inference on spheres, particularly in structural biology and directional statistics where tuning parameters is difficult.
• Multimodality: The method demonstrates a distinct advantage over gradient-based methods (HMC) in navigating complex, multimodal landscapes where gradients can mislead the sampler into local optima.
• Limitations: The performance of GeoSSS degrades as the dimension $d$ and the concentration parameter $\kappa$ increase significantly. In very high dimensions with extremely narrow targets, HMC remains superior.
• Future Work: The authors note that the combination of stereographic projection (mapping $\mathbb{R}^d$ to $S^{d-1}$) with their slice sampling approach shows promise for handling heavy-tailed distributions in Euclidean space.

In summary, this paper provides a theoretically grounded, efficient, and tuning-free framework for sampling on spheres, filling a critical gap in the MCMC toolkit for geometric statistical models.