{'fraction_non_alphanumeric': 0.03932394366197183, 'fraction_numerical': 0.012056338028169014, 'mean_word_length': 4.31149012567325, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Investigations of the effects of random sampling patterns on the stability of generalized sampling

We investigate how the choice of spatial point process for generating random sampling patterns affects the numerical stability of non-uniform generalized sampling between Fourier bases and Daubechies scaling functions. Specifically, we consider binomial, Poisson and determinantal point processes and demonstrate that the more regular point patterns from the determinantal point process are superior.


Introduction
Generalized sampling [3,4] is a technique for computing a representation of a function in one basis/frame of a Hilbert space from another. The theory is abstract and does not restrict the type of bases or frames that can be considered, and this provides the freedom to adapt the setup to the structure of the functions at hand. In a typical application, we have samples of the function given as inner products with respect to some fixed basis or frame imposed by the measuring process, but prior knowledge of the general function structure dictates a desire to change to another more efficient representation system for the function. For example, one may have access to Fourier samples of an image, but would like to change to a more efficient representation system for images such as wavelets.
An essential quantity ensuring numerical stability of the generalized sampling approach is the condition number of the change of basis (or frame) matrix (for short "condition number") between the two representation systems considered, see [3]. The condition number will, in general, depend on the sampling scheme and on the sampling and representation system. If the sampling scheme is a subset of a regular grid, the numerical stability of the change of basis matrix is well understood in the Fourier/wavelet setup [1,5,6]. However, the data acquisition process often forces one to consider non-regular sampling schemes [7] where numerical stability is less well understood.
In this paper we consider sampling schemes obtained randomly in the Fourier/wavelet setup and study how the condition number can be controlled by using binomial, Poisson and determinantal point processes (DPPs, see [15,20] and the references therein). We demonstrate that DPPs are particularly useful because nearby points in the process repel each other. There are previous studies of the numerical stability of Fourier systems with random sampling schemes [9,19], but only using the binomial point process.
The condition number depend on the density and bandwidth of the sampling scheme (as defined in Section 2). For the Poisson process, we derive a theoretical result (Theorem 5) relating the density and the intensity of the process. Estimating the probability that a random point pattern satisfies an appropriate density criterion is a natural extension of results in [3] for the parameters of non-random sampling schemes.

Generalized sampling
In the following, we recap the framework of generalized sampling, introduced in a series of papers by Adcock, Hansen and collaborators, see [2,3,4]. Let H be a separable Hilbert space and let f ∈ H be an element we want to reconstruct from measurements c k = s k , f , where {s k } is the set of sampling vectors. The reconstruction is an approximation of f of the formf = j β j r j , where r j are called reconstruction vectors. In practice, the index sets for k and j should be finite, which means that the quality of the reconstructioñ f ∈ span j {r j } depends heavily on the choice of reconstruction vectors. In the following, we assume that the unknown function f is an element of L 2 (R d ) supported in the compact set E, and we focus on frequency measurements (i.e. the c k 's are certain values of the Fourier transform of f ) .
Let Y ⊂ R d be a closed, simply connected set with 0 in its interior, referred to as our observation window. The set of frequencies where we measure f is denoted Ω ⊂ Y and is referred to as a sampling scheme. The bandwidth of the observation window/sampling scheme is max y∈Y |y| ∞ .
If Ω is not a subset of a (sufficiently nice subset of a) lattice in R d , the classical theory is not applicable, and we need to use the so-called non-uniform generalized sampling, see [2,3]. In the following, we recall some results from these papers.

Theorem 1 ([2])
Assume that we have a countable sampling scheme Ω ⊂ R d , a finite dimensional reconstruction space, i.e., a subspace T ⊂ H = L 2 (R d ), and a non-negative, bounded, selfadjoint operator S : H → H such that for all f ∈ H, Sf is uniquely determined by {f (ξ)} ξ∈Ω and there exists a C > 0 such that for all f ∈ T , Sf, f ≥ C f 2 . Then for every f ∈ H there exists a uniquef = F (f ) ∈ T determined by ∀g ∈ T : Sf, g = Sf , g where P denotes the orthogonal projection on T .
To apply the theorem, we need to verify the assumptions. In [3], it is shown that if T ⊂ L 2 (E) ⊂ H for a sufficiently nice, compactly supported set E, and if {x → √ µ ξ e 2πiξ·x1 E (x) } ξ∈Ω with suitably chosen µ ξ > 0 is a so-called weighted Fourier frame for L 2 (E), then S can be chosen to be the corresponding frame operator, and they establish sufficient conditions on Ω which ensures that such a weighted frame exists. Since we want to go to finite subsets of Ω, choose a labelling such that {ξ n } ∞ n=1 = Ω and let Ω N = {ξ n } N n=1 for positive integers N . With T and S as above, [3] establishes sufficient conditions for the corresponding truncated frame operator S N to satisfy the conditions of Theorem 1. Before we can state the condition, we need to introduce some additional notation.
Note that E • is automatically also compact, convex and symmetric, so |·| E • is welldefined. We can now define the relative, inverse density of Ω in an observation window If the norm used is just the usual one, we omit the subscript "E • ".
, then there exists weights µ ξn > 0, ξ n ∈ Ω such that {e n } n∈N is a frame for L 2 (E). Moreover, the weights µ ξn may be chosen as the measures of the Voronoi regions (of ξ n ) with respect to the |·| E • norm.
This result is obviously not applicable for finite sets Ω, as the inverse density of a finite set is infinite. But since we are only interested in vectors in the finite dimensional T , we can do with less than a frame for L 2 (E):

Theorem 4 ([3])
Let T ⊂ L 2 (E) be finite-dimensional, E be a compact, convex and symmetric set, and assume δ E • (Ω, R d ) < 1 4 . Let {e n } n∈N be a frame satisfying the conditions in Theorem 3 and let A and B be the frame bounds. Assume that Y is an observation window, such that Ω N = Ω ∩ Y is finite and that The reconstruction is computed by solving a least squares problem where the design matrix is a finite section of the change of basis matrix between the sampling and reconstruction vectors. The quality and convergence speed of an iterative solver like conjugate gradients depends on the condition number of this matrix [12]. It is the weights in Theorems 3 and 4 that ensure small condition numbers for non-regular sampling schemes. In particular, without weights the numerical stability would worsen for sampling schemes with clusters. A sampling scheme can cause large conditions numbers if the density requirement is violated or if the bandwidth is small [2, Theorem 6.1].

Binomial, Poisson and determinantal point processes
In this section we assume Ω is a locally finite spatial point process in R d without multiple points and any accumulation point, i.e. we can view Ω as a closed random subset of R d so that with probability one, for any bounded set B ⊂ R d , the intersection Ω ∩ B is finite. For measure theoretical details, see [17] and the references therein. We focus on three models: binomial, Poisson and determinantal point processes. We discuss only the definitions and properties of these models which become relevant for our purpose. In particular, in the case where Ω is a stationary Poisson process, we establish a lower bound on the probability that δ(Ω, Y ) < 1/4. We use the generic notation K for a Borel set K ⊂ R d of finite Lebesgue measure |K|. Moreover, N (K) denotes the random number of points in Ω ∩ K.

Binomial and Poisson processes
For a given Borel set . . , ξ n } is called a binomial point process. This is the model used in [9], and it can be extended as follows. Let ρ > 0. If for any Borel set K ⊂ R d with |K| < ∞, we have that N (K) is Poisson distributed with parameter λ = ρ|K|, and conditional on N (K) = n > 0, the n points in Ω ∩ K form a binomial point process, then Ω is a stationary Poisson process on R d with intensity ρ. The process is often referred to as "complete spatial randomness".
The following theorem is verified in A, and it is of particular interest for us when K = Y is the observation window.

Theorem 5
Suppose Ω is a stationary Poisson process with intensity ρ > 0 and consider any Borel

Determinantal point processes
Determinantal point processes (DPPs) are models for repulsiveness (inhibition or regularity) between points in "space", where space means R d in the present setting. DPPs are of interest because of their applications in mathematical physics, combinatorics, randommatrix theory, machine learning and spatial statistics, and because they provide rather flexible and tractable parametric models, see [15] and the references therein.
In this paper we restrict attention to kernels defined by a continuous complex function C 0 ∈ L 2 (R d ) so that C(x, y) = C 0 (x − y) is assumed to be positive semi-definite. As discussed in [15] these are rather mild conditions, though the continuity assumption excludes the case of the Poisson process. For ϕ ∈ L 1 (R d ), denote its inverse Fourier transform by F −1 (ϕ), i.e.
Then the existence of the DPP is equivalent to the existence of a function ϕ ∈ L 1 (R d ) such that 0 ≤ ϕ ≤ 1 and C 0 = F −1 (ϕ), cf. Corollary 3.3 in [15]. Then ϕ is called the spectral density of the DPP, and the intensity ρ (1) (x) = ρ does not depend on x and is given by ρ = C 0 (0). Moreover, by comparison with the Poisson process, the repulsiveness of the process is reflected by that fact that ρ (n) (x 1 , . . . , x n ) ≤ ρ n (see [15]). Therefore, we expect that P(δ(Ω, K) < 1/4) is larger than in the Poisson case. In fact this in accordance with our experimental results discussed in Section 4. Moreover, an important observation in [15] is the trade-off between how large ρ can be and how strong the repulsiveness in the DPP can be. Several examples of such kernels C and their spectral densities are discussed in [15]. A simulation algorithm for the corresponding DPPs is available in the spatstat package [8] -in particular with the contribution from [15].
For instance, a power exponential spectral model is specified by its spectral density given by where · denotes usual Euclidean distance, ρ > 0 is the intensity, ν > 0 is a shape parameter and α ∈ (0, α max ] is a scale parameter, where For fixed values of ρ and ν, the DPP becomes more and more repulsive as α increases to α max ; and for a fixed value of ρ and letting α = α max , as ν increases, the DPP ranges from the Poisson process (the limiting case of ν → 0) to the "most repulsive DPP" (the limiting case of ν → ∞), see [15] for the details.

Experiments
We compare the condition numbers obtained when using random sampling schemes generated from the binomial, Poisson and determinantal point processes. The reconstruction functions are Daubechies scaling functions (see e.g. [13]) on [− 1 2 , 1 2 ] 2 using the boundary correction of [11]. The scaling functions are chosen for convenience due to the fact that the software from [14] reconstructs scaling functions instead of wavelets. However, this does not affect the numerical stability of generalized sampling as this only depends on the reconstruction subspace and not on the basis of choice, see also [1, §4.4]. Figure 1 shows a simulation from a DPP and a Poisson process when we have the same mean number of points in an observation window. The Poisson (and binomial) point processes show "complete spatial randomness", whereas the DPP is repulsive and give rise to a more regular point pattern with less "empty space".
Let the observation window be Y = [−64, 64] 2 , since the theory of generalized sampling dictates that the sampling area should be symmetric with a bandwidth that depends on the number of functions we wish to reconstruct. We let the DPP kernel be a power exponential spectral model with shape parameter ν = 10 and scale parameter α = α max ; this is very close to the "most repulsive DPP" (see [15]).
For each point process model we made 100 simulations, where the fixed number of points in the binomial point process is n = 4096 and the intensity of both the Poisson process and the DPP is ρ = 1/4. Thus in all cases, the expected number of points is E{N (Y )} = 4096. Simulations of the point processes were performed in R [18] with the spatstat package [8]. The condition numbers were computed in Julia [10] with the GeneralizedSampling package from [14]. The code used in the experiments is available at http://doi.org/10.5281/zenodo.887928.
Depending on the nature of the sampling locations and the choice of reconstruction scaling function, we can recover up to 32 2 = 1024 scaling functions, i.e., scaling functions at scale 5. However, this is overly optimistic in our experiments with non-uniform points that do not fulfill the density assumption of Theorem 4. The support of the Daubechies p scaling functions at scale J is of length 2 −J (2p − 1). Since our reconstruction space is we must have less than or equal to 7 vanishing moments of the reconstructed wavelet to ensure that the support of the scaling functions are fully contained in [− 1 2 , 1 2 ].

Results
We investigated three questions: (1) Which Daubechies basis is best for reconstruction (independently of the choice of point process)? (2) Which point process is best for reconstruction (independently of the choice of Daubechies basis)? (3) How does the density of a point pattern influence the reconstruction? For all three point processes, the Haar scaling functions gave rise to the lowest condition numbers. In fact, as shown in Table 1 the condition numbers for Haar was measured in tens, where the condition numbers for the other functions were measured in hundreds or thousands. This is consistent with the theoretical results for generalized sampling with regular sampling schemes in [5].

Binomial
Poisson As can be concluded from Table 1, the DPP consistently gave rise to the lowest condition numbers and standard deviations. Strong evidence suggested that the mean condition number for the DPP is significantly lower than for both the binomial and Poisson process sampling schemes (for the Haar scaling functions that generally have the lowest condition numbers, the p-value is < 10 −6 when using Tykey's range test). For both the binomial and Poisson process sampling schemes the average condition numbers and standard deviations were similar.
As mentioned in Theorem 4, a small density of a point pattern is (part of) a sufficient condition for a small condition number. In our simulations none of the realizations had small densities. Figure 2 shows scatterplots of densities of the point patterns versus the condition number for reconstruction with the Haar scaling functions, where for each of the processes individually, there is no significant correlation between the density and the condition numbers (p-value ≈ 0.17 for the binomial point process, p-value ≈ 0.50 for the Poisson process and p-value ≈ 0.72 for the DPP using the test based on Pearson's product-moment correlation). This is in contrast to the case of deterministic sampling, where a violation of the density condition has severe impact on the condition number. An example is given in Table 2 showing the rapidly increasing condition numbers obtained for the Haar function and deterministic sampling on εZ 2 for increasing values of ε using the same observation window as above and recovery of scaling functions up to level 5.

Conclusion
In this paper we have investigated how the choice of sampling according to a random sampling scheme affects the numerical stability of 2D non-uniform generalized sampling measured by the condition number.
We have compared three kinds of random point patterns, generated by binomial, Poisson or determinantal point processes. As reconstruction bases we have considered Daubechies scaling functions with polynomial reconstruction of degree 1 through 7 and the moment preserving boundary correction of [11].
Our results can be summarized as follows: 1) We have shown that certain sampling schemes can give rise to large densities while retaining small condition numbers. This is surprising because the theory dictates that a small density is part of a sufficient condition for small a condition number. 2) For all scaling functions sampling points from the determinantal point process yields the lowest mean condition number. 3) For all kinds of sampling points the Haar scaling function yields the lowest condition numbers. Point 3) is consistent with the findings of [5].
A theoretical result has been obtained for Poisson processes in Theorem 5 and it would be interesting to extend the validity to the case of a general DPP. However, the the proof of Theorem Theorem 5 relies heavily on the strong independence properties of a Poisson process, and a much more sophisticated approach will be needed to extend the result to the case of a general DPP. We leave this for future research.

A. Proof of Theorem 5
Let Ω be a stationary Poisson process on R d with intensity ρ > 0. Many statements in the sequel are only satisfied almost surely (a.s.), i.e. with probability one.