Curvature-based rejection sampling
Isabella Costa Maia [email protected], Marco Congedo [email protected], Pedro L. C. Rodrigues [email protected], Salem Said [email protected] · 2025
Read Curvature-based rejection sampling by Isabella Costa Maia [email protected], Marco Congedo [email protected], Pedro L. C. Rodrigues [email protected], Salem Said [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24537.txt.
Introduction
Isabella Costa Maia leads a team of four authors on random sampling. Sampling means drawing random points that follow a target density. Their densities live on Riemannian manifolds, curved spaces with distances. Only the distance from a center sets the density value. Rejection sampling draws from a simple density and keeps good draws.
Their method, CURS, pairs rejection sampling with volume comparison. Volume comparison bounds how curved space spreads versus flat space. The method is exact: kept draws follow the target precisely. Its cost stays moderate when the manifold meets mild conditions. The authors argue CURS should be the first choice in low dimensions. Many curved-space tasks in statistics fit that low-dimensional case. The work links a classic statistics trick to modern geometry.
Catalog record
| CREATOR | Isabella Costa Maia [email protected], Marco Congedo [email protected], Pedro L. C. Rodrigues [email protected], Salem Said [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24537
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Curvature-based rejection sampling Isabella Costa Maia [email protected], Marco Congedo [email protected], Pedro L. C. Rodrigues [email protected], Salem Said [email protected] Abstract The present work introduces curvature-based rejection sampling (CURS). This is a method for sampling from a general class of probability densities defined on Riemannian manifolds. It can be used to sample from any probability density which “depends only on distance". The idea is to combine the statistical principle of rejection sampling with the geometric principle of volume comparison. CURS is an exact sampling method and (assuming the underlying Riemannian manifold satisfies certain technical conditions) it has a particularly moderate computational cost. The aim of the present work is to show that there are many applications where CURS should be the user’s method of choice for dealing with relatively low-dimensional scenarios. 1 Introduction The present work introduces a new method for sampling from probability densities defined on Riemannian manifolds. This method is called curvature-based rejection sampling (CURS). It addresses the problem of sampling from a probability density function which “depends only on distance". Specifically, let M be a Riemannian manifold and let x_{\scriptscriptstyle o} be some point in M . CURS can be used to sample from any probability density p on M , of the form p(x)\propto f(r(x))\text{ where }r(x)=d(x_{\scriptscriptstyle o}\hskip 0.56917pt,x) (1) Here, p\propto f means p is proportional to f , and d(x_{\scriptscriptstyle o}\hskip 0.56917pt,x) denotes the Riemannian distance between x_{\scriptscriptstyle o} and x in M (the precise definition of a probability density on M is given in the following Section 2 ). CURS is a geometric rejection sampling method which has the following advantages : • it is a rather general method, since it applies to any density p of the form ( 1 ) and to a large class of manifolds M . For example, it applies successfully whenever M is a so-called Hadamard manifold, such as a manifold of covariance matrices (real, complex, Toeplitz, etc. ) ( Lee 2018 ; Said et al. 2018 ) , but is by no means limited to this special case of Hadamard manifolds. • it is an exact method, which produces samples that immediately follow the density p , with no need for any kind of burn-in period. This is in contrast to existing Markov-Chain Monte Carlo methods. • the computational cost of a single iteration of this method is quite moderate. • it is often possible to theoretically evaluate the time complexity of this method, by computing its rejection probability. In this way, one has a theoretical performance guarantee. The introduction of CURS was motivated by the specific problem of sampling from a Gaussian density p(x)\propto\exp\!\left[-\frac{d^{\hskip 0.56917pt2}(x_{\scriptscriptstyle o}\hskip 0.56917pt,x)}{2\sigma^{2}}\right]\text{ where }\sigma>0 (2) which is defined on the manifold M of real covariance matrices. In the notation of ( 1 ), this corresponds to f(r)=\exp(-r^{2}/2\sigma^{2}) . Section 5 , below, will return to this problem. At present, existing methods for sampling on manifolds can be divided into exact and approximate methods. Exact methods tend to be specialized, applicable only to specific probability distributions and specific classes of manifolds. For example, there exist highly effective methods for sampling from uniform distributions on compact Lie groups, or from classical directional distributions on Stiefel and Grassmann manifolds ( Meckes 2019 ; Chikuse 2003 ) . Clearly, the major drawback of such methods is that they are too specialized, as they are of no immediate use beyond their originally intended goal. Approximate methods are based on geometric Markov Chain Monte Carlo techniques (geometric MCMC). They are very general, as they can be used to sample from any positive density, on any Riemannian manifold which satisfies rather mild technical conditions. Famous examples of such methods include Hamiltonian Monte Carlo and geometric Langevin MCMC ( Girolami & Calderhead 2011 ; Bharath et al. 2025 ) . Their main drawback is their computational complexity, due to the use of often complicated discretization schemes. CURS follows a kind of middle ground which allows it to make the best of both worlds. Being neither too specialized nor completely general, it is able to perform exact sampling at a moderate computational cost. Its main drawback is that, being a rejection sampling method, its performance is significantly affected by the curse of dimensionality. Still, users should find it useful to know about CURS, and retain it as part of their toolbox, due to its highly advantageous performance-complexity tradeoff in relatively low-dimensional scenarios. The present work is organised as follows. Section 2 explains the general idea behind the CURS method. Section 3 formalises this idea into pseudo-code instructions. Section 4 discusses the geometric interpretation of CURS, while Section 5 applies it to the problem of sampling from a Gaussian density of the form ( 2 ). Finally, Section 6 is concerned with a more general version of CURS, extending its applicability to a larger class of Riemannian manifolds. 2 The idea behind CURS 2.1 Geodesic spherical coordinates Consider the problem of sampling from a probability density p of the form ( 1 ). Since p(x) depends only on the distance r(x) , one may hope to perform a separation of variables, by introducing geodesic spherical coordinates ( Chavel 2006 ; Lee 2018 ) . These coordinates parameterise the point x\in M using two quantities, the distance r and the direction s (in fact, s is a unit-length tangent vector to M at the point x_{\scriptscriptstyle o} ). Then, x is obtained by moving for a distance r along a geodesic curve starting at x_{\scriptscriptstyle o} and whose initial velocity is equal to the vector s . In terms of the Riemannian exponential mapping ( Chavel 2006 ; Lee 2018 ) x=\mathrm{Exp}_{x_{\scriptscriptstyle o}}(r\hskip 0.85355pts) (3) which will be abbreviated to x=x(r,s) . In general, geodesic spherical coordinates do not regularly cover the entire manifold M , but are limited to a subset D_{x_{\scriptscriptstyle o}} called the domain of injectivity. For now (to simplify the presentation) it is assumed that D_{x_{\scriptscriptstyle o}}=M , so the mapping (r,s)\mapsto x(r,s) in ( 3 ) is a diffeomorphism from (0,\infty)\times S_{x_{\scriptscriptstyle o}}M to M-\{x_{\scriptscriptstyle o}\} (here, S_{x_{\scriptscriptstyle o}}M denotes the set of unit-length tangent vectors to M at x_{\scriptscriptstyle o}\hskip 0.85355pt ). This assumption is certainly verified when M is a Hadamard manifold, such as a manifold of covariance matrices (real, complex, Toeplitz, etc. ) ( Lee 2018 ; Said et al. 2018 ) . It will be dropped later on, in Section 6 . One hopes to sample x by first separately sampling r and s and then replacing them into ( 3 ). The major stumbling block for this approach will be the difficulty in expressing the Riemannian volume measure of M . To say that p is a probability density on M means that the probability distribution of a random point x (when x is sampled from p ) is given by P(dx)=p(x)\hskip 0.85355pt\mathrm{vol}(dx) (4) where \mathrm{vol} denotes the Riemannian volume measure of M . From ( 1 ), the joint distribution of r and s is then P(dr\times ds)\propto f(r)\hskip 0.85355pt\mathrm{vol}(dr\times ds) (5) where \mathrm{vol}(dr\times ds) is just \mathrm{vol}(dx) , but expressed in terms of r and s . This is given as follows. Note that S_{x_{\scriptscriptstyle o}}M is the unit sphere in