Cover art: Issues in the metric-guided and metric-less placement of random and stochastic template banks

The efficient placement of signal templates in source-parameter space is a crucial requisite for exhaustive matched-filtering searches of modeled gravitational-wave sources, as well as other searches based on more general detection statistics. Unfortunately, the current placement algorithms based on regular parameter-space meshes are difficult to generalize beyond simple signal models with few parameters. Various authors have suggested that a general, flexible, yet efficient alternative can be found in randomized placement strategies such as random placement and stochastic placement, which enhances random placement by selectively rejecting templates that are too close to others. In this article we explore several theoretical and practical issues in randomized placement: the size and performance of the resulting template banks; the very general, purely geometric effects of parameter-space boundaries; the use of quasirandom (self-avoiding) number sequences; most important, the implementation of these algorithms in curved signal manifolds with and without the use of a Riemannian signal metric, which may be difficult to obtain. Specifically, we show how the metric can be replaced with a discrete triangulation-based representation of local geometry. We argue that the broad class of randomized placement algorithms offers a promising answer to many search problems, but that the specific choice of a scheme and its implementation details will still need to be fine-tuned separately for each problem.

Figure 1

Efficiency of partial coverings. Left: thickness of $(\mathrm{A}d{)}^{*}$ coverings as a function of the covering fraction, for $d=2–8$. Right: isotropic dilation factor between a complete covering and partial covering of the same thickness, for the covering fraction given on the horizontal axis.

Figure 2

Three ways in which manifold curvature disturbs a lattice covering laid out periodically along manifold coordinates. Left: variation in the metric’s determinant causes spheres with the same geodesic-distance radius to have different coordinate radii. Center: variation in the ratio of the metric’s eigenvalues maps geodesic-distance spheres into coordinate ellipses. Right: variation in the metric’s eigenvectors changes the orientation of coordinate ellipses. Because of all three effects, the covering fraction comes to depend on the position in the manifold.

Figure 3

Left: effect of dilating space along the $x$ direction and contracting along $y$, for a $d=2$ hexagonal covering. The dilation-contraction factor is 2, so the determinant of the transformation is 1. The spheres centered on the lattice points are now too far apart along the $x$ direction, too close along $y$. The new lattice realizes a covering with the larger radius (i.e., maximum template distance) of the dashed circle. Notice that the Voronoi cells (i.e., the sets of points closer to a given lattice point than to any other lattice point) of the stretched lattice are not the stretched Voronoi cells of the original lattice. Right: reduction in covering fraction (for a fixed thickness) or increase in thickness (for a fixed covering fraction) for the dilation-contraction of the left panel, shown here also for a $d=2$ cubic covering. As we shall see in Sec. 4, random coverings are not affected.

Figure 4

Left: typical geometry that enters the computation of the variance of the covering fraction and of boundary effects. The basic ingredient is the volume of the slice of a sphere cut by parallel hyperplanes. Right: boundary effects. The probability that a generic point is covered scales with the “available” manifold volume within a distance smaller than the covering radius.

Figure 5

Probability of covering a point at a distance $\rho$ from a ($d-1$)-dimensional boundary with a sphere from: left—a random bulk covering with $p_C=95\%$; center—a random boundary covering with $p_S=77\%$; right—either covering. As in the main text, here $r$ is the covering radius.

Figure 6

Halton’s quasirandom sequence. Left: to obtain the $n$-th number in the sequence, write $n$ as a base-$b$ number (here 2), reverse the digits, add a radix point at the left, and interpret the resulting string as a number $\in [0,1)$. This algorithm fills a succession of finer and finer Cartesian grids, spreading out the points maximally on each, since the most rapidly changing $b$-ary digit of $n$ controls the most significant digit of the placement [28]. Right: the combination of base-2 and -3 Halton sequences fills the unit square more uniformly than the same number of (pseudo-)randomly placed points.

Figure 7

Left: effective thickness as a function of covering fraction for Sobol quasirandom coverings of bulk ${\mathbb{E}}^d$, for $d=$ 2, 4, and 6, as compared to the theoretical expectation for random coverings. (As a control, we used the same “experimental” setup to evaluate the random-covering thickness for $d=$ 2, 4, and 6, which matches the theoretical expectation very accurately, and is not shown here.) Right: deterioration of quasirandom covering thickness on curved manifolds. We estimate the effect of applying a rejection method in the presence of a varying $\sqrt{|g_{kl}|}$ by extracting random subsets of $1/2$, $1/5$, and $1/10$ of all points from a Sobol covering of ${\mathbb{E}}^2$, and evaluating the resulting thickness. Already for a range of variation $\sim 10$ in $\sqrt{|g_{kl}|}$, the thickness grows very close to its random-covering value for the same covering fraction.

Figure 8

Mapping of a parameter-space triangulation $T$ onto the signal manifold $\mathcal{H}$. If the $\Delta$ edge lengths are smaller than the characteristic curvature scale $\delta$ of the manifold, the image of $T$ will lie close to $\mathcal{H}$.

Figure 9

Three phases in the refined triangulation of ${\mathbb{E}}^2$, performed by placing new points at the barycenters of existing triangles.