Introduction
The manifold hypothesis specifies that point cloud data is sampled from a distribution supported on a low-dimensional manifold. A natural variant of this setup is to assume that the support is instead a manifold with boundary. In this case, determining the location of the boundary and a normal vector to it become fundamental questions. Algorithms to determine the boundary have many applications. For example, in spatial transcriptomics data, each point on a grid has a gene expression vector that lies in R n \mathbb{R}^{n} R n for n n n approximately 20000. Detecting boundary regions in genomic space allow us to determine qualitative changes in underlying tissue, for example transitions from cancerous tumor regions to healthy cells. Another application of interest is to study the geometry of LLM activations. Recent mechanistic interpretability work has discovered that residual-stream activations often lie on curved submanifolds rather than linear subspaces [9 , 7 , 10 , 3 ] . Model behavior can be influenced by adding a “steering” vector at intermediate activations (Turner et al., 2024; Panickssery et al., 2024), but these interventions work best when one is able to stay on the underlying manifold (Wurgraft et al., 2026). Knowing the boundary points as well as having estimated boundary normals is useful for steering interventions and other interpretability problems. More broadly, boundary detection can be used for general-purpose methods such as clustering [2 ] (Wang et al. 2018).
Contributions
We introduce two general-purpose methods for identifying boundary points and calculating normal vectors at the boundary. Both methods are fast and practical for large data sets. Our hyperplane method works the best among all tested methods when the local dimension can be reliably estimated. When the estimated dimension m m m is larger than the true dimension, it finds the correct boundary of the data as though it were m m m -dimensional. Our directional uniformity method is more robust when noise levels prevent accurate dimension estimates.
The hyperplane method is mathematically grounded by theorems proving that boundary points can be reliably distinguished from interior points in a way that scales well with intrinsic dimension. We empirically validate both methods on synthetic data.
Finally, we show that our methodology is effective on spatial transcriptomics data for identifying a tumor boundary, and we also apply it to find the boundary of LLM activations for the character-counting manifold of [10 ] for open-weight models.
We have released the source code and scripts for reproducing our figures and experiments on github: https://github.com/aghickok/boundary_detection.
Related Work
There are several boundary-detection methods that rely on the fact that boundary points have lower density than interior points. BORDER (Xia et al., 2006) counts the number of “reverse k k k nearest neighbors” (R k N N \mathrm{RkNN} RkNN ), i.e., the number of points for which the query point is a k k k NN. Boundary points tend to have fewer k k k NNs. Averbuch-Elor et al. [2 ] and Du et al. [6 ] also use reverse k k k NNs for boundary detection, as an intermediate step towards clustering. In more detail, Averbuch-Elor et al. [2 ] and Du et al. [6 ] calculate ∑ x j ∈ R k N N ( x i ) K ( x i , x j ) \sum_{x_j\in\mathrm{RkNN}(x_i)} K(x_i,x_j) ∑ x j ∈ RkNN ( x i ) K ( x i , x j ) , where K K K is a Gaussian or Cauchy kernel, respectively. Reverse unreachability (RU) [11 ] is different; it uses the representation matrix W W W from Roweis & Saul (2000) to approximate each point x i x_i x i as a linear combination ∑ j W i j x j \sum_j W_{ij}x_j ∑ j W ij x j of its neighbors, and then reverse unreachability is defined as ∑ j 1 W j i ≤ 0 \sum_j \mathbf{1}_{W_{ji}\le0} ∑ j 1 W j i ≤ 0 . All of these methods perform poorly when the point cloud has non-uniform density.
Some methods are only designed to be used for very low-dimensional data. The direction centrality measure (Peng et al., 2022) is defined for data in R 2 \mathbb{R}^2 R 2 and the level-set method [5 ] was only applied to 2D data. Both methods can be theoretically generalized to higher dimensions, but scale poorly with ambient dimension and are not practical for data that is more than two dimensional.
The last class of methods uses geometric structure to detection boundaries in data of any dimension. Border Edge Pattern Selection (BEPS) [12 ] , CO (Wang et al., 2018), and LoDD (Peng et al., 2025) all start by projecting the nearest neighbors { x i j } \{x_{ij}\} { x ij } to the unit sphere centered at the query point x i x_i x i . Let y ˉ i j : = ( x i j − x i ) / ∥ x i j − x i ∥ \bar{y}_{ij}:=(x_{ij}-x_i)/\lVert x_{ij}-x_i\rVert y ˉ ij := ( x ij − x i ) / ∥ x ij − x i ∥ and define v ˉ i : = 1 k ∑ j = 1 k y ˉ i j \bar{v}_i:=\frac{1}{k}\sum_{j=1}^{k}\bar{y}_{ij} v ˉ i := k 1 ∑ j = 1 k y ˉ ij . BEPS is similar to our hyperplane method—the BEPS score 1 k ∑ j 1 y ˉ i j ⋅ v ˉ i ≥ 0 \frac{1}{k}\sum_j\mathbf{1}_{\bar{y}_{ij}\cdot\bar{v}_i\ge0} k 1 ∑ j 1 y ˉ ij ⋅ v ˉ i ≥ 0 is the percentage of neighbors on the positive side of the hyperplane orthogonal to v ˉ i \bar{v}_i v ˉ i . It is far less robust to noise than either of our methods, though, because the direction of the vector v ˉ i \bar{v}_i v ˉ i is sensitive to noisy perturbations off the manifold, especially on interior points where E [ v ˉ i ] = 0 \mathbb{E}[\bar{v}_i]=0 E [ v ˉ i ] = 0 .
The CO score (Wang et al., 2018) uses the same vector v ˉ i \bar{v}_i v ˉ i but scales by density and measures the alignment between neighbors. At query point x i x_i x i , the score is ∑ j = 1 k m i − 1 m j − 1 v ˉ i ⋅ v ˉ j \sum_{j=1}^{k}m_i^{-1}m_j^{-1}\bar{v}_i\cdot\bar{v}_j ∑ j = 1 k m i − 1 m j − 1 v ˉ i ⋅ v ˉ j , where m i − 1 = ∑ j ∥ x i j − x i ∥ m_i^{-1}=\sum_j\lVert x_{ij}-x_i\rVert m i − 1 = ∑ j ∥ x ij − x i ∥ is a “mass” term that is high in regions with low density. Like the other density-based methods, CO performs poorly on data with non-uniform density.
The LoDD score is ω ( ∑ i = 1 d λ i ) 2 + ( 1 − ω ) 2 d d − 1 ∑ i ∑ j ≠ i λ i λ j \omega(\sum_{i=1}^{d}\lambda_i)^2+(1-\omega)\frac{2d}{d-1}\sum_i\sum_{j\ne i}\lambda_i\lambda_j ω ( ∑ i = 1 d λ i ) 2 + ( 1 − ω ) d − 1 2 d ∑ i ∑ j = i λ i λ j , where { λ i } \{\lambda_i\} { λ i } is the set of eigenvalues of the covariance matrix for the centered, normalized neighbor vectors { y ˉ i j } \{\bar{y}_{ij}\} { y ˉ ij } and ω ∈ [ 0 , 1 ] \omega\in[0,1] ω ∈ [ 0 , 1 ] is a hyperparameter that is set to .5 in Peng et al. (2025) and in our experiments in this paper. The LoDD score has a maximum of 1 that is achieved when the eigenvalues are equal and sum to 1. It is higher for interior points because { y ˉ i j } \{\bar{y}_{ij}\} { y ˉ ij } is uniformly distributed on the d d d -dimensional sphere. LoDD has the strongest overall performance of all the existing methods we tested in the literature, but it is less robust than ours to noise, especially in high ambient dimensions. Unlike our methods (or BEPS or CO), LoDD does not produce normal vectors at each point—just pointwise boundary scores.
Hyperplane method for boundary detection
The idea of our hyperplane (HP) boundary-detection algorithm, detailed in Algorithm 1, is that if x x x is a boundary point on an n n n -dimensional manifold, then it has a neighborhood that is diffeomorphic to an n n n -dimensional half ball. A half space is defined by a hyperplane in R n \mathbb{R}^{n} R n . If x x x is a boundary point, then it is possible to find a hyperplane such that most its neighbors lie on the same side of the hyperplane. On the other hand, if x x x is an interior point, then any hyperplane will split the neighborhood in half, with roughly half the points on one side and half on the other side.
We assign each point x x x a boundary score s ( x ) ∈ [ 0 , 1 ] s(x) \in[0,1] s ( x ) ∈ [ 0 , 1 ] that is the percentage of its neighborhood lying on the same side of an “optimal” hyperplane. Boundary points have scores near 1 1 1 , and manifold points have scores near .5 .5 .5 . Near a transverse intersection of manifolds, the score is usually higher than .5 .5 .5 but lower than 1 1 1 —for example, near a transverse intersection of two manifolds, the score is near .75 .75 .75 . (See Figure 6 , for example.)1 The algorithm steps are described below.
Figure 6. Boundary scores on noisy intersecting line segments.
The algorithm
Local PCA: For each point x x x , we use local PCA to reduce the dimension of its local neighborhood { x i } i = 1 k \{x_i\}_{i=1}^{k} { x i } i = 1 k , where k k k is a parameter that controls the size of the neighborhood. If the dimension n n n of the manifold is known, then we reduce to n n n dimensions; otherwise, we use a spectral gap threshold condition. Let { z ⃗ i } i = 1 k \{\vec{z}_i\}_{i=1}^{k} { z i } i = 1 k be the neighborhood after dimension reduction and after centering so that x x x is mapped to 0 ⃗ \vec{0} 0 .
Hyperplane optimization: We solve for an “optimal” hyperplane that best separates the data points onto a single side of the hyperplane. Every hyperplane is determined by an orthogonal vector w ⃗ \vec{w} w with norm ∥ w ⃗ ∥ = 1 \lVert\vec{w}\rVert= 1 ∥ w ∥ = 1 . A point z ⃗ i \vec{z}_i z i lies on the “positive” side of the hyperplane if z ⃗ i ⋅ w ⃗ > 0 \vec{z}_i \cdot\vec{w} > 0 z i ⋅ w > 0 . A hyperplane is good if most of the points lie on the positive side of the hyperplane. To formulate this, we solve the optimization problem
argmax w ⃗ f ( w ⃗ ) = ∑ i = 1 k z ⃗ i ⋅ w ⃗ , subject to g ( w ⃗ ) = ∥ w ⃗ ∥ 2 = 1. (1) \underset{\vec{w}}{\operatorname{argmax}}\ f(\vec{w}) = \sum_{i=1}^{k} \vec{z}_i \cdot\vec{w}, \qquad\text{subject to } g(\vec{w}) = \lVert\vec{w}\rVert^{2} = 1. \tag*{(1)} w argmax f ( w ) = i = 1 ∑ k z i ⋅ w , subject to g ( w ) = ∥ w ∥ 2 = 1. (1)
The function f ( w ⃗ ) f(\vec{w}) f ( w ) is proportional to the mean (signed) distance to the hyperplane, and the constraint normalizes the sum so that it cannot be arbitrarily large. By the method of Lagrange multipliers, the solution to our optimization problem is w ⃗ = ∑ i z ⃗ i / ∥ ∑ i z ⃗ i ∥ \vec{w} = \sum_i \vec{z}_i / \lVert\sum_i \vec{z}_i \rVert w = ∑ i z i / ∥ ∑ i z i ∥ .
Boundary score: The boundary score s ( x ) ∈ [ 0 , 1 ] s(x) \in[0,1] s ( x ) ∈ [ 0 , 1 ] for point x x x is the percentage of neighboring points that lie on the positive side of the hyperplane. Boundary and interior points have scores close to 1 1 1 and .5 .5 .5 , respectively.
As an alternative to our hyperplane optimization step, one could instead aim to maximize the number of points such that z ⃗ i ⋅ w ⃗ ≥ 0 \vec{z}_i \cdot\vec{w} \ge0 z i ⋅ w ≥ 0 . In contrast, maximizing f ( w ⃗ ) f(\vec{w}) f ( w ) encourages but does not force points to lie on the positive hyperplane side. The advantage of our formulation is that it has a fast, closed-form solution. Algorithm 1 runs in about 1s for N = 10 , 000 N = 10,000 N = 10 , 000 points in R 15 \mathbb{R}^{15} R 15 .
Algorithm 1 Boundary Detection
Input: Point cloud X \mathcal{X} X , neighborhood size k k k , PCA spectral gap threshold τ \tau τ (default τ = 7 \tau= 7 τ = 7 ) Output: Boundary score s ( x ) ∈ [ 0 , 1 ] s(x) \in[0,1] s ( x ) ∈ [ 0 , 1 ] for each x ∈ X x \in\mathcal{X} x ∈ X
for all x ∈ X x \in\mathcal{X} x ∈ X do
N ← k \mathcal{N} \leftarrow k N ← k -nearest neighbors of x x x in X \mathcal{X} X
{ z i } ← PCA ( N , τ ) \{z_i\} \leftarrow\operatorname{PCA}(\mathcal{N},\tau) { z i } ← PCA ( N , τ ) ▷ Use threshold τ \tau τ to determine dimension
{ z i } ← { z i − z } \{z_i\} \leftarrow\{z_i-z\} { z i } ← { z i − z } ▷ Center so projection of x x x is at origin
w ⃗ ← ∑ i z ⃗ i ∥ ∑ i z ⃗ i ∥ \vec{w} \leftarrow\dfrac{\sum_i \vec{z}_i}{\left\lVert\sum_i \vec{z}_i\right\rVert} w ← ∥ ∑ i z i ∥ ∑ i z i ▷ w ⃗ \vec{w} w is orthogonal to an optimal hyperplane
m ← ∣ { z i ∣ z ⃗ i ⋅ w ⃗ ≥ 0 } ∣ m \leftarrow\left|\{z_i \mid\vec{z}_i \cdot\vec{w} \ge0\}\right| m ← ∣ { z i ∣ z i ⋅ w ≥ 0 } ∣ ▷ Count neighbors on positive side of the hyperplane
s ( x ) ← m / k s(x) \leftarrow m/k s ( x ) ← m / k ▷ Divide by total size of the neighborhood
end for
return { s ( x ) } x ∈ X \{s(x)\}_{x\in\mathcal{X}} { s ( x ) } x ∈ X
To illustrate the hyperplane optimization step of the algorithm, we sample k k k points { z ⃗ i } \{\vec{z}_i\} { z i } from half or full n n n -dimensional balls and calculate w ⃗ \vec{w} w . See Figure 1 . For each experiment, we define the “accuracy” to be the percentage of points that lie on the positive side of the hyperplane determined by w ⃗ \vec{w} w —this is analogous to the boundary score defined previously. When the points are sampled from a half ball—which models the boundary-point case—the accuracy stays close to 1, even for the smallest neighborhood size that we tested (k = 10 k = 10 k = 10 ). By contrast, when the points are sampled from a full ball—which models the interior-point case—the accuracy is close to 1 / 2 1/2 1/2 . The gap between interior and boundary points persists as the dimension n n n increases to n = 10 n = 10 n = 10 . This is preliminary evidence that the optimized hyperplane reliably distinguishes between boundary and interior points.
Figure 1. Hyperplane optimization on points sampled from half and full balls. Accuracy is the percentage of points that lie on the positive side of the hyperplane orthogonal to w ⃗ \vec{w} w .
Concentration Inequalities for the Boundary Scores
The theorems below can be used to guide a choice of neighborhood size k k k given a manifold dimension n n n , or to pick a threshold on the boundary scores for identifying boundary points. Our goal is to quantify the distribution of boundary scores s ( x ) s(x) s ( x ) when x x x is either an interior point or a boundary point. To do so, we consider the random variable
S n k : = ∑ i = 1 k 1 w ⃗ ⋅ z ⃗ i ≥ 0 , (2) S_{nk} := \sum_{i=1}^{k} \mathbf{1}_{\vec{w}\cdot\vec{z}_i\geq0}, \tag*{(2)} S nk := i = 1 ∑ k 1 w ⋅ z i ≥ 0 , (2)
which counts the number of points that lie on the positive side of the hyperplane determined by w ⃗ \vec{w} w . In our theoretical results below, we assume that the points { z ⃗ i } i = 1 k \{\vec{z}_i\}_{i=1}^{k} { z i } i = 1 k are drawn uniformly at random from either an n n n -dimensional ball (to model the situation where x x x is an interior point) or an n n n -dimensional half ball (to model the situation where x x x is a boundary point). The boundary score s ( x ) s(x) s ( x ) behaves similarly to 1 k S n k \frac{1}{k}S_{nk} k 1 S nk , and we are interested in its probability distribution. The challenge is that the terms in the sum S n k S_{nk} S nk are generally not independent because w ⃗ \vec{w} w depends on all z ⃗ i \vec{z}_i z i , so S n k S_{nk} S nk is not a binomial random variable. Below, we prove that boundary scores for boundary and interior points concentrate near 1 and 1 / 2 1/2 1/2 , respectively.
Theorem 2.1. Let { z ⃗ i } i = 1 k \{\vec{z}_i\}_{i=1}^{k} { z i } i = 1 k be points sampled independently and uniformly at random from an n n n -dimensional ball. Then there are constants C 1 , C 2 C_1,C_2 C 1 , C 2 such that for any ϵ > 0 \epsilon> 0 ϵ > 0 , we have
P [ ∣ S n k / k − 1 / 2 ∣ > ϵ ] ≤ ϵ − 2 ( C 1 n / k + C 2 n / k ) \mathbb{P}\left[\left|S_{nk}/k-1/2\right|>\epsilon\right]\leq\epsilon^{-2}\left(C_1\sqrt{n/k}+C_2n/k\right) P [ ∣ S nk / k − 1/2 ∣ > ϵ ] ≤ ϵ − 2 ( C 1 n / k + C 2 n / k ) for all dimensions n n n and all k ≥ 3 k \geq3 k ≥ 3 .
Theorem 2.2. Let { z ⃗ i } i = 1 k \{\vec{z}_i\}_{i=1}^{k} { z i } i = 1 k be points sampled independently and uniformly at random from an n n n -dimensional half ball. For any ϵ > 0 \epsilon> 0 ϵ > 0 , we have
P [ 1 − S n k / k ≥ ϵ ] ≤ 3 4 3 n + 1 ϵ k 3 . \mathbb{P}\left[1-S_{nk}/k\geq\epsilon\right]\leq\frac{3}{\sqrt[3]{4}}\frac{n+1}{\epsilon\sqrt[3]{k}}. P [ 1 − S nk / k ≥ ϵ ] ≤ 3 4 3 ϵ 3 k n + 1 .
Directional Uniformity Method for Boundary Detection
Our directional uniformity (DU) method is related to the Rayleigh uniformity test for deciding whether a spherical sample is uniform or not [13 ] . Suppose that for each point x x x , we consider a local neighborhood { x i j } \{x_{ij}\} { x ij } of size k k k . We project each neighbor onto a sphere centered at x x x and calculate the vector v ⃗ i : = 1 k 3 ∑ j ( x j − x i ) / ∥ x j − x i ∥ \vec{v}_i := \frac{1}{k^3}\sum_j (x_j-x_i)/\lVert x_j-x_i\rVert v i := k 3 1 ∑ j ( x j − x i ) / ∥ x j − x i ∥ . If x x x is a manifold point, then the neighbors are uniformly distributed on the sphere, so E [ v ⃗ i ] = 0 \mathbb{E}[\vec{v}_i]=0 E [ v i ] = 0 . If x x x is a boundary point, then E [ v ⃗ i ] \mathbb{E}[\vec{v}_i] E [ v i ] is nonzero and parallel to the boundary normal. We define the boundary score
s ( x ) : = 1 k 3 ∑ j v ⃗ i ⋅ v ⃗ j . (3) s(x) := \frac{1}{k^3}\sum_j \vec{v}_i\cdot\vec{v}_j. \tag*{(3)} s ( x ) := k 3 1 j ∑ v i ⋅ v j . (3)
Note that expected boundary point scores are strictly less than 1 and depend on dimension n n n .
Algorithm 2 Directional-Uniformity (DU) Boundary Detection
Input: Point cloud X \mathcal{X} X , neighborhood size k k k Output: Boundary score s ( x ) ∈ [ 0 , 1 ] s(x)\in[0,1] s ( x ) ∈ [ 0 , 1 ] for each x ∈ X x\in\mathcal{X} x ∈ X
for all x ∈ X x\in\mathcal{X} x ∈ X do
N ← k \mathcal{N}\leftarrow k N ← k -nearest neighbors of x x x in X \mathcal{X} X
v ⃗ i ← ∑ j ∈ N x j − x i ∥ x j − x i ∥ \vec{v}_i\leftarrow\sum_{j\in\mathcal{N}}\frac{x_j-x_i}{\lVert x_j-x_i\rVert} v i ← ∑ j ∈ N ∥ x j − x i ∥ x j − x i
s ( x ) ← 1 k 3 ∑ j v ⃗ i ⋅ v ⃗ j s(x)\leftarrow\frac{1}{k^3}\sum_j\vec{v}_i\cdot\vec{v}_j s ( x ) ← k 3 1 ∑ j v i ⋅ v j
end for
return { s ( x ) } x ∈ X \{s(x)\}_{x\in\mathcal{X}} { s ( x ) } x ∈ X
Robustness-to-noise is the main advantage of (3) instead of simply ∥ v ⃗ i ∥ \lVert\vec{v}_i\rVert ∥ v i ∥ . The former equation measures the alignment of v ⃗ i \vec{v}_i v i with its neighbors v ⃗ j \vec{v}_j v j . Although there is always correlation between v ⃗ i \vec{v}_i v i and v ⃗ j \vec{v}_j v j due to the overlap in neighborhoods, there is stronger alignment when x x x is a boundary point because E [ v ⃗ i ] \mathbb{E}[\vec{v}_i] E [ v i ] is nonzero.
More importantly, ambient noise can thicken an n n n -dimensional manifold into a higher-dimensional object, and it is challenging for boundary detection methods to distinguish between the boundary of the ground-truth n n n -dimensional manifold and the boundary of the higher-dimensional object; Equation (3) helps to mitigate that. For example, in Figure 2 , a 1D horizontal line segment in R 2 \mathbb{R}^2 R 2 has noise added so that it is a thin 2D subset. A point x i x_i x i at the top (or bottom) of the subset has a neighborhood that is genuinely a half ball, so ∥ v ⃗ i ∥ \lVert\vec{v}_i\rVert ∥ v i ∥ is as large as it is for a “true” boundary point. However, because it is a thin 2D strip, the points x j x_j x j at the bottom of the neighborhood are boundary points on the opposite side. For points x j x_j x j at the top and bottom, the vectors v ⃗ j \vec{v}_j v j point down and up, respectively. Therefore, there are cancellations in Equation (3) so that it is small, even though most of the vectors v ⃗ j \vec{v}_j v j are large. This correctly signifies that the point x i x_i x i is not on the true boundary (the left and right endpoints of the line segment). For comparison, the right panel of Figure 2 shows { v ⃗ j } \{\vec{v}_j\} { v j } for points x j x_j x j in a neighborhood of a point x i x_i x i on the boundary of a half plane. The norm v ⃗ i \vec{v}_i v i is close to that of the point on the line segment, but ∑ j v ⃗ i ⋅ v ⃗ j \sum_j\vec{v}_i\cdot\vec{v}_j ∑ j v i ⋅ v j is larger. At a fixed neighborhood size and high noise level, Equation (3) is less likely than ∥ v ⃗ i ∥ \lVert\vec{v}_i\rVert ∥ v i ∥ to flag interior points as boundary points.
Figure 2. The vectors v ⃗ j \vec{v}_j v j for points { x i j } \{x_{ij}\} { x ij } (orange) in a local neighborhood of a point x i x_i x i (red) within a larger point cloud that is sampled from (left) a thin strip in R 2 \mathbb{R}^2 R 2 with noise and (right) a half plane.
Boundary Detection on Synthetic Data
Non-uniform density. Many methods in the literature erroneously detect low-density interior points as boundary points. To test this, we sample points non-uniformly from a 2D disk where there is a low-density region in the interior. For each method, we calculate AUC values (shown in Table 1 ) for boundary points vs. deep interior points (the low-density region).2 See Figure 12 for the pointwise scores. RU (Li et al., [11 ] ), BORDER (Xia et al., 2006), and BP (Averbuch-Elor et al., [2 ] ; Du et al., [6 ] ) explicitly rely on the idea that boundary points have lower density, so it is unsurprising that they have AUC values below .5. The CO method (Wang et al., 2018) performs similarly poorly (AUC .447) because of a “mass” term that increases the score at low-density points. The only methods that perform well on the non-uniform-density data set are LoDD, BEPS, our HP method, and our DU method, which all have AUC = 1.
Table 1. Boundary (∥ x ∥ > .98 \lVert x\rVert> .98 ∥ x ∥ > .98 ) vs deep-interior (∥ x ∥ < .23 \lVert x\rVert< .23 ∥ x ∥ < .23 ) AUC for N = 10,000 N = 10{,}000 N = 10 , 000 points sampled non-uniformly from a 2D disk. In the interior, there is a “well” (r < .23 r < .23 r < .23 ) where the density is 1/9 that of the density in the outer region (r > .67 r > .67 r > .67 ). The density increases linearly in between.
Figure 12. We sample N = 10 , 000 N = 10,000 N = 10 , 000 points non-uniformly from a 2D disk. In the interior, there is a “well” (r < .23 r < .23 r < .23 ) where the density is 1/9 that of the density in the outer region (r > .67 r > .67 r > .67 ). The density increases linearly in between. For each method, we calculate the AUC value for boundary points (∥ x ∥ > .98 \lVert x \rVert> .98 ∥ x ∥ > .98 ) vs. interior well points (∥ x ∥ < .23 \lVert x \rVert< .23 ∥ x ∥ < .23 ), using neighborhood size k = 100 k = 100 k = 100 . In the top row, we show the methods that are able to handle non-uniform density. In the bottom row, we show the methods that confuse boundary points and low-density interior points.
Surfaces with non-trivial geometry. For the remainder of Section 4, our primary focus is comparing LoDD (Peng et al., 2025) and BEPS (Li & Maguire, [12 ] ) with our HP and DU methods. We test the four methods on six synthetic data sets with low levels of Gaussian noise; see Figure 3 for the cone and saddle-skewer, and Figure 13 for four more. BEPS performs reasonably well, but it has a high number of false positives (interior points that score as high as boundary points) on three of the surfaces (the cone, Saturn, and the three disks). LoDD struggles with data points that have intrinsic dimension one, such as the skewer in the saddle-skewer. The interior 1D points have LoDD scores that are as low as points near the surface boundaries. (LoDD scores are close to 0 on boundary points and higher on the interior, unlike the other three methods.) HP scores boundary points close to 1, while manifold points have low boundary scores close to .5. Points near (but not on) a transverse intersection of two surfaces have moderate hyperplane boundary scores near .75. Similarly, DU scores are higher at boundary points and lower (close to 0) at interior points. This data set shows that all four methods are reasonably accurate on surfaces with complex topologies and curvature, except that LoDD confuses interior 1D points with boundary points and BEPS is prone to false positives, sometimes confusing isolated interior points for boundary points.
Figure 3. Boundary scores (k = 100 k = 100 k = 100 ) for two synthetic data sets (N = 10 4 N = 10^{4} N = 1 0 4 ) with low noise levels.
Figure 13. Boundary scores for four synthetic data sets with low noise levels. Each point cloud has N = 10,000 N = 10{,}000 N = 10 , 000 points, and we use neighborhood size k = 100 k = 100 k = 100 .
High ambient dimension. In high ambient dimension with low noise, BEPS cannot distinguish between boundary points and interior points, and LoDD scores have high variance on interior points. For example, see Figure 4 . BEPS scores are roughly constant across all points, and many interior points have LoDD scores that are as low as boundary-point LoDD scores. In contrast, our HP and DU methods both highlight a clear boundary, scoring interior points much lower, although HP has a small amount of interior noise. A limitation of HP in high ambient dimensions is that it scores selfintersections as high as boundary points. (In lower ambient dimensions, HP assigns score ≈ .75 < 1 \approx.75 < 1 ≈ .75 < 1 to points near intersections.) For the remainder of this subsection, we focus on HP, DU, and LoDD.
Figure 4. Boundary scores (N = 10,000 N = 10{,}000 N = 10 , 000 , k = 100 k = 100 k = 100 ) on the Henneberg minimal surface embedded in R 15 \mathbb{R}^{15} R 15 with isotropic Gaussian noise (σ = .02 \sigma= .02 σ = .02 ), plotted in R 3 \mathbb{R}^{3} R 3 .
Next, we study 2D disks embedded in R D \mathbb{R}^{D} R D (3 ≤ D ≤ 15 3 \le D \le15 3 ≤ D ≤ 15 ) with isotropic Gaussian noise (σ = .01 \sigma= .01 σ = .01 ). In Figure 5 (a), we calculate AUC values for interior vs. boundary points3 . Both the hyperplane and DU methods have AUC values near 1 at all D D D , while LoDD’s performance degrades as D D D increases. That is, HP and DU perform better than LoDD on point clouds with high ambient dimension.
Figure 5. Analysis of boundary scores on disks embedded in R D \mathbb{R}^{D} R D with Gaussian noise σ = .01 \sigma= .01 σ = .01 (size N = 10,000 N = 10{,}000 N = 10 , 000 points, with k = 100 k = 100 k = 100 ).
For each method (excluding BEPS), we measure the strength of the relationship between a point’s norm and its boundary score. A good method should score all interior points at an approximately constant value and then monotonically change as one approaches the boundary. For each method we fit a monotonic function f ( r ) f(r) f ( r ) to the scores as a function of radius r r r and calculate the coefficient of determination R 2 R^{2} R 2 . Figure 5 (b) shows that the DU method has the highest R 2 R^{2} R 2 value (near 1) at each D D D , while LoDD has the lowest values, reflecting its high variance within the interior of the disk.
High noise levels. At higher levels of noise, local PCA may overestimate the local dimension. This affects HP. If the estimated dimension m m m is larger than the true manifold dimension n n n , then HP will
Figure 20. Point clouds are sampled from 2D disks embedded in R D \mathbb{R}^{D} R D for D = 3 , 5 , 8 , 10 , 12 , 15 D = 3, 5, 8, 10, 12, 15 D = 3 , 5 , 8 , 10 , 12 , 15 with Gaussian noise level σ = .01 \sigma= .01 σ = .01 . Each point cloud has N = 10 , 000 N = 10,000 N = 10 , 000 points, and we use neighborhood size k = 100 k = 100 k = 100 . Interior points are defined to be points with norm less than .8 .8 .8 , and boundary points are defined to be points with norm larger than τ B \tau_B τ B , which increases from τ B = .91 \tau_B = .91 τ B = .91 to τ B = .98 \tau_B = .98 τ B = .98 across the panels. In each panel, we plot the AUC values as a function of ambient dimension D D D for each of the three methods.
find the boundary of it as an m m m -dimensional object rather than an n n n -dimensional object. In Figure 6 , we show an example where a point cloud (N = 2,500 N = 2{,}500 N = 2 , 500 ) is sampled from two intersecting orthogonal line segments with Gaussian noise σ = .025 \sigma= .025 σ = .025 . At this noise level, with default neighborhood size k = 100 k = 100 k = 100 , local PCA over-estimates the intrinsic dimension—99.1% of points are assigned local dimension 2. HP thus detects the edges of the thickened arms as boundary points, because this is the boundary when the object is treated as 2-dimensional. Increasing the neighborhood size to k = 200 k = 200 k = 200 resolves the issue because at the larger neighborhood size, local PCA correctly estimates dimension 1 at most points except near the intersection. Interestingly, LoDD and BEPS suffer from the same limitation, but increasing the neighborhood size does not help them. DU is able to correctly identify true boundary points at both neighborhood sizes.
In Figure 7 , we study each method’s boundary-detection performance as we increase the noise level σ \sigma σ . The point clouds are sampled from 2D disks embedded in R 3 \mathbb{R}^{3} R 3 with isotropic Gaussian noise. Again, we see that at higher noise levels, HP often misclassifies interior points as boundary points because local PCA overestimates the dimension as 3 instead of 2. An interior point with high ∣ z ∣ |z| ∣ z ∣ coordinate is seen as the “boundary” of the thickened disk. However, if we fix dimension 2 for the local PCA dimension, then HP is able to correctly recover the disk boundary. We plot the AUC values as a function of σ \sigma σ in Figure 7 (a). At the highest noise level (σ = .05 \sigma= .05 σ = .05 ), HP with fixed dimension (AUC .969) performs best, followed by DU (AUC .932), then LoDD (AUC .868), and then finally BEPS (AUC .818) and HP with the spectral-gap threshold condition (AUC .816). In the high-noise experiments, BEPS and HP (spectral gap threshold) are almost identical because both methods optimize for a hyperplane (in different ways) that maximizes the number of points on a single side of the hyperplane. When the local dimension is overestimated, HP suffers from the same limitations as BEPS. We see the same behavior when the 2D disk is embedded in higher-dimensional R D \mathbb{R}^{D} R D with noise level σ = .05 \sigma= .05 σ = .05 , in Figure 7 (b). See Figure 16 for scatter plots of the boundary scores at D = 3 D = 3 D = 3 and σ = .05 \sigma= .05 σ = .05 . This suggests that HP should be used if the intrinsic dimension can be reliably estimated, but otherwise, it is best to use DU.
Figure 7. Boundary scores at high noise, for 2D disks (N = 10,000 N = 10{,}000 N = 10 , 000 ) embedded in R D \mathbb{R}^{D} R D with Gaussian noise σ \sigma σ . We use neighborhood size k = 100 k = 100 k = 100 . Boundary and interior points are defined as points with norm > .95 > .95 > .95 and < .8 < .8 < .8 , respectively, with norm computed in the x y xy x y plane.
Figure 16. Boundary scores for 2D disks embedded in R 3 \mathbb{R}^3 R 3 with isotropic Gaussian noise σ = .05 \sigma= .05 σ = .05 , projected here to R 2 \mathbb{R}^2 R 2 .
High intrinsic dimension. All methods (hyperplane, DU, LoDD, and BEPS) are able to detect the boundary of an n n n -dimensional object. We sample N = 10,000 N = 10{,}000 N = 10 , 000 points from n n n -balls embedded in R n \mathbb{R}^{n} R n for n = 3 , 5 , 7 , 10 n = 3, 5, 7, 10 n = 3 , 5 , 7 , 10 . For each method, the AUC value is 1 for each n n n , where boundary and interior points are points with norm > .95 > .95 > .95 and < .8 < .8 < .8 , respectively. See Figure 17 for boundary scores.
Figure 17. Boundary scores on a point cloud with N = 10 , 000 N = 10,000 N = 10 , 000 points sampled from a 10-dimensional ball in R 10 \mathbb{R}^{10} R 10 , with isotropic Gaussian noise (σ = .01 \sigma= .01 σ = .01 ). The ground-truth boundary is difficult to display in 2D because it is 9-dimensional, so instead we take a thin 2D slice (a slightly thickened disk) the ball, plotting the 1500 points closest to the x y xy x y plane. Because of the curvature of the boundary (a sphere), the boundary appears thicker than the 2D balls in earlier figures, but this is an artifact of the way we are taking a slice and projecting to R 2 \mathbb{R}^2 R 2 .
Boundary normals. Both of our boundary detection methods yield normal directions at each point, in addition to numerical scores. For HP, we take the vector w ⃗ \vec{w} w (line 5 of Algorithm 1) and lift it from its PCA coordinates back into the ambient space to get a normal w ⃗ a m b \vec{w}_{\mathrm{amb}} w amb . For DU, the vector v ⃗ i : = 1 k ∑ j ( x i j − x i ) / ∥ x i j − x i ∥ \vec{v}_i := \frac{1}{k}\sum_j (x_{ij}-x_i)/\lVert x_{ij}-x_i\rVert v i := k 1 ∑ j ( x ij − x i ) / ∥ x ij − x i ∥ is the same as the vector used by BEPS [12 ] and CO (Wang et al., 2018). In Figure 8 , we test the accuracy of these vectors on 2D disks and n n n -balls. For 2D disks in R 3 \mathbb{R}^3 R 3 , HP generally yields a more accurate normal direction estimate than DU, with the performance gap narrowing as the noise σ \sigma σ increases. For HP, fixing the dimension 2 works better than using a spectral gap threshold condition at lower noise levels (σ ≤ .05 \sigma\le.05 σ ≤ .05 ), but at the highest noise level (σ = .1 \sigma= .1 σ = .1 ), the top two local principal components do not align as well with the tangent space. For 2D disks in R D \mathbb{R}^D R D , the hyperplane normal w ⃗ a m b \vec{w}_{\mathrm{amb}} w amb is significantly more accurate than v ⃗ i \vec{v}_i v i as D D D increases. For n n n -balls, both methods (and variants) are equally accurate; we suspect that this is usually true for manifolds with codimension zero. Overall, HP generally yields a much more accurate boundary normal direction compared to DU.
Figure 8. For points x x x near the boundary of a 2D disk or n n n -ball (∥ x ∥ > .95 \lVert x\rVert> .95 ∥ x ∥ > .95 ), we compare the estimated boundary normal with the ground-truth normal − x / ∥ x ∥ -x/\lVert x\rVert − x / ∥ x ∥ . We plot median error and IQR.
Boundary Detection in Spatial Transcriptomics Data
As a first application, we apply our methods to spatial transcriptomics data, which measures gene expression across a tissue section, to recover cell-state boundaries in glioblastoma. Glioblastoma is an aggressive brain tumor that diffusely infiltrates the brain, making it difficult to distinguish regions where tumor cells are abundant or sparse. Malignant cells also occupy distinct transcriptional states (Neftel et al., 2019) that may be amenable to different therapies, further motivating the identification of boundaries within the tumor. We analyze tissue slice ST1A1 from Al-Dalahmah et al. [1 ] .
Each capture area measures the combined expression of multiple cells. To interpret our boundary scores, we use published cell-state abundance estimates obtained by Robust Cell Type Decomposition (RCTD) [4 ] , which deconvolves this expression into contributions from different cell states. Following Al-Dalahmah et al. [1 ] , we combine the malignant-cell subpopulations gl_Mes1 and gl_Mes2 into an astrocyte-like/mesenchymal group (Mes), and gl_Pro1 and gl_Pro2 into a proliferative group (Pro). These represent distinct malignant states that have prognostic and therapeutic implications. Figure 9 shows their spatial distributions and the mesenchymal/proliferative contrast, calculated as Mes minus Pro.
Figure 9. Glioblastoma slice ST1A1.
In Figure 9 , both HP and DU assign higher boundary scores along the tissue edge and near parts of the transition between Mes- and Pro-enriched regions. After pre-processing (see Section C.3), we reduce gene expression to 30 principal components and concatenate these with the two spatial coordinates, yielding a point cloud of size N = 741 N = 741 N = 741 (the number of spatial spots) in R 32 \mathbb{R}^{32} R 32 . We view this as the graph of an expression function over spatial coordinates, motivating fixed dimension two for HP. For both methods, we construct each spot’s neighborhood by taking the intersection of nearest neighbors with respect to both spatial coordinates and gene expression coordinates. Our results suggest that our methods can detect internal transitions between tumor states without using cell-state labels or predefined tumor-marker genes.
LLM Activation Geometry
As as second application, we reproduce the character-counting manifold of Gurnee et al. [10 ] on two open-weight models (Pythia-2.8B and Llama-3.1-8B) and apply our boundary-detection methods. Using text from the C4 (English) data set (Raffel et al., 2020), we strip newlines and then re-insert them every k k k characters, rounded to the nearest word boundary, for k ∈ { 15 , 20 , … , 150 } k \in\{15,20,\ldots,150\} k ∈ { 15 , 20 , … , 150 } . This produces 28 versions of each document, each with fixed line width w w w . Every non-newline token has a character position i i i within its line of width w w w . We extract the layer-4 residual-stream activations and average the activations for each ( i , w ) (i,w) ( i , w ) , yielding point clouds of size N ≈ 2,300 N \approx2{,}300 N ≈ 2 , 300 for each model. Figure 10 shows the Pythia-2.8B point cloud; see Figure 19 for Llama-3.1-8B. See Section C.4 for details of our procedure.
Figure 10. Boundary detection on the character-counting manifold for Pythia-2.8B.
Figure 19. Boundary detection on the character-counting manifold for Llama-3.1-8B. In (c), we calculate normal vectors only for the top 10% scoring boundary points.
In Figure 10 (b), both of our boundary detectors correctly assign higher scores to the ground-truth boundary of the averaged manifold, which is { ( i , w ) ∣ i = 0 or i = w or w = 15 or w = 150 } \{(i,w) \mid i=0 \text{ or } i=w \text{ or } w=15 \text{ or } w=150\} {( i , w ) ∣ i = 0 or i = w or w = 15 or w = 150 } . For HP, we use dimension n = 2 n=2 n = 2 because the surface is intrinsically parameterized by character position i i i and line width w w w . We also show the vector fields of estimated boundary normals in Figure 10 (c) for the top 10% scoring points; the vectors tend to point inwards on the surface, as they should.
Lastly, we test HP and DU on the un-averaged, per-token point cloud (size N ≈ 250 k N \approx250\mathrm{k} N ≈ 250 k per model). See Figure 10 (d). This is much more challenging because the intrinsic dimension of the space is much higher (and unknown), and there are other, unknown boundaries in the token point cloud. After calculating boundary scores at each point, we average the boundary scores for the tokens at each ( i , w ) (i,w) ( i , w ) . The averaged boundary scores are consistently higher at the ground-truth boundary.
Conclusions
We presented two new methods for identifying boundary points and calculating boundary normal vectors in high-dimensional, noisy data. We justified the hyperplane method mathematically, and we rigorously tested both methods empirically against others in the literature on synthetic data. Finally, we showed that our boundary detection methods are effective on real-world applications by using them to identify a tumor boundary in a spatial transcriptomics data set and to characterize the boundary of a manifold in LLM activations.
AI Use Statement
We used generative AI to write almost all of the code and to assist with isolated steps within the proofs of Lemma B.3 , Lemma B.4 , Lemma B.5 , and Lemma B.6 .
We have reviewed all AI-assisted work. In particular, we have reviewed the code and checked all mathematical arguments for correctness. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI.
Acknowledgments
Hickok was supported by NSF grant DMS-2303402. Al Dalahmah was partially supported by NIH grant 1R21NS136647 NINDS. Blumberg was partially supported by NSF grants DMS-2311338 and IIS-2552120.
Additional Experimental Figures
Hyperplane optimization in half and full balls
To illustrate the intuition for HP, we calculate the vector w ⃗ \vec{w} w , the solution to Equation (1) , for points sampled from 2D and 3D balls and half balls. In Figure 1 (a), we showed w ⃗ \vec{w} w and its orthogonal hyperplane (line) for k = 10 k = 10 k = 10 points sampled from a 2D half ball. In Figure 11 , we show w ⃗ \vec{w} w and its orthogonal hyperplane for k = 50 k = 50 k = 50 points in 2D half and full balls and for k = 100 k = 100 k = 100 points in 3D half and full balls. In all cases, the “accuracy” (the percentage of points z ⃗ \vec{z} z such that w ⃗ ⋅ z ⃗ ≥ 0 \vec{w} \cdot\vec{z} \ge0 w ⋅ z ≥ 0 ) is close to 1 for the half balls and close to .5 for the full balls.
Figure 11. We calculate the vector w ⃗ \vec{w} w that is the solution to Equation (1) in our hyperplane method, where the accuracy of w ⃗ \vec{w} w is the percentage of points { z i } \{z_i\} { z i } such that w ⃗ ⋅ z ⃗ i ≥ 0 \vec{w} \cdot\vec{z}_i \ge0 w ⋅ z i ≥ 0 . (A) 2D half ball with normal ( 1 , 0 ) (1,0) ( 1 , 0 ) and k = 50 k = 50 k = 50 points, with accuracy .98, (B) 2D full ball with k = 50 k = 50 k = 50 and accuracy .5, (C) 3D half ball with normal ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) and k = 100 k = 100 k = 100 , with accuracy .99, and (D) 3D full ball with k = 100 k = 100 k = 100 and accuracy .6.
In Section 4, we tested boundary detection methods on a 2D disk with non-uniform density and reported AUC values in Table 1 . In Figure 12 , we show scatter plots of the pointwise boundary scores for each method.
Surfaces with non-trivial geometry
In Section 4, we calculated boundary scores for the hyperplane method, DU, LoDD, and BEPS on a cone and a saddle-skewer data set with low noise levels. In Figure 13 below, we show the boundary scores for four more synthetic data sets.
High ambient dimension
In Section 4, we calculated boundary scores for the hyperplane method, DU, LoDD, and BEPS for surfaces in high ambient dimension with Gaussian noise. Figure 4 showed the Henneberg minimal
surface in R 15 \mathbb{R}^{15} R 15 and Figure 5 analyzed the boundary scores for disks in R D \mathbb{R}^{D} R D . In Figure 14 , we show the boundary scores for three more surfaces in R 15 \mathbb{R}^{15} R 15 , and in Figure 15 , we show the boundary scores for 2D disks in R 15 \mathbb{R}^{15} R 15 with noise.
Figure 14. Boundary scores for three synthetic data sets embedded in R 15 \mathbb{R}^{15} R 15 with noise. Scores here are plotted in R 3 \mathbb{R}^{3} R 3 .
Figure 15. Boundary scores on disks embedded in R 15 \mathbb{R}^{15} R 15 with Gaussian noise σ = .01 \sigma= .01 σ = .01 , with N = 10,000 N = 10{,}000 N = 10 , 000 points. We use neighborhood size k = 100 k = 100 k = 100 . We plot only the first two coordinates.
High noise levels
In Section 4, we tested our hyperplane and DU methods against LoDD and BEPS on 2D disks embedded in R D \mathbb{R}^{D} R D with increasing noise level σ \sigma σ . In Figure 16 , we show the boundary scores for disks in R 3 \mathbb{R}^{3} R 3 at the highest noise level σ = .05 \sigma= .05 σ = .05 .
High intrinsic dimension
In Figure 17 , we show the boundary scores for points sampled from a 10-dimensional ball in R 10 \mathbb{R}^{10} R 10 . All methods achieve AUC 1 except for reverse unreachability (AUC .01). For the AUC calculation, we define boundary and interior points as points with norm > .95 > .95 > .95 and .8 .8 .8 , respectively.
Spatial transcriptomics
In § 5 , we analyzed glioblastoma slice ST1A1 from [1 ] . In Figure 9 , we showed HP and DU scores at neighborhood sizes k = 150 k = 150 k = 150 and k = 100 k = 100 k = 100 , respectively. In Figure 18 below, we show the boundary scores at neighborhood sizes k = 75 , 100 , 150 k = 75, 100, 150 k = 75 , 100 , 150 for each method.
Figure 18. HP and DU boundary scores on the ST1A1 glioblastoma slice at neighborhood sizes k = 75 k = 75 k = 75 , 100 100 100 , 150 150 150 .
Llama-3.1-8B activation geometry
We reproduce the character-counting manifold of [10 ] for Llama-3.1-8B using the methodology in Section C.4. In Figure 19 , we show the averaged manifold and our detected boundaries. We also show the average boundary scores at each character position i i i and line width w w w when we compute boundary scores for the un-averaged, per-token point cloud. See Figure 10 for Pythia-2.8B.
Mathematical proofs
Proof of theorem 2.1 for interior manifold points
Suppose that { z ⃗ i } i = 1 k \{\vec{z}_i\}_{i=1}^k { z i } i = 1 k are sampled independently and uniformly at random from an n n n -dimensional ball. Let w ⃗ = ∑ i z ⃗ i ∥ ∑ i z ⃗ i ∥ \vec{w} = \frac{\sum_i \vec{z}_i}{\lVert\sum_i \vec{z}_i\rVert} w = ∥ ∑ i z i ∥ ∑ i z i and let S n k S_{nk} S nk be defined as in Equation (2) . Define
X i : = 1 w ⃗ ⋅ z ⃗ i ≥ 0 , Q n k : = P [ w ⃗ ⋅ z ⃗ 1 ≥ 0 ] . X_i := \mathbf{1}_{\vec{w}\cdot\vec{z}_i\geq0}, \qquad
Q_{nk} := \mathbb{P}[\vec{w}\cdot\vec{z}_1\geq0]. X i := 1 w ⋅ z i ≥ 0 , Q nk := P [ w ⋅ z 1 ≥ 0 ] .
Proof of Theorem 2.1. By Chebyschev’s inequality,
P [ ∣ S n k / k − 1 2 ∣ > ϵ ] ≤ var ( S n k ) k 2 ϵ 2 = Q n k ( 1 − Q n k ) k ϵ 2 + cov ( X 1 , X 2 ) ϵ 2 . \mathbb{P}\left[\left|S_{nk}/k-\frac{1}{2}\right|>\epsilon\right]\leq\frac{\operatorname{var}(S_{nk})}{k^2\epsilon^2}=\frac{Q_{nk}(1-Q_{nk})}{k\epsilon^2}+\frac{\operatorname{cov}(X_1,X_2)}{\epsilon^2}. P [ S nk / k − 2 1 > ϵ ] ≤ k 2 ϵ 2 var ( S nk ) = k ϵ 2 Q nk ( 1 − Q nk ) + ϵ 2 cov ( X 1 , X 2 ) .
The first summand is bounded above by k − 1 ϵ − 2 k^{-1}\epsilon^{-2} k − 1 ϵ − 2 because 0 ≤ Q n k ≤ 1 0\leq Q_{nk}\leq1 0 ≤ Q nk ≤ 1 . By Lemma B.6, there are constants C 1 , C 2 C_1,C_2 C 1 , C 2 such that ∣ cov ( X 1 , X 2 ) ∣ ≤ C 1 n k + C 2 n k \left|\operatorname{cov}(X_1,X_2)\right|\leq C_1\sqrt{\frac{n}{k}}+C_2\frac{n}{k} ∣ cov ( X 1 , X 2 ) ∣ ≤ C 1 k n + C 2 k n for all k ≥ 3 k\geq3 k ≥ 3 . Therefore,
P [ ∣ S n k / k − 1 2 ∣ > ϵ ] ≤ ϵ − 2 ( C 1 n k + ( 1 + C 2 ) n k ) . \mathbb{P}\left[\left|S_{nk}/k-\frac{1}{2}\right|>\epsilon\right]\leq\epsilon^{-2}\left(C_1\sqrt{\frac{n}{k}}+(1+C_2)\frac{n}{k}\right). P [ S nk / k − 2 1 > ϵ ] ≤ ϵ − 2 ( C 1 k n + ( 1 + C 2 ) k n ) .
Below, we prove Lemma B.6 and other supporting lemmas. First, we establish basic statistics about a point z ⃗ 1 \vec{z}_1 z 1 drawn uniformly at random from an n n n -dimensional ball. The mean is 0 ⃗ \vec{0} 0 by symmetry of the ball.
Lemma B.1. The covariance matrix for z ⃗ 1 \vec{z}_1 z 1 is 1 n + 2 I n \frac{1}{n+2}I_n n + 2 1 I n .
Proof. First, we note that E [ z 1 i 2 ] \mathbb{E}[z_{1i}^2] E [ z 1 i 2 ] is independent of i i i . Let r = ∥ z ⃗ 1 ∥ r=\lVert\vec{z}_1\rVert r = ∥ z 1 ∥ be the radial coordinate of z ⃗ 1 \vec{z}_1 z 1 . For any i i i , we have
n E [ z 1 i 2 ] = ∑ j = 1 n E [ z 1 j 2 ] = E [ r 2 ] = ∫ 0 1 r 2 ϕ ( r ) d r . n\mathbb{E}[z_{1i}^2]=\sum_{j=1}^{n}\mathbb{E}[z_{1j}^2]=\mathbb{E}[r^2]=\int_0^1 r^2\phi(r)\,dr. n E [ z 1 i 2 ] = j = 1 ∑ n E [ z 1 j 2 ] = E [ r 2 ] = ∫ 0 1 r 2 ϕ ( r ) d r .
where ϕ ( r ) \phi(r) ϕ ( r ) is the pdf for r r r in an n n n -dimensional ball. We have that ϕ ( r ) \phi(r) ϕ ( r ) is proportional to the volume of an ( n − 1 ) (n-1) ( n − 1 ) -dimensional sphere (not ball) of radius r r r , so ϕ ( r ) = A r n − 1 \phi(r)=Ar^{n-1} ϕ ( r ) = A r n − 1 for a constant A A A . Because ∫ 0 1 ϕ ( r ) d r = 1 \int_0^1\phi(r)\,dr=1 ∫ 0 1 ϕ ( r ) d r = 1 , we must have ϕ ( r ) = n r n − 1 \phi(r)=nr^{n-1} ϕ ( r ) = n r n − 1 . Therefore,
var ( z 1 i ) = E [ z 1 i 2 ] = 1 n ∫ 0 1 r 2 ϕ ( r ) d r = ∫ 0 1 r n + 1 d r = 1 n + 2 . \operatorname{var}(z_{1i})=\mathbb{E}[z_{1i}^2]=\frac{1}{n}\int_0^1r^2\phi(r)\,dr=\int_0^1r^{n+1}\,dr=\frac{1}{n+2}. var ( z 1 i ) = E [ z 1 i 2 ] = n 1 ∫ 0 1 r 2 ϕ ( r ) d r = ∫ 0 1 r n + 1 d r = n + 2 1 .
By symmetry of the ball,
E [ z 1 i z 1 j ] = E [ − z 1 i z 1 j ] = − E [ z 1 i z 1 j ] \mathbb{E}[z_{1i}z_{1j}]=\mathbb{E}[-z_{1i}z_{1j}]=-\mathbb{E}[z_{1i}z_{1j}] E [ z 1 i z 1 j ] = E [ − z 1 i z 1 j ] = − E [ z 1 i z 1 j ]
for i ≠ j i\ne j i = j , so cov ( z 1 i , z 1 j ) = E [ z 1 i z 1 j ] = 0 \operatorname{cov}(z_{1i},z_{1j})=\mathbb{E}[z_{1i}z_{1j}]=0 cov ( z 1 i , z 1 j ) = E [ z 1 i z 1 j ] = 0 .
We will use the following lemma in an application of the Berry-Esseen theorem to bound the probability Q n k Q_{nk} Q nk .
Lemma B.2. The third moment of z 1 i z_{1i} z 1 i is
E [ ∣ z 1 i ∣ 3 ] = 4 v n − 1 v n ( n + 3 ) ( n + 1 ) , \mathbb{E}[|z_{1i}|^3]=\frac{4v_{n-1}}{v_n(n+3)(n+1)}, E [ ∣ z 1 i ∣ 3 ] = v n ( n + 3 ) ( n + 1 ) 4 v n − 1 ,
where v n v_n v n is the volume of a unit n n n -dimensional ball.
Proof. The slice of the ball where z 1 i = t ∈ [ − 1 , 1 ] z_{1i}=t\in[-1,1] z 1 i = t ∈ [ − 1 , 1 ] is an ( n − 1 ) (n-1) ( n − 1 ) -dimensional ball of radius 1 − t 2 \sqrt{1-t^2} 1 − t 2 , which has volume v n − 1 ( 1 − t 2 ) n − 1 2 v_{n-1}(1-t^2)^{\frac{n-1}{2}} v n − 1 ( 1 − t 2 ) 2 n − 1 . Therefore, the pdf is
f ( t ) = A − 1 v n − 1 ( 1 − t 2 ) n − 1 2 , f(t)=A^{-1}v_{n-1}(1-t^2)^{\frac{n-1}{2}}, f ( t ) = A − 1 v n − 1 ( 1 − t 2 ) 2 n − 1 ,
where A = ∫ − 1 1 v n − 1 ( 1 − t 2 ) n − 1 2 = v n A=\int_{-1}^{1}v_{n-1}(1-t^2)^{\frac{n-1}{2}}=v_n A = ∫ − 1 1 v n − 1 ( 1 − t 2 ) 2 n − 1 = v n . The third moment is
E [ ∣ z 1 i ∣ 3 ] = 2 ∫ 0 1 z 1 i 3 f ( t ) d t = 2 v n − 1 v n ∫ 0 1 t 3 ( 1 − t 2 ) n − 1 2 d t . \mathbb{E}[|z_{1i}|^3]=2\int_0^1 z_{1i}^3f(t)dt=\frac{2v_{n-1}}{v_n}\int_0^1t^3(1-t^2)^{\frac{n-1}{2}}dt. E [ ∣ z 1 i ∣ 3 ] = 2 ∫ 0 1 z 1 i 3 f ( t ) d t = v n 2 v n − 1 ∫ 0 1 t 3 ( 1 − t 2 ) 2 n − 1 d t .
Substituting s = t 2 s=t^2 s = t 2 ,
E [ ∣ z 1 i ∣ 3 ] = v n − 1 v n B ( 2 , n + 1 2 ) = v n − 1 v n Γ ( 2 ) Γ ( n + 1 2 ) Γ ( 2 + n + 1 2 ) = v n − 1 v n Γ ( n + 1 2 ) n + 3 2 n + 1 2 Γ ( n + 1 2 ) = 4 v n − 1 v n ( n + 3 ) ( n + 1 ) . \mathbb{E}[|z_{1i}|^3]=\frac{v_{n-1}}{v_n}B\left(2,\frac{n+1}{2}\right)=\frac{v_{n-1}}{v_n}\frac{\Gamma(2)\Gamma\left(\frac{n+1}{2}\right)}{\Gamma\left(2+\frac{n+1}{2}\right)}=\frac{v_{n-1}}{v_n}\frac{\Gamma\left(\frac{n+1}{2}\right)}{\frac{n+3}{2}\frac{n+1}{2}\Gamma\left(\frac{n+1}{2}\right)}=\frac{4v_{n-1}}{v_n(n+3)(n+1)}. E [ ∣ z 1 i ∣ 3 ] = v n v n − 1 B ( 2 , 2 n + 1 ) = v n v n − 1 Γ ( 2 + 2 n + 1 ) Γ ( 2 ) Γ ( 2 n + 1 ) = v n v n − 1 2 n + 3 2 n + 1 Γ ( 2 n + 1 ) Γ ( 2 n + 1 ) = v n ( n + 3 ) ( n + 1 ) 4 v n − 1 .
Lemma B.3. For all dimensions n n n and neighborhood sizes k k k ,
1 2 ≤ Q n k ≤ 1 2 + 1 2 π n + 2 k − 1 + 8 C B E 2 π ( k − 1 ) . \frac{1}{2}\leq Q_{nk}\leq\frac{1}{2}+\frac{1}{\sqrt{2\pi}}\sqrt{\frac{n+2}{k-1}}+\frac{8C_{BE}}{\sqrt{2\pi(k-1)}}. 2 1 ≤ Q nk ≤ 2 1 + 2 π 1 k − 1 n + 2 + 2 π ( k − 1 ) 8 C B E . where C B E C_{BE} C B E is a universal constant from the Berry-Esseen theorem.
Proof. Note that
Q n k = P [ ∑ j > 1 z ⃗ j ⋅ z ⃗ 1 ≥ − ∥ z ⃗ 1 ∥ 2 ] . Q_{nk}=\mathbb{P}\left[\sum_{j>1}\vec{z}_j\cdot\vec{z}_1\geq-\left\|\vec{z}_1\right\|^2\right]. Q nk = P [ j > 1 ∑ z j ⋅ z 1 ≥ − ∥ z 1 ∥ 2 ] . Therefore,
Q n k ≥ P [ ∑ j > 1 z ⃗ j ⋅ z ⃗ 1 ≥ 0 ] = 1 2 . Q_{nk}\geq\mathbb{P}\left[\sum_{j>1}\vec{z}_j\cdot\vec{z}_1\geq0\right]=\frac{1}{2}. Q nk ≥ P [ j > 1 ∑ z j ⋅ z 1 ≥ 0 ] = 2 1 . because ∥ z ⃗ 1 ∥ 2 ≥ 0 \left\|\vec{z}_1\right\|^2\geq0 ∥ z 1 ∥ 2 ≥ 0 . The last equality holds because ∑ j > 1 z ⃗ j \sum_{j>1}\vec{z}_j ∑ j > 1 z j and z ⃗ 1 \vec{z}_1 z 1 are independent vectors in the n n n -ball that are equally likely to have angle θ ∈ [ 0 , π / 2 ] \theta\in[0,\pi/2] θ ∈ [ 0 , π /2 ] and angle π − θ ∈ [ π / 2 , π ] \pi-\theta\in[\pi/2,\pi] π − θ ∈ [ π /2 , π ] .
Next, we prove the upper bound on Q n k Q_{nk} Q nk . Conditioning on z ⃗ 1 = u ⃗ \vec{z}_1=\vec{u} z 1 = u , we have
Q n k = E z ⃗ 1 [ P [ ∑ j > 1 z ⃗ j ⋅ u ⃗ ≥ − ∥ u ⃗ ∥ 2 ∣ z ⃗ 1 = u ⃗ ] ] . (4) Q_{nk}=\mathbb{E}_{\vec{z}_1}\left[\mathbb{P}\left[\sum_{j>1}\vec{z}_j\cdot\vec{u}\geq-\|\vec{u}\|^2\mid\vec{z}_1=\vec{u}\right]\right]. \tag*{(4)} Q nk = E z 1 [ P [ j > 1 ∑ z j ⋅ u ≥ − ∥ u ∥ 2 ∣ z 1 = u ] ] . (4) The sum ∑ j > 1 z ⃗ j ⋅ u ⃗ \sum_{j>1}\vec{z}_j\cdot\vec{u} ∑ j > 1 z j ⋅ u is a sum of k − 1 k-1 k − 1 iid random variables with mean 0 0 0 because E [ z ⃗ j ] = 0 \mathbb{E}[\vec{z}_j]=0 E [ z j ] = 0 . We will apply the Berry-Esseen theorem to approximate it by a normal random variable; as preliminaries, we need its variance and third moment of each term in the sum. By Lemma B.1, we have var ( ∑ j > 1 z ⃗ j ⋅ u ⃗ ) = k − 1 n + 2 ∥ u ⃗ ∥ 2 \operatorname{var}(\sum_{j>1}\vec{z}_j\cdot\vec{u})=\frac{k-1}{n+2}\|\vec{u}\|^2 var ( ∑ j > 1 z j ⋅ u ) = n + 2 k − 1 ∥ u ∥ 2 . To calculate the third moment E [ ∣ z ⃗ j ⋅ u ⃗ ∣ 3 ] \mathbb{E}[|\vec{z}_j\cdot\vec{u}|^3] E [ ∣ z j ⋅ u ∣ 3 ] , note that
E [ ∣ z ⃗ j ⋅ u ⃗ ∣ 3 ] = E [ ∣ z ⃗ j ⋅ u ^ ∣ 3 ] ∥ u ⃗ ∥ 3 , \mathbb{E}\left[|\vec{z}_j\cdot\vec{u}|^3\right]=\mathbb{E}\left[|\vec{z}_j\cdot\hat{u}|^3\right]\|\vec{u}\|^3, E [ ∣ z j ⋅ u ∣ 3 ] = E [ ∣ z j ⋅ u ^ ∣ 3 ] ∥ u ∥ 3 , where u ^ = u ⃗ / ∥ u ⃗ ∥ \hat{u}=\vec{u}/\|\vec{u}\| u ^ = u /∥ u ∥ . By rotational symmetry we may assume that u ^ = ( 1 , 0 , … , 0 ) \hat{u}=(1,0,\ldots,0) u ^ = ( 1 , 0 , … , 0 ) . Therefore, z ⃗ j ⋅ u ^ = z j 1 \vec{z}_j\cdot\hat{u}=z_{j1} z j ⋅ u ^ = z j 1 and so E [ ∣ z ⃗ j ⋅ u ⃗ ∣ 3 ] = E [ ∣ z j 1 ∣ 3 ] ∥ u ⃗ ∥ 3 \mathbb{E}[|\vec{z}_j\cdot\vec{u}|^3]=\mathbb{E}[|z_{j1}|^3]\|\vec{u}\|^3 E [ ∣ z j ⋅ u ∣ 3 ] = E [ ∣ z j 1 ∣ 3 ] ∥ u ∥ 3 . By Lemma B.2,
E [ ∣ z ⃗ j ⋅ u ⃗ ∣ 3 ] = 4 v n − 1 v n ( n + 1 ) ( n + 3 ) ∥ u ⃗ ∥ 3 ≤ 4 v n − 1 v n ( n + 1 ) ( n + 3 ) . \mathbb{E}\left[|\vec{z}_j\cdot\vec{u}|^3\right]=\frac{4v_{n-1}}{v_n(n+1)(n+3)}\|\vec{u}\|^3\leq\frac{4v_{n-1}}{v_n(n+1)(n+3)}. E [ ∣ z j ⋅ u ∣ 3 ] = v n ( n + 1 ) ( n + 3 ) 4 v n − 1 ∥ u ∥ 3 ≤ v n ( n + 1 ) ( n + 3 ) 4 v n − 1 . By the Berry-Esseen theorem,
∣ P [ ∑ j > 1 z ⃗ j ⋅ u ⃗ ≥ − ∥ u ⃗ ∥ 2 ] − Φ ( n + 2 k − 1 ∥ u ⃗ ∥ ) ∣ ≤ 4 C B E v n − 1 v n ( n + 2 ) 3 / 2 ( n + 1 ) ( n + 3 ) k − 1 . \left|\mathbb{P}\left[\sum_{j>1}\vec{z}_j\cdot\vec{u}\geq-\|\vec{u}\|^2\right]-\Phi\left(\sqrt{\frac{n+2}{k-1}}\|\vec{u}\|\right)\right|\leq\frac{4C_{BE}v_{n-1}}{v_n}\frac{(n+2)^{3/2}}{(n+1)(n+3)\sqrt{k-1}}. P [ j > 1 ∑ z j ⋅ u ≥ − ∥ u ∥ 2 ] − Φ ( k − 1 n + 2 ∥ u ∥ ) ≤ v n 4 C B E v n − 1 ( n + 1 ) ( n + 3 ) k − 1 ( n + 2 ) 3/2 . where C B E C_{BE} C B E is a universal constant. Finally, we upper bound Φ ( n + 2 k − 1 ∥ u ⃗ ∥ ) \Phi\left(\sqrt{\frac{n+2}{k-1}}\|\vec{u}\|\right) Φ ( k − 1 n + 2 ∥ u ∥ ) . The cdf of a normal variable decreases monotonically after 0 0 0 , so
Φ ( n + 2 k − 1 ∥ u ⃗ ∥ ) ≤ Φ ( n + 2 k − 1 ) = 1 2 + ∫ 0 n + 2 k − 1 1 2 π e − t 2 / 2 d t ≤ 1 2 + 1 2 π n + 2 k − 1 . \Phi\left(\sqrt{\frac{n+2}{k-1}}\|\vec{u}\|\right)\leq\Phi\left(\sqrt{\frac{n+2}{k-1}}\right)=\frac{1}{2}+\int_0^{\sqrt{\frac{n+2}{k-1}}}\frac{1}{\sqrt{2\pi}}e^{-t^2/2}dt\leq\frac{1}{2}+\frac{1}{\sqrt{2\pi}}\sqrt{\frac{n+2}{k-1}}. Φ ( k − 1 n + 2 ∥ u ∥ ) ≤ Φ ( k − 1 n + 2 ) = 2 1 + ∫ 0 k − 1 n + 2 2 π 1 e − t 2 /2 d t ≤ 2 1 + 2 π 1 k − 1 n + 2 .
All together,
P [ ∑ j > 1 z ⃗ j ⋅ u ⃗ ≥ − ∥ u ⃗ ∥ 2 ] ≤ 1 2 + 1 2 π n + 2 k − 1 + 4 C B E v n − 1 v n ( n + 2 ) 3 / 2 ( n + 1 ) ( n + 3 ) k − 1 . \mathbb{P}\left[\sum_{j>1}\vec{z}_j\cdot\vec{u}\ge-\lVert\vec{u}\rVert^2\right]\le\frac{1}{2}+\frac{1}{\sqrt{2\pi}}\sqrt{\frac{n+2}{k-1}}+\frac{4C_{\mathrm{BE}}v_{n-1}}{v_n}\frac{(n+2)^{3/2}}{(n+1)(n+3)\sqrt{k-1}}. P [ j > 1 ∑ z j ⋅ u ≥ − ∥ u ∥ 2 ] ≤ 2 1 + 2 π 1 k − 1 n + 2 + v n 4 C BE v n − 1 ( n + 1 ) ( n + 3 ) k − 1 ( n + 2 ) 3/2 .
for all u ⃗ \vec{u} u . Consequently, the right-hand side is an upper bound for Q n k Q_{nk} Q nk by Equation (4) .
Finally, we upper bound v n − 1 / v n v_{n-1}/v_n v n − 1 / v n to finish the proof. The volume of a unit n n n -ball is v n = π n / 2 / Γ ( n / 2 + 1 ) v_n=\pi^{n/2}/\Gamma(n/2+1) v n = π n /2 /Γ ( n /2 + 1 ) . By Gautschi’s inequality [8 ] ,
v n − 1 v n = Γ ( n 2 + 1 ) Γ ( n − 1 2 + 1 ) π ≤ n + 2 2 π . \frac{v_{n-1}}{v_n}=\frac{\Gamma\left(\frac{n}{2}+1\right)}{\Gamma\left(\frac{n-1}{2}+1\right)\sqrt{\pi}}\le\sqrt{\frac{n+2}{2\pi}}. v n v n − 1 = Γ ( 2 n − 1 + 1 ) π Γ ( 2 n + 1 ) ≤ 2 π n + 2 .
Therefore,
4 C B E v n − 1 v n ( n + 2 ) 3 / 2 ( n + 1 ) ( n + 3 ) k − 1 ≤ 8 C B E 2 π ( k − 1 ) . \frac{4C_{\mathrm{BE}}v_{n-1}}{v_n}\frac{(n+2)^{3/2}}{(n+1)(n+3)\sqrt{k-1}}\le\frac{8C_{\mathrm{BE}}}{\sqrt{2\pi(k-1)}}. v n 4 C BE v n − 1 ( n + 1 ) ( n + 3 ) k − 1 ( n + 2 ) 3/2 ≤ 2 π ( k − 1 ) 8 C BE .
Lemma B.4. Suppose that u ^ 1 , u ^ 2 \hat{u}_1,\hat{u}_2 u ^ 1 , u ^ 2 are unit vectors in R n \mathbb{R}^n R n with angle θ ≠ 0 , π \theta\ne0,\pi θ = 0 , π . Let U U U be the matrix whose columns are u ^ 1 , u ^ 2 \hat{u}_1,\hat{u}_2 u ^ 1 , u ^ 2 and let R = ( 1 cos ( θ ) cos ( θ ) 1 ) R=\begin{pmatrix}1&\cos(\theta)\\\cos(\theta)&1\end{pmatrix} R = ( 1 cos ( θ ) cos ( θ ) 1 ) . If z ⃗ \vec{z} z is sampled uniformly at random from the n n n -ball, then
E [ ∥ R − 1 / 2 U T z ⃗ ∥ 3 ] = E [ ∥ P U z ⃗ ∥ 3 ] ≤ 2 n + 2 , \mathbb{E}\left[\left\lVert R^{-1/2}U^T\vec{z}\right\rVert^3\right]=\mathbb{E}\left[\lVert P_U\vec{z}\rVert^3\right]\le\frac{2}{n+2}, E [ R − 1/2 U T z 3 ] = E [ ∥ P U z ∥ 3 ] ≤ n + 2 2 , where P U P_U P U is the orthogonal projection matrix onto span ( u ^ 1 , u ^ 2 ) \operatorname{span}(\hat{u}_1,\hat{u}_2) span ( u ^ 1 , u ^ 2 ) .
Proof. First, note that R = U T U R=U^TU R = U T U . Therefore,
∥ R − 1 / 2 U T z ⃗ ∥ 2 = z ⃗ T U ( R − 1 / 2 ) T R − 1 / 2 U T z ⃗ = z ⃗ U R − 1 U T z ⃗ = z ⃗ U ( U T U ) − 1 U T z ⃗ = z ⃗ P U z ⃗ = ∥ P U z ⃗ ∥ 2 . \begin{aligned}
\left\lVert R^{-1/2}U^T\vec{z}\right\rVert^2
&=\vec{z}^TU\left(R^{-1/2}\right)^TR^{-1/2}U^T\vec{z}\\
&=\vec{z}UR^{-1}U^T\vec{z}\\
&=\vec{z}U(U^TU)^{-1}U^T\vec{z}\\
&=\vec{z}P_U\vec{z}\\
&=\lVert P_U\vec{z}\rVert^2.
\end{aligned} R − 1/2 U T z 2 = z T U ( R − 1/2 ) T R − 1/2 U T z = z U R − 1 U T z = z U ( U T U ) − 1 U T z = z P U z = ∥ P U z ∥ 2 .
Because ∥ P U z ⃗ ∥ ≤ ∥ z ⃗ ∥ ≤ 1 \lVert P_U\vec{z}\rVert\le\lVert\vec{z}\rVert\le1 ∥ P U z ∥ ≤ ∥ z ∥ ≤ 1 , we have
E [ ∥ R − 1 / 2 U T z ⃗ ∥ 3 ] = E [ ∥ P U z ⃗ ∥ 3 ] ≤ E [ ∥ P U z ⃗ ∥ 2 ] . (5) \mathbb{E}\left[\left\lVert R^{-1/2}U^T\vec{z}\right\rVert^3\right]=\mathbb{E}\left[\lVert P_U\vec{z}\rVert^3\right]\le\mathbb{E}\left[\lVert P_U\vec{z}\rVert^2\right]. \tag*{(5)} E [ R − 1/2 U T z 3 ] = E [ ∥ P U z ∥ 3 ] ≤ E [ ∥ P U z ∥ 2 ] . (5)
Because P U P_U P U is an orthogonal projection matrix,
E [ ∥ P U z ⃗ ∥ 2 ] = E [ z ⃗ T P U z ⃗ ] . \mathbb{E}\left[\lVert P_U\vec{z}\rVert^2\right]=\mathbb{E}[\vec{z}^TP_U\vec{z}]. E [ ∥ P U z ∥ 2 ] = E [ z T P U z ] .
We have
E [ z ⃗ T P U z ⃗ ] = E [ tr ( z ⃗ T P U z ⃗ ) ] = E [ tr ( P U z ⃗ z ⃗ T ) ] = tr ( P U E [ z ⃗ z ⃗ T ] ) . \mathbb{E}[\vec{z}^TP_U\vec{z}]=\mathbb{E}[\operatorname{tr}(\vec{z}^TP_U\vec{z})]=\mathbb{E}[\operatorname{tr}(P_U\vec{z}\vec{z}^T)]=\operatorname{tr}\left(P_U\mathbb{E}[\vec{z}\vec{z}^T]\right). E [ z T P U z ] = E [ tr ( z T P U z )] = E [ tr ( P U z z T )] = tr ( P U E [ z z T ] ) .
For i ≠ j i\ne j i = j , we have E [ ( z ⃗ z ⃗ T ) i j ] = E [ z ⃗ i ] E [ z ⃗ j ] = 0 \mathbb{E}[(\vec{z}\vec{z}^T)_{ij}]=\mathbb{E}[\vec{z}_i]\mathbb{E}[\vec{z}_j]=0 E [( z z T ) ij ] = E [ z i ] E [ z j ] = 0 because the components are independent and mean-centered. For i = j i=j i = j , we have E [ z ⃗ i 2 ] = 1 n ∑ r E [ z ⃗ r 2 ] = 1 n ∥ z ⃗ ∥ 2 \mathbb{E}[\vec{z}_i^2]=\frac{1}{n}\sum_r\mathbb{E}[\vec{z}_r^2]=\frac{1}{n}\lVert\vec{z}\rVert^2 E [ z i 2 ] = n 1 ∑ r E [ z r 2 ] = n 1 ∥ z ∥ 2 . Therefore, E [ z ⃗ z ⃗ T ] = 1 n E [ ∥ z ⃗ ∥ 2 ] I n \mathbb{E}[\vec{z}\vec{z}^T]=\frac{1}{n}\mathbb{E}[\lVert\vec{z}\rVert^2]I_n E [ z z T ] = n 1 E [∥ z ∥ 2 ] I n . By Lemma B.6, we have E [ ∥ z ⃗ ∥ 2 ] = n n + 2 \mathbb{E}[\lVert\vec{z}\rVert^2]=\frac{n}{n+2} E [∥ z ∥ 2 ] = n + 2 n . All together,
E [ ∥ P U z ⃗ ∥ 2 ] = 1 n + 2 tr ( P U ) . \mathbb{E}\left[\lVert P_U\vec{z}\rVert^2\right]=\frac{1}{n+2}\operatorname{tr}(P_U). E [ ∥ P U z ∥ 2 ] = n + 2 1 tr ( P U ) .
Because P U P_U P U is an orthogonal projection matrix onto a plane (the span of non-parallel vector u ^ 1 , u ^ 2 \hat{u}_1,\hat{u}_2 u ^ 1 , u ^ 2 ), its eigenvalues are 1 , 1 , 0 , … , 0 1,1,0,\ldots,0 1 , 1 , 0 , … , 0 , so tr ( P U ) = 2 \operatorname{tr}(P_U)=2 tr ( P U ) = 2 . By Equation (5) ,
E [ ∥ R − 1 / 2 U T z ⃗ ∥ 3 ] ≤ 2 n + 2 . \mathbb{E}\left[\left\lVert R^{-1/2}U^T\vec{z}\right\rVert^3\right]\le\frac{2}{n+2}. E [ R − 1/2 U T z 3 ] ≤ n + 2 2 .
Lemma B.5. Let R = [ 1 ρ ρ 1 ] R = \begin{bmatrix} 1 & \rho\\ \rho& 1 \end{bmatrix} R = [ 1 ρ ρ 1 ] for some − 1 ≤ ρ ≤ 1 -1 \le\rho\le1 − 1 ≤ ρ ≤ 1 , and suppose that B ⃗ ∼ N ( 0 , R ) \vec{B} \sim N(0,R) B ∼ N ( 0 , R ) . Define
f ( τ 1 , τ 2 , ρ ) = P [ B 1 ≤ τ 1 , B 2 ≤ τ 2 ] − Φ ( τ 1 ) Φ ( τ 2 ) f(\tau_1,\tau_2,\rho) = \mathbb{P}[B_1 \le\tau_1, B_2 \le\tau_2] - \Phi(\tau_1)\Phi(\tau_2) f ( τ 1 , τ 2 , ρ ) = P [ B 1 ≤ τ 1 , B 2 ≤ τ 2 ] − Φ ( τ 1 ) Φ ( τ 2 ) .
Then
∣ f ( τ 1 , τ 2 , ρ ) + f ( τ 1 , τ 2 , − ρ ) ∣ ≤ 4 2 π ( ∣ τ 1 ∣ + ∣ τ 2 ∣ ) . \left|f(\tau_1,\tau_2,\rho) + f(\tau_1,\tau_2,-\rho)\right| \le\frac{4}{\sqrt{2\pi}}(|\tau_1| + |\tau_2|). ∣ f ( τ 1 , τ 2 , ρ ) + f ( τ 1 , τ 2 , − ρ ) ∣ ≤ 2 π 4 ( ∣ τ 1 ∣ + ∣ τ 2 ∣ ) .
Proof. We have f ( τ 1 , τ 2 , − ρ ) = P [ B 1 ≤ τ 1 , − B 2 ≤ τ 2 ] − Φ ( τ 1 ) Φ ( τ 2 ) f(\tau_1,\tau_2,-\rho) = \mathbb{P}[B_1 \le\tau_1,-B_2 \le\tau_2] - \Phi(\tau_1)\Phi(\tau_2) f ( τ 1 , τ 2 , − ρ ) = P [ B 1 ≤ τ 1 , − B 2 ≤ τ 2 ] − Φ ( τ 1 ) Φ ( τ 2 ) because B 1 , − B 2 B_1,-B_2 B 1 , − B 2 are normally distributed with variance 1 and correlation − ρ -\rho − ρ . Therefore,
f ( 0 , 0 , ρ ) + f ( 0 , 0 , − ρ ) = P [ B 1 ≤ 0 , B 2 ≤ 0 ] + P [ B 1 ≤ 0 , − B 2 ≤ 0 ] − 2 Φ ( 0 ) Φ ( 0 ) = P [ B 1 ≤ 0 ] − 1 2 = 0. \begin{aligned}
f(0,0,\rho) + f(0,0,-\rho) = \mathbb{P}[B_1 \le0,B_2 \le0] + \mathbb{P}[B_1 \le0,-B_2 \le0] - 2\Phi(0)\Phi(0) \\
&= \mathbb{P}[B_1 \le0] - \frac{1}{2} \\
&= 0.
\end{aligned} f ( 0 , 0 , ρ ) + f ( 0 , 0 , − ρ ) = P [ B 1 ≤ 0 , B 2 ≤ 0 ] + P [ B 1 ≤ 0 , − B 2 ≤ 0 ] − 2Φ ( 0 ) Φ ( 0 ) = P [ B 1 ≤ 0 ] − 2 1 = 0.
Therefore, for nonzero τ 1 , τ 2 \tau_1,\tau_2 τ 1 , τ 2 ,
∣ f ( τ 1 , τ 2 , ρ ) + f ( τ 1 , τ 2 , − ρ ) ∣ ≤ ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , ρ ) ∣ + ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , − ρ ) ∣ + ∣ f ( 0 , 0 , ρ ) − f ( 0 , 0 , − ρ ) ∣ = ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , ρ ) ∣ + ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , − ρ ) ∣ . (6) \begin{aligned}
\left|f(\tau_1,\tau_2,\rho) + f(\tau_1,\tau_2,-\rho)\right|
&\le\left|f(\tau_1,\tau_2,\rho)-f(0,0,\rho)\right| + \left|f(\tau_1,\tau_2,\rho)-f(0,0,-\rho)\right| \\
&\quad+ \left|f(0,0,\rho)-f(0,0,-\rho)\right| \\
&= \left|f(\tau_1,\tau_2,\rho)-f(0,0,\rho)\right| + \left|f(\tau_1,\tau_2,\rho)-f(0,0,-\rho)\right|. \tag*{(6)}
\end{aligned} ∣ f ( τ 1 , τ 2 , ρ ) + f ( τ 1 , τ 2 , − ρ ) ∣ ≤ ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , ρ ) ∣ + ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , − ρ ) ∣ + ∣ f ( 0 , 0 , ρ ) − f ( 0 , 0 , − ρ ) ∣ = ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , ρ ) ∣ + ∣ f ( τ 1 , τ 2 , ρ ) − f ( 0 , 0 , − ρ ) ∣ . (6)
Therefore, it suffices to show that ∣ ∂ f / ∂ τ i ∣ ≤ 1 2 π \left|\partial f/\partial\tau_i\right| \le\frac{1}{\sqrt{2\pi}} ∣ ∂ f / ∂ τ i ∣ ≤ 2 π 1 . Let g ( τ 1 , τ 2 , ρ ) = P [ B 1 ≤ τ 1 , B 2 ≤ τ 2 ] g(\tau_1,\tau_2,\rho) = \mathbb{P}[B_1 \le\tau_1,B_2 \le\tau_2] g ( τ 1 , τ 2 , ρ ) = P [ B 1 ≤ τ 1 , B 2 ≤ τ 2 ] , where ρ \rho ρ is the correlation of B 1 , B 2 B_1,B_2 B 1 , B 2 . We will calculate ∂ f / ∂ τ i \partial f/\partial\tau_i ∂ f / ∂ τ i for i = 1 i=1 i = 1 ; the case i = 2 i=2 i = 2 is symmetric. We have
∂ f ∂ τ 1 = ∂ g ∂ τ 1 − φ ( τ 1 ) Φ ( τ 2 ) . \frac{\partial f}{\partial\tau_1} = \frac{\partial g}{\partial\tau_1} - \varphi(\tau_1)\Phi(\tau_2). ∂ τ 1 ∂ f = ∂ τ 1 ∂ g − φ ( τ 1 ) Φ ( τ 2 ) .
Letting φ ρ ( b 1 , b 2 ) \varphi_\rho(b_1,b_2) φ ρ ( b 1 , b 2 ) denote the joint pdf for B 1 , B 2 B_1,B_2 B 1 , B 2 , we have
∂ g ∂ τ 1 = ∂ g ∂ τ 1 ∫ − ∞ τ 1 ∫ − ∞ τ 2 φ ρ ( b 1 , b 2 ) d b 2 d b 1 = ∫ − ∞ τ 2 φ ρ ( τ 1 , b 2 ) d b 2 = φ ( τ 1 ) P [ B 2 ≤ τ 2 ∣ B 1 = τ 1 ] . \frac{\partial g}{\partial\tau_1} = \frac{\partial g}{\partial\tau_1}\int_{-\infty}^{\tau_1}\int_{-\infty}^{\tau_2}\varphi_\rho(b_1,b_2)\,db_2\,db_1 = \int_{-\infty}^{\tau_2}\varphi_\rho(\tau_1,b_2)\,db_2 = \varphi(\tau_1)\mathbb{P}[B_2 \le\tau_2\mid B_1=\tau_1]. ∂ τ 1 ∂ g = ∂ τ 1 ∂ g ∫ − ∞ τ 1 ∫ − ∞ τ 2 φ ρ ( b 1 , b 2 ) d b 2 d b 1 = ∫ − ∞ τ 2 φ ρ ( τ 1 , b 2 ) d b 2 = φ ( τ 1 ) P [ B 2 ≤ τ 2 ∣ B 1 = τ 1 ] .
To calculate the conditional CDF, we note that φ ρ \varphi_\rho φ ρ factors as
φ ρ ( b 1 , b 2 ) = 1 2 π 1 − ρ 2 exp ( − 1 2 ( 1 − ρ 2 ) [ b 1 2 + b 2 2 − 2 ρ b 1 b 2 ] ) = 1 2 π 1 − ρ 2 exp ( − 1 2 ( 1 − ρ 2 ) [ ( 1 − ρ 2 ) b 1 2 + ( b 2 − ρ b 1 ) 2 ] ) = 1 2 π exp ( − b 1 2 2 ) 1 2 π ( 1 − ρ 2 ) exp ( − 1 2 ( 1 − ρ 2 ) ( b 2 − ρ b 1 ) 2 ) = φ ( b 1 ) 1 2 π ( 1 − ρ 2 ) exp ( − 1 2 ( 1 − ρ 2 ) ( b 2 − ρ b 1 ) 2 ) , \begin{aligned}
\varphi_\rho(b_1,b_2)
&= \frac{1}{2\pi\sqrt{1-\rho^2}}\exp\left(-\frac{1}{2(1-\rho^2)}[b_1^2+b_2^2-2\rho b_1b_2]\right) \\
&= \frac{1}{2\pi\sqrt{1-\rho^2}}\exp\left(-\frac{1}{2(1-\rho^2)}[(1-\rho^2)b_1^2+(b_2-\rho b_1)^2]\right) \\
&= \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{b_1^2}{2}\right)\frac{1}{\sqrt{2\pi(1-\rho^2)}}\exp\left(-\frac{1}{2(1-\rho^2)}(b_2-\rho b_1)^2\right) \\
&= \varphi(b_1)\frac{1}{\sqrt{2\pi(1-\rho^2)}}\exp\left(-\frac{1}{2(1-\rho^2)}(b_2-\rho b_1)^2\right),
\end{aligned} φ ρ ( b 1 , b 2 ) = 2 π 1 − ρ 2 1 exp ( − 2 ( 1 − ρ 2 ) 1 [ b 1 2 + b 2 2 − 2 ρ b 1 b 2 ] ) = 2 π 1 − ρ 2 1 exp ( − 2 ( 1 − ρ 2 ) 1 [( 1 − ρ 2 ) b 1 2 + ( b 2 − ρ b 1 ) 2 ] ) = 2 π 1 exp ( − 2 b 1 2 ) 2 π ( 1 − ρ 2 ) 1 exp ( − 2 ( 1 − ρ 2 ) 1 ( b 2 − ρ b 1 ) 2 ) = φ ( b 1 ) 2 π ( 1 − ρ 2 ) 1 exp ( − 2 ( 1 − ρ 2 ) 1 ( b 2 − ρ b 1 ) 2 ) ,
so the pdf for B 2 ∣ B 1 = τ 1 B_2\mid B_1=\tau_1 B 2 ∣ B 1 = τ 1 is the pdf of a normal random variable with mean ρ b 1 \rho b_1 ρ b 1 and variance 1 − ρ 2 1-\rho^2 1 − ρ 2 . Therefore,
P [ B 2 ≤ τ 2 ∣ B 1 = τ 1 ] = Φ ( τ 2 − ρ τ 1 1 − ρ 2 ) . \mathbb{P}[B_2 \le\tau_2\mid B_1=\tau_1] = \Phi\left(\frac{\tau_2-\rho\tau_1}{\sqrt{1-\rho^2}}\right). P [ B 2 ≤ τ 2 ∣ B 1 = τ 1 ] = Φ ( 1 − ρ 2 τ 2 − ρ τ 1 ) .
Because 0 ≤ Φ ( x ) ≤ 1 0\le\Phi(x)\le1 0 ≤ Φ ( x ) ≤ 1 for any x x x ,
∣ ∂ f ∂ τ 1 ∣ = φ ( τ 1 ) ∣ Φ ( τ 2 − ρ τ 1 1 − ρ 2 ) − Φ ( τ 2 ) ∣ ≤ φ ( τ 1 ) = 1 2 π e − τ 1 2 / 2 ≤ 1 2 π . (7) \left|\frac{\partial f}{\partial\tau_1}\right| = \varphi(\tau_1)\left|\Phi\left(\frac{\tau_2-\rho\tau_1}{\sqrt{1-\rho^2}}\right)-\Phi(\tau_2)\right| \le\varphi(\tau_1)=\frac{1}{\sqrt{2\pi}}e^{-\tau_1^2/2}\le\frac{1}{\sqrt{2\pi}}. \tag*{(7)} ∂ τ 1 ∂ f = φ ( τ 1 ) Φ ( 1 − ρ 2 τ 2 − ρ τ 1 ) − Φ ( τ 2 ) ≤ φ ( τ 1 ) = 2 π 1 e − τ 1 2 /2 ≤ 2 π 1 . (7)
The same upper bound holds for ∣ ∂ f / ∂ τ 2 ∣ \left|\partial f/\partial\tau_2\right| ∣ ∂ f / ∂ τ 2 ∣ . Combining (6) and (7) completes the proof.
Lemma B.6. We have var ( X i ) = Q n k ( 1 − Q n k ) \operatorname{var}(X_i)=Q_{nk}(1-Q_{nk}) var ( X i ) = Q nk ( 1 − Q nk ) for all i i i , and there are constants C 1 , C 2 C_1,C_2 C 1 , C 2 such that
cov ( X 1 , X 2 ) ≤ C 1 n k + C 2 n k \operatorname{cov}(X_1,X_2)\le C_1\sqrt{\frac{n}{k}}+C_2\frac{n}{k} cov ( X 1 , X 2 ) ≤ C 1 k n + C 2 k n for all $k\ge 3.
Proof. For the variance, observe that X i X_i X i is a Boolean random variable with probability of success Q n k Q_{nk} Q nk . For the covariance, we have
cov ( X 1 , X 2 ) = E [ X 1 X 2 ] − Q n k 2 = P [ X 1 = 1 and X 2 = 1 ] − Q n k 2 . (8) \operatorname{cov}(X_1,X_2)=\mathbb{E}[X_1X_2]-Q_{nk}^{2}=\mathbb{P}[X_1=1\text{ and }X_2=1]-Q_{nk}^{2}. \tag*{(8)} cov ( X 1 , X 2 ) = E [ X 1 X 2 ] − Q nk 2 = P [ X 1 = 1 and X 2 = 1 ] − Q nk 2 . (8)
By Lemma B.3 , there are constants A 1 , A 2 A_1,A_2 A 1 , A 2 such that
∣ Q n k 2 − 1 4 ∣ ≤ A 1 n k + A 2 n k . (9) \left|Q_{nk}^{2}-\frac{1}{4}\right|\leq A_1\sqrt{\frac{n}{k}}+A_2\frac{n}{k}. \tag*{(9)} Q nk 2 − 4 1 ≤ A 1 k n + A 2 k n . (9)
for all k ≥ 2 k\geq2 k ≥ 2 .
The focus of the rest of the proof is to upper bound ∣ P [ X 1 = 1 and X 2 = 1 ] − 1 4 ∣ \left|\mathbb{P}[X_1=1\text{ and }X_2=1]-\frac{1}{4}\right| P [ X 1 = 1 and X 2 = 1 ] − 4 1 . Let v ^ = ∑ j > 2 z ⃗ j \hat{v}=\sum_{j>2}\vec{z}_j v ^ = ∑ j > 2 z j . For i = 1 , 2 i=1,2 i = 1 , 2 , we have
∑ j z ⃗ j ⋅ z ⃗ i = v ^ ⋅ z ⃗ i + ∥ z ⃗ i ∥ 2 + z ⃗ 1 ⋅ z ⃗ 2 , \sum_j\vec{z}_j\cdot\vec{z}_i=\hat{v}\cdot\vec{z}_i+\|\vec{z}_i\|^2+\vec{z}_1\cdot\vec{z}_2, j ∑ z j ⋅ z i = v ^ ⋅ z i + ∥ z i ∥ 2 + z 1 ⋅ z 2 ,
so X i = 1 X_i=1 X i = 1 if and only if v ^ ⋅ z ⃗ i ≥ − ∥ z ⃗ i ∥ 2 − z ⃗ 1 ⋅ z ⃗ 2 \hat{v}\cdot\vec{z}_i\geq-\|\vec{z}_i\|^2-\vec{z}_1\cdot\vec{z}_2 v ^ ⋅ z i ≥ − ∥ z i ∥ 2 − z 1 ⋅ z 2 . Conditioning on z ⃗ 1 = u ⃗ 1 \vec{z}_1=\vec{u}_1 z 1 = u 1 and z ⃗ 2 = u ⃗ 2 \vec{z}_2=\vec{u}_2 z 2 = u 2 , we get
P [ X 1 = 1 and X 2 = 1 ] = E z ⃗ 1 , z ⃗ 2 [ P [ X 1 = 1 and X 2 = 1 ∣ z ⃗ 1 = u ⃗ 1 , z ⃗ 2 = u ⃗ 2 ] ] , \mathbb{P}[X_1=1\text{ and }X_2=1]=\mathbb{E}_{\vec{z}_1,\vec{z}_2}\left[\mathbb{P}[X_1=1\text{ and }X_2=1\mid\vec{z}_1=\vec{u}_1,\vec{z}_2=\vec{u}_2]\right], P [ X 1 = 1 and X 2 = 1 ] = E z 1 , z 2 [ P [ X 1 = 1 and X 2 = 1 ∣ z 1 = u 1 , z 2 = u 2 ] ] ,
where the conditional probability is
P [ X 1 = 1 and X 2 = 1 ∣ z ⃗ 1 = u ⃗ 1 , z ⃗ 2 = u ⃗ 2 ] = P [ v ^ ⋅ u ⃗ 1 ≥ − a 1 and v ^ ⋅ u ⃗ 2 ≥ − a 2 ] , (10) \mathbb{P}[X_1=1\text{ and }X_2=1\mid\vec{z}_1=\vec{u}_1,\vec{z}_2=\vec{u}_2]=\mathbb{P}[\hat{v}\cdot\vec{u}_1\geq-a_1\text{ and }\hat{v}\cdot\vec{u}_2\geq-a_2], \tag*{(10)} P [ X 1 = 1 and X 2 = 1 ∣ z 1 = u 1 , z 2 = u 2 ] = P [ v ^ ⋅ u 1 ≥ − a 1 and v ^ ⋅ u 2 ≥ − a 2 ] , (10)
where a i = ∥ u ⃗ i ∥ 2 − u ⃗ 1 ⋅ u ⃗ 2 a_i=\|\vec{u}_i\|^2-\vec{u}_1\cdot\vec{u}_2 a i = ∥ u i ∥ 2 − u 1 ⋅ u 2 for i = 1 , 2 i=1,2 i = 1 , 2 .
Let Y i = v ^ ⋅ u ⃗ i Y_i=\hat{v}\cdot\vec{u}_i Y i = v ^ ⋅ u i for i = 1 , 2 i=1,2 i = 1 , 2 , and consider the 2D vector Y ⃗ = ( Y 1 , Y 2 ) \vec{Y}=(Y_1,Y_2) Y = ( Y 1 , Y 2 ) . The right-hand side of Equation (10) is P [ Y ⃗ ≥ ( − a 1 , − a 2 ) ] \mathbb{P}[\vec{Y}\geq(-a_1,-a_2)] P [ Y ≥ ( − a 1 , − a 2 )] . Therefore,
P [ X 1 = 1 and X 2 = 1 ] = E z ⃗ 1 , z ⃗ 2 [ P [ Y ⃗ ≥ ( − a 1 , − a 2 ) ] ] . \mathbb{P}[X_1=1\text{ and }X_2=1]=\mathbb{E}_{\vec{z}_1,\vec{z}_2}\left[\mathbb{P}[\vec{Y}\geq(-a_1,-a_2)]\right]. P [ X 1 = 1 and X 2 = 1 ] = E z 1 , z 2 [ P [ Y ≥ ( − a 1 , − a 2 )] ] .
We have that Y ⃗ \vec{Y} Y is the sum of k − 2 k-2 k − 2 iid 2D random variables:
Y ⃗ = ∑ j > 2 ( z ⃗ j ⋅ u ⃗ 1 , z ⃗ j ⋅ u ⃗ 2 ) \vec{Y}=\sum_{j>2}(\vec{z}_j\cdot\vec{u}_1,\vec{z}_j\cdot\vec{u}_2) Y = j > 2 ∑ ( z j ⋅ u 1 , z j ⋅ u 2 )
with mean 0 because E [ z ⃗ j ] = 0 \mathbb{E}[\vec{z}_j]=0 E [ z j ] = 0 by symmetry of the ball. Using the fact that the variance of the i i i th component of z ⃗ j \vec{z}_j z j is 1 n + 2 \frac{1}{n+2} n + 2 1 by Lemma B.1, we get that the covariance matrix for Y ⃗ \vec{Y} Y is
C Y ⃗ = k − 2 n + 2 [ ∥ u ⃗ 1 ∥ 2 u ⃗ 1 ⋅ u ⃗ 2 u ⃗ 1 ⋅ u ⃗ 2 ∥ u ⃗ 2 ∥ 2 ] . C_{\vec{Y}}=\frac{k-2}{n+2}
\begin{bmatrix}
\|\vec{u}_1\|^2 & \vec{u}_1\cdot\vec{u}_2\\
\vec{u}_1\cdot\vec{u}_2 & \|\vec{u}_2\|^2
\end{bmatrix}. C Y = n + 2 k − 2 [ ∥ u 1 ∥ 2 u 1 ⋅ u 2 u 1 ⋅ u 2 ∥ u 2 ∥ 2 ] .
We normalize Y ⃗ \vec{Y} Y so that each component has variance 1. Let Y ^ i = Y i / σ Y i \hat{Y}_i=Y_i/\sigma_{Y_i} Y ^ i = Y i / σ Y i and let τ i = a i / σ Y i \tau_i=a_i/\sigma_{Y_i} τ i = a i / σ Y i . The main probability of interest is
P [ Y ⃗ ≥ ( − a 1 , − a 2 ) ] = P [ Y ⃗ ^ ≥ ( − τ 1 , − τ 2 ) ] , \mathbb{P}[\vec{Y}\geq(-a_1,-a_2)]=\mathbb{P}[\hat{\vec{Y}}\geq(-\tau_1,-\tau_2)], P [ Y ≥ ( − a 1 , − a 2 )] = P [ Y ^ ≥ ( − τ 1 , − τ 2 )] ,
where
∣ τ i ∣ = n + 2 k − 2 ∣ ∥ u ⃗ i ∥ 2 − u ⃗ 1 ⋅ u ⃗ 2 ∣ ∥ u ⃗ i ∥ ≤ 2 n + 2 k − 2 . (11) |\tau_i|=\sqrt{\frac{n+2}{k-2}}\frac{\left|\|\vec{u}_i\|^2-\vec{u}_1\cdot\vec{u}_2\right|}{\|\vec{u}_i\|}\leq2\sqrt{\frac{n+2}{k-2}}. \tag*{(11)} ∣ τ i ∣ = k − 2 n + 2 ∥ u i ∥ ∥ u i ∥ 2 − u 1 ⋅ u 2 ≤ 2 k − 2 n + 2 . (11)
because u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 are in the unit ball. The covariance matrix for Y ⃗ ^ \hat{\vec{Y}} Y ^ is
R : = [ 1 cos ( θ ) cos ( θ ) 1 ] , R:=\begin{bmatrix}
1 & \cos(\theta)\\
\cos(\theta) & 1
\end{bmatrix}, R := [ 1 cos ( θ ) cos ( θ ) 1 ] ,
where θ \theta θ is the angle between u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 .
Let B ⃗ ∼ N ( 0 ⃗ , R ) \vec{B}\sim N(\vec{0},R) B ∼ N ( 0 , R ) . We will upper bound ∣ P [ Y ⃗ ^ ≥ ( − τ 1 , − τ 2 ) ] − P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] ∣ \left|\mathbb{P}[\hat{\vec{Y}}\geq(-\tau_1,-\tau_2)]-\mathbb{P}[\vec{B}\geq(-\tau_1,-\tau_2)]\right| P [ Y ^ ≥ ( − τ 1 , − τ 2 )] − P [ B ≥ ( − τ 1 , − τ 2 )] using the multi-dimensional Berry-Esseen theorem. We can write Y ⃗ ^ \hat{\vec{Y}} Y ^ as the sum of ( k − 2 ) (k-2) ( k − 2 ) iid random variables Y ⃗ ^ = ∑ j = 3 k w ⃗ j \hat{\vec{Y}}=\sum_{j=3}^{k}\vec{w}_j Y ^ = ∑ j = 3 k w j , where
w ⃗ j : = ( z ⃗ j ⋅ u ⃗ 1 σ Y 1 , z ⃗ j ⋅ u ⃗ 2 σ Y 2 ) = n + 2 k − 2 ( z ⃗ j ⋅ u ⃗ ^ 1 , z ⃗ j ⋅ u ⃗ ^ 2 ) = n + 2 k − 2 U T z ⃗ \vec{w}_j:=\left(\frac{\vec{z}_j\cdot\vec{u}_1}{\sigma_{Y_1}},\frac{\vec{z}_j\cdot\vec{u}_2}{\sigma_{Y_2}}\right)=\sqrt{\frac{n+2}{k-2}}(\vec{z}_j\cdot\hat{\vec{u}}_1,\vec{z}_j\cdot\hat{\vec{u}}_2)=\sqrt{\frac{n+2}{k-2}}U^T\vec{z} w j := ( σ Y 1 z j ⋅ u 1 , σ Y 2 z j ⋅ u 2 ) = k − 2 n + 2 ( z j ⋅ u ^ 1 , z j ⋅ u ^ 2 ) = k − 2 n + 2 U T z
where u ^ i = u ⃗ i / ∥ u ⃗ i ∥ \hat{u}_i=\vec{u}_i/\lVert\vec{u}_i\rVert u ^ i = u i / ∥ u i ∥ and U U U is the ( n × 2 ) (n\times2) ( n × 2 ) matrix with columns u ^ 1 , u ^ 2 \hat{u}_1,\hat{u}_2 u ^ 1 , u ^ 2 . The covariance matrix R R R is invertible whenever θ ≠ 0 , π \theta\ne0,\pi θ = 0 , π . Therefore when θ ≠ 0 , π \theta\ne0,\pi θ = 0 , π , the multi-dimensional Berry-Esseen theorem implies that
∣ P [ Y ^ ≥ ( − τ 1 , − τ 2 ) ] − P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] ∣ ≤ C B E 2 1 / 4 γ k − 2 , \left|\mathbb{P}[\widehat{Y}\ge(-\tau_1,-\tau_2)]-\mathbb{P}[\vec{B}\ge(-\tau_1,-\tau_2)]\right|\le C_{BE}2^{1/4}\gamma_{k-2}, P [ Y ≥ ( − τ 1 , − τ 2 )] − P [ B ≥ ( − τ 1 , − τ 2 )] ≤ C B E 2 1/4 γ k − 2 ,
where C B E C_{BE} C B E is a universal constant and
γ k − 2 = ∑ j = 3 k E [ ∥ R − 1 / 2 w ⃗ j ∥ 2 3 ] = ( k − 2 ) E [ ∥ R − 1 / 2 w ⃗ 3 ∥ 2 3 ] = ( n + 2 ) 3 / 2 k − 2 E [ ∥ R − 1 / 2 U T z ⃗ 3 ∥ 2 3 ] . \gamma_{k-2}=\sum_{j=3}^{k}\mathbb{E}\left[\lVert R^{-1/2}\vec{w}_j\rVert_2^3\right]=(k-2)\mathbb{E}\left[\lVert R^{-1/2}\vec{w}_3\rVert_2^3\right]=\frac{(n+2)^{3/2}}{\sqrt{k-2}}\mathbb{E}\left[\lVert R^{-1/2}U^{T}\vec{z}_3\rVert_2^3\right]. γ k − 2 = j = 3 ∑ k E [ ∥ R − 1/2 w j ∥ 2 3 ] = ( k − 2 ) E [ ∥ R − 1/2 w 3 ∥ 2 3 ] = k − 2 ( n + 2 ) 3/2 E [ ∥ R − 1/2 U T z 3 ∥ 2 3 ] .
By Lemma B.4, we have γ k − 2 ≤ n + 2 k − 2 \gamma_{k-2}\le\sqrt{\frac{n+2}{k-2}} γ k − 2 ≤ k − 2 n + 2 when θ ≠ 0 , π \theta\ne0,\pi θ = 0 , π . Therefore,
∣ P [ Y ^ ≥ ( − τ 1 , − τ 2 ) ] − P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] ∣ ≤ C B E 2 1 / 4 n + 2 k − 2 \left|\mathbb{P}[\widehat{Y}\ge(-\tau_1,-\tau_2)]-\mathbb{P}[\vec{B}\ge(-\tau_1,-\tau_2)]\right|\le C_{BE}2^{1/4}\sqrt{\frac{n+2}{k-2}} P [ Y ≥ ( − τ 1 , − τ 2 )] − P [ B ≥ ( − τ 1 , − τ 2 )] ≤ C B E 2 1/4 k − 2 n + 2
for all fixed u ⃗ 1 , u ⃗ 2 \vec{u}_1,\vec{u}_2 u 1 , u 2 such that θ ≠ 0 , π \theta\ne0,\pi θ = 0 , π . Vectors z ⃗ 1 , z ⃗ 2 \vec{z}_1,\vec{z}_2 z 1 , z 2 have angle θ ≠ 0 , π \theta\ne0,\pi θ = 0 , π with probability 1 1 1 , so
∣ E z ⃗ 1 , z ⃗ 2 [ P [ Y ^ ≥ ( − τ 1 , − τ 2 ) ] − P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] ] ∣ ≤ C B E 2 1 / 4 n + 2 k − 2 . (12) \left|\mathbb{E}_{\vec{z}_1,\vec{z}_2}\left[\mathbb{P}[\widehat{Y}\ge(-\tau_1,-\tau_2)]-\mathbb{P}[\vec{B}\ge(-\tau_1,-\tau_2)]\right]\right|\le C_{BE}2^{1/4}\sqrt{\frac{n+2}{k-2}}. \tag*{(12)} E z 1 , z 2 [ P [ Y ≥ ( − τ 1 , − τ 2 )] − P [ B ≥ ( − τ 1 , − τ 2 )] ] ≤ C B E 2 1/4 k − 2 n + 2 . (12)
Next, we show that Φ ( τ 1 ) Φ ( τ 2 ) \Phi(\tau_1)\Phi(\tau_2) Φ ( τ 1 ) Φ ( τ 2 ) is a good approximation to P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] \mathbb{P}[\vec{B}\ge(-\tau_1,-\tau_2)] P [ B ≥ ( − τ 1 , − τ 2 )] in the expectation over z ⃗ 1 , z ⃗ 2 \vec{z}_1,\vec{z}_2 z 1 , z 2 . First, note that
P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] = P [ B ⃗ ≤ ( τ 1 , τ 2 ) ] . \mathbb{P}[\vec{B}\ge(-\tau_1,-\tau_2)]=\mathbb{P}[\vec{B}\le(\tau_1,\tau_2)]. P [ B ≥ ( − τ 1 , − τ 2 )] = P [ B ≤ ( τ 1 , τ 2 )] .
Use the notation P θ [ B ⃗ ≤ ( τ 1 , τ 2 ) ] \mathbb{P}_{\theta}[\vec{B}\le(\tau_1,\tau_2)] P θ [ B ≤ ( τ 1 , τ 2 )] to denote the probability when the angle between u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 is θ \theta θ . By Lemma B.5,
∣ P θ [ B ⃗ ≤ ( τ 1 , τ 2 ) ] + P π − θ [ B ⃗ ≤ ( τ 1 , τ 2 ) ] − 2 Φ ( τ 1 ) Φ ( τ 2 ) ∣ ≤ 4 2 π ( ∣ τ 1 ∣ + ∣ τ 2 ∣ ) . \left|\mathbb{P}_{\theta}[\vec{B}\le(\tau_1,\tau_2)]+\mathbb{P}_{\pi-\theta}[\vec{B}\le(\tau_1,\tau_2)]-2\Phi(\tau_1)\Phi(\tau_2)\right|\le\frac{4}{\sqrt{2\pi}}(|\tau_1|+|\tau_2|). P θ [ B ≤ ( τ 1 , τ 2 )] + P π − θ [ B ≤ ( τ 1 , τ 2 )] − 2Φ ( τ 1 ) Φ ( τ 2 ) ≤ 2 π 4 ( ∣ τ 1 ∣ + ∣ τ 2 ∣ ) .
Therefore when we integrate over all u ⃗ 1 , u ⃗ 2 \vec{u}_1,\vec{u}_2 u 1 , u 2 in the n n n -ball, we get
∣ E z ⃗ 1 , z ⃗ 2 [ P θ [ B ⃗ ≤ ( τ 1 , τ 2 ) ] − Φ ( τ 1 ) Φ ( τ 2 ) ] ∣ ≤ 2 2 π ( ∣ τ 1 ∣ + ∣ τ 2 ∣ ) . \left|\mathbb{E}_{\vec{z}_1,\vec{z}_2}\left[\mathbb{P}_{\theta}[\vec{B}\le(\tau_1,\tau_2)]-\Phi(\tau_1)\Phi(\tau_2)\right]\right|\le\frac{2}{\sqrt{2\pi}}(|\tau_1|+|\tau_2|). E z 1 , z 2 [ P θ [ B ≤ ( τ 1 , τ 2 )] − Φ ( τ 1 ) Φ ( τ 2 ) ] ≤ 2 π 2 ( ∣ τ 1 ∣ + ∣ τ 2 ∣ ) .
By Equation (11) ,
∣ E z ⃗ 1 , z ⃗ 2 [ P θ [ B ⃗ ≤ ( τ 1 , τ 2 ) ] − Φ ( τ 1 ) Φ ( τ 2 ) ] ∣ ≤ 8 2 π n + 2 k − 2 . (13) \left|\mathbb{E}_{\vec{z}_1,\vec{z}_2}\left[\mathbb{P}_{\theta}[\vec{B}\le(\tau_1,\tau_2)]-\Phi(\tau_1)\Phi(\tau_2)\right]\right|\le\frac{8}{\sqrt{2\pi}}\sqrt{\frac{n+2}{k-2}}. \tag*{(13)} E z 1 , z 2 [ P θ [ B ≤ ( τ 1 , τ 2 )] − Φ ( τ 1 ) Φ ( τ 2 ) ] ≤ 2 π 8 k − 2 n + 2 . (13)
Additionally, we note that
1 2 ≤ Φ ( τ i ) ≤ Φ ( n + 2 k − 2 ) ≤ 1 2 + ∫ 0 n + 2 k − 2 1 2 π e − t 2 / 2 d t ≤ 1 2 + 1 2 π n + 2 k − 2 . \frac{1}{2}\le\Phi(\tau_i)\le\Phi\left(\sqrt{\frac{n+2}{k-2}}\right)\le\frac{1}{2}+\int_{0}^{\sqrt{\frac{n+2}{k-2}}}\frac{1}{\sqrt{2\pi}}e^{-t^2/2}dt\le\frac{1}{2}+\frac{1}{\sqrt{2\pi}}\sqrt{\frac{n+2}{k-2}}. 2 1 ≤ Φ ( τ i ) ≤ Φ ( k − 2 n + 2 ) ≤ 2 1 + ∫ 0 k − 2 n + 2 2 π 1 e − t 2 /2 d t ≤ 2 1 + 2 π 1 k − 2 n + 2 .
Consequently,
∣ Φ ( τ 1 ) Φ ( τ 2 ) − 1 4 ∣ ≤ 1 2 π n + 2 k − 2 + 1 2 π ( n + 2 k − 2 ) . (14) \left|\Phi(\tau_1)\Phi(\tau_2)-\frac{1}{4}\right|\le\frac{1}{\sqrt{2\pi}}\sqrt{\frac{n+2}{k-2}}+\frac{1}{2\pi}\left(\frac{n+2}{k-2}\right). \tag*{(14)} Φ ( τ 1 ) Φ ( τ 2 ) − 4 1 ≤ 2 π 1 k − 2 n + 2 + 2 π 1 ( k − 2 n + 2 ) . (14)
By Equation (8) , Equation (9) , Equation (12) , Equation (13) , and Equation (14) , there are constants C 1 , C 2 C_1,C_2 C 1 , C 2 such that
∣ cov ( X 1 , X 2 ) ∣ ≤ ∣ E z ⃗ 1 , z ⃗ 2 [ P [ Y ^ ≥ ( − τ 1 , − τ 2 ) ] − P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] ] ∣ + ∣ E z ⃗ 1 , z ⃗ 2 [ P [ B ⃗ ≥ ( − τ 1 , − τ 2 ) ] − Φ ( τ 1 ) Φ ( τ 2 ) ] ∣ + ∣ Φ ( τ 1 ) Φ ( τ 2 ) − 1 4 ∣ + ∣ Q n k 2 − 1 4 ∣ ≤ C 1 n k + C 2 n k \begin{aligned}
\left|\operatorname{cov}(X_1,X_2)\right|
&\le\left|\mathbb{E}_{\vec{z}_1,\vec{z}_2}\left[\mathbb{P}[\widehat{Y}\ge(-\tau_1,-\tau_2)]-\mathbb{P}[\vec{B}\ge(-\tau_1,-\tau_2)]\right]\right|\\
&\quad+\left|\mathbb{E}_{\vec{z}_1,\vec{z}_2}\left[\mathbb{P}[\vec{B}\ge(-\tau_1,-\tau_2)]-\Phi(\tau_1)\Phi(\tau_2)\right]\right|\\
&\quad+\left|\Phi(\tau_1)\Phi(\tau_2)-\frac{1}{4}\right|+\left|Q_{nk}^{2}-\frac{1}{4}\right|\\
&\le C_1\sqrt{\frac{n}{k}}+C_2\frac{n}{k}
\end{aligned} ∣ cov ( X 1 , X 2 ) ∣ ≤ E z 1 , z 2 [ P [ Y ≥ ( − τ 1 , − τ 2 )] − P [ B ≥ ( − τ 1 , − τ 2 )] ] + E z 1 , z 2 [ P [ B ≥ ( − τ 1 , − τ 2 )] − Φ ( τ 1 ) Φ ( τ 2 ) ] + Φ ( τ 1 ) Φ ( τ 2 ) − 4 1 + Q nk 2 − 4 1 ≤ C 1 k n + C 2 k n
for all k ≥ 3 k\ge3 k ≥ 3 .
Proof of thm:half for boundary points
Next, we consider the case where { z ⃗ i } i = 1 k \{\vec{z}_i\}_{i=1}^k { z i } i = 1 k is a set of points sampled from an n n n -dimensional half ball, modeling the boundary score of a point x x x on the boundary of an n n n -dimensional manifold.
Proof of Theorem 2.2. The random variable 1 − S n k k 1-\frac{S_{n k}}{k} 1 − k S nk is non-negative. By Markov’s inequality,
P [ 1 − S n k k ≥ ϵ ] ≤ E [ 1 − S n k k ] ϵ = 1 − P [ w ⃗ ⋅ z ⃗ 1 ≥ 0 ] ϵ = P [ w ⃗ ⋅ z ⃗ 1 < 0 ] ϵ . \mathbb{P}\left[1-\frac{S_{n k}}{k}\ge\epsilon\right]\le\frac{\mathbb{E}\left[1-\frac{S_{n k}}{k}\right]}{\epsilon}=\frac{1-\mathbb{P}[\vec{w}\cdot\vec{z}_1\ge0]}{\epsilon}=\frac{\mathbb{P}[\vec{w}\cdot\vec{z}_1<0]}{\epsilon}. P [ 1 − k S nk ≥ ϵ ] ≤ ϵ E [ 1 − k S nk ] = ϵ 1 − P [ w ⋅ z 1 ≥ 0 ] = ϵ P [ w ⋅ z 1 < 0 ] .
Applying Lemma B.11 completes the proof.
Below, we prove the supporting lemmas, starting with statistics about a point z ⃗ 1 \vec{z}_1 z 1 sampled uniformly at random from the half ball. Without loss of generality, we assume that it is the half ball where the first coordinate is ≥ 0 \ge0 ≥ 0 .
Notation B.7. Let μ ⃗ ( n ) = E [ z ⃗ 1 ] \vec{\mu}^{(n)}=\mathbb{E}[\vec{z}_1] μ ( n ) = E [ z 1 ] and let σ i ( n ) \sigma_i^{(n)} σ i ( n ) denote the standard deviation of the i i i th component z 1 i z_{1i} z 1 i . Let F ( n ) ( t ) F^{(n)}(t) F ( n ) ( t ) denote the cdf for the first coordinate z 11 z_{11} z 11 , and let f ( n ) ( t ) f^{(n)}(t) f ( n ) ( t ) denote the pdf. We will denote the volume of a unit n n n -dimensional ball by v n v_n v n .
Lemma B.8. The pdf f ( n ) ( t ) f^{(n)}(t) f ( n ) ( t ) for the first coordinate of z ⃗ 1 \vec{z}_1 z 1 is
f ( n ) ( t ) = 2 v n − 1 v n ( 1 − t 2 ) n − 1 2 . f^{(n)}(t)=\frac{2v_{n-1}}{v_n}(1-t^2)^{\frac{n-1}{2}}. f ( n ) ( t ) = v n 2 v n − 1 ( 1 − t 2 ) 2 n − 1 . Proof. The slice of the half ball where z 11 = t z_{11}=t z 11 = t is an ( n − 1 ) (n-1) ( n − 1 ) -dimensional ball of radius 1 − t 2 \sqrt{1-t^2} 1 − t 2 , which has volume v n − 1 ( 1 − t 2 ) n − 1 2 v_{n-1}(1-t^2)^{\frac{n-1}{2}} v n − 1 ( 1 − t 2 ) 2 n − 1 . Therefore,
f ( n ) ( t ) = A − 1 v n − 1 ( 1 − t 2 ) n − 1 2 , f^{(n)}(t)=A^{-1}v_{n-1}(1-t^2)^{\frac{n-1}{2}}, f ( n ) ( t ) = A − 1 v n − 1 ( 1 − t 2 ) 2 n − 1 , where A = ∫ 0 1 v n − 1 ( 1 − t 2 ) n − 1 2 d t A=\int_0^1v_{n-1}(1-t^2)^{\frac{n-1}{2}}\,dt A = ∫ 0 1 v n − 1 ( 1 − t 2 ) 2 n − 1 d t . This is the volume v n / 2 v_n/2 v n /2 of the half ball.
Lemma B.9. The mean μ ⃗ ( n ) \vec{\mu}^{(n)} μ ( n ) has components
μ i ( n ) = { 2 v n − 1 v n ( n + 1 ) , i = 1 , 0 , i > 1. \mu_i^{(n)}=\begin{cases}
\frac{2v_{n-1}}{v_n(n+1)}, & i=1,\\
0, & i>1.
\end{cases} μ i ( n ) = { v n ( n + 1 ) 2 v n − 1 , 0 , i = 1 , i > 1. Proof. By symmetry, μ i ( n ) = 0 \mu_i^{(n)}=0 μ i ( n ) = 0 for i > 1 i>1 i > 1 . For i = 1 i=1 i = 1 ,
μ 1 ( n ) = 2 v n − 1 v n ∫ 0 1 t ( 1 − t 2 ) n − 1 2 d t \mu_1^{(n)}=2\frac{v_{n-1}}{v_n}\int_0^1t(1-t^2)^{\frac{n-1}{2}}\,dt μ 1 ( n ) = 2 v n v n − 1 ∫ 0 1 t ( 1 − t 2 ) 2 n − 1 d t by Lemma B.8. Using the substitution s = 1 − t 2 s=1-t^2 s = 1 − t 2 ,
μ 1 ( n ) = v n − 1 v n ∫ 0 1 s n − 1 2 d s = 2 v n − 1 v n ( n + 1 ) . \mu_1^{(n)}=\frac{v_{n-1}}{v_n}\int_0^1s^{\frac{n-1}{2}}\,ds=\frac{2v_{n-1}}{v_n(n+1)}. μ 1 ( n ) = v n v n − 1 ∫ 0 1 s 2 n − 1 d s = v n ( n + 1 ) 2 v n − 1 .
Lemma B.10. The variance ( σ i ( n ) ) 2 (\sigma_i^{(n)})^2 ( σ i ( n ) ) 2 of the i i i th component of z ⃗ 1 \vec{z}_1 z 1 is
( σ i ( n ) ) 2 = { 1 n + 2 − ( μ 1 ( n ) ) 2 , i = 1 , 1 n + 2 , i > 1. (\sigma_i^{(n)})^2=\begin{cases}
\frac{1}{n+2}-(\mu_1^{(n)})^2, & i=1,\\
\frac{1}{n+2}, & i>1.
\end{cases} ( σ i ( n ) ) 2 = { n + 2 1 − ( μ 1 ( n ) ) 2 , n + 2 1 , i = 1 , i > 1. Proof. The same proof as Lemma B.1 shows that E [ z 1 i 2 ] = 1 n + 2 \mathbb{E}[z_{1i}^2]=\frac{1}{n+2} E [ z 1 i 2 ] = n + 2 1 for all i i i , because the pdf ϕ ( r ) \phi(r) ϕ ( r ) for ∥ z ⃗ 1 ∥ \lVert\vec{z}_1\rVert ∥ z 1 ∥ is the same in both the full and half ball.
Therefore, the variance is
( σ i ( n ) ) 2 = E [ z 1 i 2 ] − ( μ i ( n ) ) 2 = { 1 n + 2 − ( μ 1 ( n ) ) 2 , i = 1 , 1 n + 2 , i > 1. (\sigma_i^{(n)})^2=\mathbb{E}[z_{1i}^2]-(\mu_i^{(n)})^2=\begin{cases}
\frac{1}{n+2}-(\mu_1^{(n)})^2, & i=1,\\
\frac{1}{n+2}, & i>1.
\end{cases} ( σ i ( n ) ) 2 = E [ z 1 i 2 ] − ( μ i ( n ) ) 2 = { n + 2 1 − ( μ 1 ( n ) ) 2 , n + 2 1 , i = 1 , i > 1.
Lemma B.11. Let { z ⃗ i } i = 1 k \{\vec{z}_i\}_{i=1}^k { z i } i = 1 k be points drawn independently and uniformly at random from an n n n -dimensional half ball where the first coordinate is ≥ 0 \ge0 ≥ 0 , and let w ⃗ = ∑ i z ⃗ i ∥ ∑ i z ⃗ i ∥ \vec{w} = \frac{\sum_i \vec{z}_i}{\lVert\sum_i \vec{z}_i\rVert} w = ∥ ∑ i z i ∥ ∑ i z i . Then
P [ w ⃗ ⋅ z ⃗ 1 < 0 ] ≤ 3 4 3 n + 1 k 3 . \mathbb{P}[\vec{w}\cdot\vec{z}_1 < 0] \le\frac{3}{\sqrt[3]{4}}\frac{n+1}{\sqrt[3]{k}}. P [ w ⋅ z 1 < 0 ] ≤ 3 4 3 3 k n + 1 .
Proof. Define v ⃗ = 1 k ∑ j z ⃗ j \vec{v} = \frac{1}{k}\sum_j \vec{z}_j v = k 1 ∑ j z j . Note that w ⃗ ⋅ z ⃗ 1 < 0 \vec{w}\cdot\vec{z}_1 < 0 w ⋅ z 1 < 0 if and only if v ⃗ ⋅ z ⃗ 1 < 0 \vec{v}\cdot\vec{z}_1 < 0 v ⋅ z 1 < 0 , so P [ w ⃗ ⋅ z ⃗ 1 < 0 ] = P [ v ⃗ ⋅ z ⃗ 1 < 0 ] \mathbb{P}[\vec{w}\cdot\vec{z}_1 < 0] = \mathbb{P}[\vec{v}\cdot\vec{z}_1 < 0] P [ w ⋅ z 1 < 0 ] = P [ v ⋅ z 1 < 0 ] . First, will show that v ⃗ \vec{v} v concentrates near μ ⃗ ( n ) \vec{\mu}^{(n)} μ ( n ) . Then, we will condition on v ⃗ \vec{v} v being near μ ⃗ ( n ) \vec{\mu}^{(n)} μ ( n ) to derive an upper bound on P [ v ⃗ ⋅ z ⃗ 1 < 0 ] \mathbb{P}[\vec{v}\cdot\vec{z}_1 < 0] P [ v ⋅ z 1 < 0 ] . When v ⃗ \vec{v} v is sufficiently close to μ ⃗ ( n ) \vec{\mu}^{(n)} μ ( n ) , the conditional probability is small.
First, we bound the L ∞ L^\infty L ∞ norm of v ⃗ − μ ⃗ ( n ) \vec{v}-\vec{\mu}^{(n)} v − μ ( n ) . Let δ > 0 \delta> 0 δ > 0 . For the ℓ \ell ℓ th component,
P [ ∣ v ℓ − μ ℓ ( n ) ∣ > δ ] = 1 k ( σ ℓ ( n ) ) 2 δ 2 ≤ 1 k ( n + 2 ) δ 2 \mathbb{P}[|v_\ell-\mu_\ell^{(n)}|>\delta] = \frac{1}{k}\frac{(\sigma_\ell^{(n)})^2}{\delta^2} \le\frac{1}{k(n+2)\delta^2} P [ ∣ v ℓ − μ ℓ ( n ) ∣ > δ ] = k 1 δ 2 ( σ ℓ ( n ) ) 2 ≤ k ( n + 2 ) δ 2 1
by Chebyschev’s inequality and Lemma B.10 . Let A δ A_\delta A δ be the event that ∥ v ⃗ − μ ⃗ ( n ) ∥ ∞ ≤ δ \lVert\vec{v}-\vec{\mu}^{(n)}\rVert_\infty\le\delta ∥ v − μ ( n ) ∥ ∞ ≤ δ . Applying a union bound yields
P [ A δ c ] ≤ ∑ ℓ = 1 n P [ ∣ v ℓ − μ ℓ ( n ) ∣ > δ ] ≤ n k ( n + 2 ) δ 2 . \mathbb{P}[A_\delta^c]\le\sum_{\ell=1}^n\mathbb{P}[|v_\ell-\mu_\ell^{(n)}|>\delta]\le\frac{n}{k(n+2)\delta^2}. P [ A δ c ] ≤ ℓ = 1 ∑ n P [ ∣ v ℓ − μ ℓ ( n ) ∣ > δ ] ≤ k ( n + 2 ) δ 2 n .
Now we condition on the event A δ A_\delta A δ . For any δ > 0 \delta> 0 δ > 0 , we have that
P [ v ⃗ ⋅ z ⃗ 1 < 0 ] = P [ v ⃗ ⋅ z ⃗ 1 < 0 ∣ A δ ] P [ A δ ] + P [ v ⃗ ⋅ z ⃗ 1 < 0 ∣ A δ c ] P [ A δ c ] ≤ P [ v ⃗ ⋅ z ⃗ 1 < 0 ∣ A δ ] + P [ A δ c ] ≤ P [ v ⃗ ⋅ z ⃗ 1 < 0 ∣ A δ ] + n k ( n + 2 ) δ 2 . (15) \begin{aligned}
\mathbb{P}[\vec{v}\cdot\vec{z}_1<0] &= \mathbb{P}[\vec{v}\cdot\vec{z}_1<0\mid A_\delta]\mathbb{P}[A_\delta]+\mathbb{P}[\vec{v}\cdot\vec{z}_1<0\mid A_\delta^c]\mathbb{P}[A_\delta^c]\\
&\le\mathbb{P}[\vec{v}\cdot\vec{z}_1<0\mid A_\delta]+\mathbb{P}[A_\delta^c]\\
&\le\mathbb{P}[\vec{v}\cdot\vec{z}_1<0\mid A_\delta]+\frac{n}{k(n+2)\delta^2}. \tag*{(15)}
\end{aligned} P [ v ⋅ z 1 < 0 ] = P [ v ⋅ z 1 < 0 ∣ A δ ] P [ A δ ] + P [ v ⋅ z 1 < 0 ∣ A δ c ] P [ A δ c ] ≤ P [ v ⋅ z 1 < 0 ∣ A δ ] + P [ A δ c ] ≤ P [ v ⋅ z 1 < 0 ∣ A δ ] + k ( n + 2 ) δ 2 n . (15)
We can write
v ⃗ ⋅ z ⃗ 1 = ∑ ℓ = 1 n μ ℓ ( n ) z 1 ℓ + ∑ ℓ = 1 n ( v ℓ − μ ℓ ( n ) ) z 1 ℓ = μ 1 ( n ) z i 1 + ∑ ℓ = 1 n ( v ℓ − μ ℓ ( n ) ) z 1 ℓ , \vec{v}\cdot\vec{z}_1=\sum_{\ell=1}^n\mu_\ell^{(n)}z_{1\ell}+\sum_{\ell=1}^n(v_\ell-\mu_\ell^{(n)})z_{1\ell}=\mu_1^{(n)}z_{i1}+\sum_{\ell=1}^n(v_\ell-\mu_\ell^{(n)})z_{1\ell}, v ⋅ z 1 = ℓ = 1 ∑ n μ ℓ ( n ) z 1 ℓ + ℓ = 1 ∑ n ( v ℓ − μ ℓ ( n ) ) z 1 ℓ = μ 1 ( n ) z i 1 + ℓ = 1 ∑ n ( v ℓ − μ ℓ ( n ) ) z 1 ℓ ,
where the last equality follows by Lemma B.9 . If ∥ v ⃗ − μ ⃗ ( n ) ∥ ∞ ≤ δ \lVert\vec{v}-\vec{\mu}^{(n)}\rVert_\infty\le\delta ∥ v − μ ( n ) ∥ ∞ ≤ δ , then
∣ ∑ ℓ = 1 n ( v ℓ − μ ℓ ( n ) ) z 1 ℓ ∣ ≤ ∑ ℓ ∣ v ℓ − μ ℓ ( n ) ∣ ⋅ ∣ z 1 ℓ ∣ ≤ δ ∥ z ⃗ 1 ∥ 1 ≤ δ n ∥ z ⃗ 1 ∥ 2 ≤ δ n . \left|\sum_{\ell=1}^n(v_\ell-\mu_\ell^{(n)})z_{1\ell}\right|\le\sum_\ell|v_\ell-\mu_\ell^{(n)}|\cdot|z_{1\ell}|\le\delta\lVert\vec{z}_1\rVert_1\le\delta\sqrt{n}\lVert\vec{z}_1\rVert_2\le\delta\sqrt{n}. ℓ = 1 ∑ n ( v ℓ − μ ℓ ( n ) ) z 1 ℓ ≤ ℓ ∑ ∣ v ℓ − μ ℓ ( n ) ∣ ⋅ ∣ z 1 ℓ ∣ ≤ δ ∥ z 1 ∥ 1 ≤ δ n ∥ z 1 ∥ 2 ≤ δ n .
Therefore,
v ⃗ ⋅ z ⃗ 1 ≥ μ 1 ( n ) z i 1 − δ n \vec{v}\cdot\vec{z}_1\ge\mu_1^{(n)}z_{i1}-\delta\sqrt{n} v ⋅ z 1 ≥ μ 1 ( n ) z i 1 − δ n
when ∥ v ⃗ − μ ⃗ ( n ) ∥ ∞ ≤ δ \lVert\vec{v}-\vec{\mu}^{(n)}\rVert_\infty\le\delta ∥ v − μ ( n ) ∥ ∞ ≤ δ . This yields
P [ v ⃗ ⋅ z ⃗ 1 < 0 ∣ A δ ] ≤ P [ μ 1 ( n ) z i 1 ≤ δ n ] = F ( n ) ( δ n μ 1 ( n ) ) . \mathbb{P}[\vec{v}\cdot\vec{z}_1<0\mid A_\delta]\le\mathbb{P}[\mu_1^{(n)}z_{i1}\le\delta\sqrt{n}]=F^{(n)}\left(\frac{\delta\sqrt{n}}{\mu_1^{(n)}}\right). P [ v ⋅ z 1 < 0 ∣ A δ ] ≤ P [ μ 1 ( n ) z i 1 ≤ δ n ] = F ( n ) ( μ 1 ( n ) δ n ) .
Combining with Equation (15) gives us
P [ v ⃗ ⋅ z ⃗ 1 < 0 ] ≤ F ( n ) ( δ n μ 1 ( n ) ) + n k ( n + 2 ) δ 2 . (16) \mathbb{P}[\vec{v}\cdot\vec{z}_1<0]\le F^{(n)}\left(\frac{\delta\sqrt{n}}{\mu_1^{(n)}}\right)+\frac{n}{k(n+2)\delta^2}. \tag*{(16)} P [ v ⋅ z 1 < 0 ] ≤ F ( n ) ( μ 1 ( n ) δ n ) + k ( n + 2 ) δ 2 n . (16)
where F ( n ) F^{(n)} F ( n ) is the CDF for the first coordinate of z ⃗ 1 \vec{z}_1 z 1 . The CDF is monotonically increasing and satisfies
F ( t ) = ∫ 0 t f ( n ) ( s ) d s ≤ t max s ∈ [ 0 , 1 ] f ( n ) ( s ) . F(t)=\int_0^t f^{(n)}(s)\,ds\le t\max_{s\in[0,1]}f^{(n)}(s). F ( t ) = ∫ 0 t f ( n ) ( s ) d s ≤ t s ∈ [ 0 , 1 ] max f ( n ) ( s ) .
By Lemma B.8 , the pdf f ( n ) ( s ) f^{(n)}(s) f ( n ) ( s ) is monotonically decreasing, so
max s ∈ [ 0 , 1 ] f ( n ) ( s ) = f ( n ) ( 0 ) = 2 v n − 1 v n = ( n + 1 ) μ 1 ( n ) . \max_{s\in[0,1]} f^{(n)}(s)=f^{(n)}(0)=\frac{2v_{n-1}}{v_n}=(n+1)\mu_1^{(n)}. s ∈ [ 0 , 1 ] max f ( n ) ( s ) = f ( n ) ( 0 ) = v n 2 v n − 1 = ( n + 1 ) μ 1 ( n ) .
Therefore,
F ( n ) ( δ n μ 1 ( n ) ) ≤ n ( n + 1 ) δ . F^{(n)}\left(\frac{\delta\sqrt{n}}{\mu_1^{(n)}}\right)\leq\sqrt{n}(n+1)\delta. F ( n ) ( μ 1 ( n ) δ n ) ≤ n ( n + 1 ) δ .
Substituting into Equation (16) gives us
P [ v ⃗ ⋅ z ⃗ 1 < 0 ] ≤ n ( n + 1 ) δ + n k ( n + 2 ) δ 2 = : g ( δ ) (17) \mathbb{P}[\vec{v}\cdot\vec{z}_1<0]\leq\sqrt{n}(n+1)\delta+\frac{n}{k(n+2)\delta^2}=:g(\delta) \tag*{(17)} P [ v ⋅ z 1 < 0 ] ≤ n ( n + 1 ) δ + k ( n + 2 ) δ 2 n =: g ( δ ) (17)
for all δ \delta δ .
To finish the proof, we will optimize the choice of δ \delta δ as a function of n n n and k k k . The right-hand side g ( δ ) g(\delta) g ( δ ) approaches ∞ \infty ∞ as δ → 0 \delta\to0 δ → 0 or δ → ∞ \delta\to\infty δ → ∞ , so it achieves a minimum. Write g ( δ ) = a δ + b δ − 2 g(\delta)=a\delta+b\delta^{-2} g ( δ ) = a δ + b δ − 2 , where a = n ( n + 1 ) a=\sqrt{n}(n+1) a = n ( n + 1 ) and b = n k ( n + 2 ) b=\frac{n}{k(n+2)} b = k ( n + 2 ) n . The only critical point occurs when
δ ∗ = 2 b a 3 . \delta_*=\sqrt[3]{\frac{2b}{a}}. δ ∗ = 3 a 2 b .
At the critical point, we have
g ( δ ∗ ) = 3 4 3 a 2 b 3 = 3 4 3 n 2 ( n + 1 ) 2 ( n + 2 ) k 3 ≤ 3 4 3 ( n + 1 ) 4 ( n + 1 ) k 3 = 3 4 3 n + 1 k 3 . g(\delta_*)=\frac{3}{\sqrt[3]{4}}\sqrt[3]{a^2b}
=\frac{3}{\sqrt[3]{4}}\sqrt[3]{\frac{n^2(n+1)^2}{(n+2)k}}
\leq\frac{3}{\sqrt[3]{4}}\sqrt[3]{\frac{(n+1)^4}{(n+1)k}}
=\frac{3}{\sqrt[3]{4}}\frac{n+1}{\sqrt[3]{k}}. g ( δ ∗ ) = 3 4 3 3 a 2 b = 3 4 3 3 ( n + 2 ) k n 2 ( n + 1 ) 2 ≤ 3 4 3 3 ( n + 1 ) k ( n + 1 ) 4 = 3 4 3 3 k n + 1 .
By Equation (17) ,
P [ v ⃗ ⋅ z ⃗ 1 < 0 ] ≤ 3 4 3 n + 1 k 3 . \mathbb{P}[\vec{v}\cdot\vec{z}_1<0]\leq\frac{3}{\sqrt[3]{4}}\frac{n+1}{\sqrt[3]{k}}. P [ v ⋅ z 1 < 0 ] ≤ 3 4 3 3 k n + 1 .
Methodological details for experiments
Intrinsic dimension estimation
HP requires local dimension estimation (Step 3 of Algorithm 1). Unless otherwise stated, we use a spectral gap threshold τ \tau τ to determine the dimension. Given a neighborhood { x i j } j \{x_{ij}\}_j { x ij } j for point x i x_i x i , let λ 1 ≥ λ 2 ≥ ⋯ ≥ λ D \lambda_1\geq\lambda_2\geq\cdots\geq\lambda_D λ 1 ≥ λ 2 ≥ ⋯ ≥ λ D be the eigenvalues of the covariance matrix (for the local neighborhood) in descending order. The local dimension estimate at x i x_i x i is the minimum index m m m such that λ m / λ m + 1 > τ \lambda_m/\lambda_{m+1}>\tau λ m / λ m + 1 > τ . If no such index exists, we use dimension D D D . The default threshold is τ = 7 \tau=7 τ = 7 .
AUC values for synthetic data experiments
In § 4 , we calculated AUC values for interior vs. boundary points of disks (and n n n -dimensional balls) embedded in R D \mathbb{R}^D R D . Because the ground-truth boundary of a disk or ball has measure 0, there are not any points on the ground-truth disk (or n n n -ball) boundary, so we defined the “empirical” boundary to be the set of points with norm larger than a threshold τ B \tau_B τ B and the “empirical” interior to be the set of points with norm smaller than a threshold τ I \tau_I τ I . We used τ B = .95 \tau_B=.95 τ B = .95 and τ I = .8 \tau_I=.8 τ I = .8 in § 4 . For the disks embedded in R D \mathbb{R}^D R D , the norm was calculated with respect to the first two coordinates (the plane that contains the disk), and for the n n n -dimensional balls in R n \mathbb{R}^n R n , we used the n n n -dimensional Euclidean norm. In this section, we present the AUC values for different choices of τ B ∈ { .91 , … , .98 } \tau_B\in\{.91,\ldots,.98\} τ B ∈ { .91 , … , .98 } . Our conclusions do not qualitatively change when we use a different threshold τ B \tau_B τ B .
In Figure 5 , we considered the AUC values for 2D disks embedded in R D \mathbb{R}^D R D with increasing ambient dimension D D D , at fixed boundary threshold τ B = .95 \tau_B=.95 τ B = .95 . In Figure 20 , we show the AUC values for varying thresholds τ B ∈ { .91 , … , .98 } \tau_B\in\{.91,\ldots,.98\} τ B ∈ { .91 , … , .98 } . At each threshold τ B \tau_B τ B , the DU method performs best, followed by HP, followed by LoDD.
In Figure 7 (B), we calculated AUC values for 2D disks embedded in R 3 \mathbb{R}^3 R 3 with increasing noise σ ∈ [ .01 , .05 ] \sigma\in[.01,.05] σ ∈ [ .01 , .05 ] , at fixed boundary threshold τ B = .95 \tau_B=.95 τ B = .95 . In Figure 21 , we show the AUC values for varying thresholds τ B ∈ { .91 , … , .98 } \tau_B \in\{.91,\ldots,.98\} τ B ∈ { .91 , … , .98 } . For τ B ≥ .95 \tau_B \geq.95 τ B ≥ .95 , the relative performance of each method is the same as when τ = .95 \tau= .95 τ = .95 , where the hyperplane method with fixed dimension does best, closely followed by DU. For .91 ≤ τ B ≤ .94 .91 \leq\tau_B \leq.94 .91 ≤ τ B ≤ .94 , DU outperforms every method at the lowest noise levels σ = .01 \sigma= .01 σ = .01 and σ = .02 \sigma= .02 σ = .02 .
Figure 21. At each noise level σ \sigma σ , we sample a point cloud from a 2D disk in R 3 \mathbb{R}^{3} R 3 with isotropic Gaussian noise. Each point cloud has N = 10 , 000 N = 10,000 N = 10 , 000 points, and we use neighborhood size k = 100 k = 100 k = 100 . Interior points are defined to be points with norm less than .8 .8 .8 , and boundary points are defined to be points with norm larger than τ B \tau_B τ B , which increases from τ B = .91 \tau_B = .91 τ B = .91 to τ B = .98 \tau_B = .98 τ B = .98 across the panels. In each panel, we plot the AUC values as a function of noise level σ \sigma σ for each of the three methods.
In Figure 7 (C), we calculated AUC values for 2D disks embedded in R D \mathbb{R}^{D} R D with increasing dimension D D D and fixed noise level σ = .05 \sigma= .05 σ = .05 , at fixed boundary threshold τ B = .95 \tau_B = .95 τ B = .95 . In Figure 22 , we show the AUC values for varying thresholds τ B ∈ { .91 , … , .98 } \tau_B \in\{.91,\ldots,.98\} τ B ∈ { .91 , … , .98 } . At all threshold τ B \tau_B τ B , the hyperplane method with fixed dimension performs best, followed by DU, followed for LoDD, followed by BEPS and the hyperplane method with a spectral gap threshold condition.
Figure 22. At each ambient dimension D D D , we sample a point cloud from a 2D disk in R D \mathbb{R}^{D} R D with isotropic Gaussian noise σ = .05 \sigma= .05 σ = .05 . Each point cloud has N = 10 , 000 N = 10,000 N = 10 , 000 points, and we use neighborhood size k = 100 k = 100 k = 100 . Interior points are defined to be points with norm less than .8, and boundary points are defined to be points with norm larger than τ B \tau_B τ B , which increases from τ B = .91 \tau_B = .91 τ B = .91 to τ B = .98 \tau_B = .98 τ B = .98 across the panels. In each panel, we plot the AUC values as a function of ambient dimension D D D for each of the four methods.
Spatial Transcriptomics
Data preprocessing
The raw data has 741 spatial spots and 27,984 genes.
Quality control. We do gene quality control by discarding genes that are detected at fewer than 3 spots. This results in the removal of 12,372 genes.
Library-size normalization. We normalize each spot to a common total count of 10,000. More precisely, if x i g x_{ig} x i g is the number of transcripts of gene g g g at spot i i i , the library size at spot i i i is L i = ∑ g x i g L_i = \sum_g x_{ig} L i = ∑ g x i g . We rescale the counts x i g : = ( x i g / L i ) × 10 , 000 x_{ig} := (x_{ig}/L_i) \times10,000 x i g := ( x i g / L i ) × 10 , 000 so that each spot has library size 10,000.
Log transform. For each spot i i i and gene g g g , we apply a log transform x i g : = log ( 1 + x i g ) x_{ig} := \log(1 + x_{ig}) x i g := log ( 1 + x i g ) , where x i g x_{ig} x i g is the output from the library-size normalization step.
Highly variable genes. We select the 3,000 most highly-variable genes, discarding the rest.
Scaling. We normalize each gene so that it has mean 0 and variance 1 by mapping each x i g x_{ig} x i g to its z z z -score. More precisely, if μ g \mu_g μ g and σ g \sigma_g σ g are the mean and standard deviation for gene g g g expression across spots, we calculate x i g : = ( x i g − μ g ) / σ g x_{ig} := (x_{ig} - \mu_g)/\sigma_g x i g := ( x i g − μ g ) / σ g . We clip values at max z z z -score 10, i.e., x i g : = min ( x i g , 10 ) x_{ig} := \min(x_{ig}, 10) x i g := min ( x i g , 10 ) , so that no single gene dominates the PCA step below.
PCA dimension reduction. Let x i = ( x i g ) g x_i = (x_{ig})_g x i = ( x i g ) g be the gene expression values at spot i i i after the preprocessing steps above. We use PCA to reduce { x i } i \{x_i\}_i { x i } i to 30 dimensions.
Neighborhood calculation for the boundary detection algorithms
Both HP and DU require a local neighborhood at each point (see lines 2 of Algorithm 1 and Algorithm 2, respectively). We define the neighborhoods as follows.
For each spot, we concatenate the 30-dimensional PCA gene expression coordinates with the 2D spatial coordinates, yielding a 32-dimensional vector at each spot. The gene and spatial coordinates have very different scales, so to determine the nearest neighbors of each spot, it does not make sense to naively calculate Euclidean distance in R 32 \mathbb{R}^{32} R 32 .
Instead, we consider spatial and gene distance independently. For integer k ′ k' k ′ , let N g ( k ′ , i ) N^{g}(k', i) N g ( k ′ , i ) denote the nearest k ′ k' k ′ neighbors of the i i i th spot with respect to gene coordinates (Euclidean distance in R 30 \mathbb{R}^{30} R 30 ), and let N s ( k ′ , i ) N^{s}(k', i) N s ( k ′ , i ) denote the nearest k ′ k' k ′ neighbors of the i i i th spot with respect to spatial coordinates (Euclidean distance in R 2 \mathbb{R}^{2} R 2 ). At neighborhood size parameter k k k , we define the neighborhood of spot i i i to be the intersection
N g ( k ′ , i ) ∩ N s ( k ′ , i ) N^{g}(k', i) \cap N^{s}(k', i) N g ( k ′ , i ) ∩ N s ( k ′ , i )
for the minimum integer k ′ k' k ′ such that the intersection has size k k k .
LLM Activation Geometry
In Section 6, we applied our boundary detection algorithms to study LLM activation geometry. The results for Pythia-2.8B were shown in Figure 10 , and the results for Llama-3.1-8B were shown in Figure 19 . Here, we detail our methodology.
Data set
We stream documents from the C4 (English) data set ((Raffel et al., 2020)), keeping those that have at least 400 characters excluding whitespace. For each document and each k ∈ { 15 , 20 , … , 150 } k \in\{15, 20, \ldots, 150\} k ∈ { 15 , 20 , … , 150 } , we remove all newlines and then re-insert them every ≤ k \leq k ≤ k characters, breaking at the nearest word boundary ≤ k \leq k ≤ k so that each line has at most k k k characters.4 We continue extracting documents from C4 until we reach at least 250,000 non-newline tokens in total. This is satisfied by the first 28 documents. (See Table 2 for total token counts for Pythia-2.8B and Llama-3.1-8B.) This process yields 28 documents × \times × 28 widths = 784 total sequences. We cap each sequence at 512 tokens, including newlines.
Table 2. Number of tokens extracted for each model.
Each non-newline token is labeled by its character position i i i and line width w ∈ { 15 , 20 , … , 150 } w \in\{15, 20, \ldots, 150\} w ∈ { 15 , 20 , … , 150 } . The character position of a token is defined to be the number of characters used from the beginning of the line through the end of the token.
Models and layer selection
We test two models, Pythia-2.8B and Llama-3.1-8B, which have dimensions D = 2560 D = 2560 D = 2560 and D = 4096 D = 4096 D = 4096 , respectively. Both models have 32 layers. For each token in our data set, we extract the residual-stream activations at layer 4 in both models. We chose layer 4 after visual inspection of the averaged character-counting manifold for candidate layers 4, 11, 16, 24, and 29.
Averaged manifold
For each ( i , w ) (i, w) ( i , w ) , we average the residual-stream vectors at layer 4 for tokens with character position i i i and line width w w w . We discard ( i , w ) (i, w) ( i , w ) if there are fewer than 5 tokens with position i i i and line width w w w . This gives us N = 2 , 311 N = 2,311 N = 2 , 311 points for the Pythia-2.8B manifold and N = 2 , 335 N = 2,335 N = 2 , 335 points for the Llama-3.1-8B manifold.5
Boundary detection on the averaged manifold
First, we use PCA to reduce the averaged manifold (N ≈ 2300 N \approx2300 N ≈ 2300 for each model) to 30 dimensions. Then, we run the DU method and the hyperplane method with fixed dimension 2, both with neighborhood size k = 100 k = 100 k = 100 . (The manifold is intrinsically 2-dimensional because it is parameterized by character position i i i and line width 2.)
The hyperplane method yields a vector w ⃗ \vec{w} w , in local PCA coordinates, at each point, which we lift to a vector w ⃗ a m b \vec{w}_{\mathrm{amb}} w amb in the ambient 30-dimensional PCA basis. The DU method gives us a vector v ⃗ i ∈ R 30 \vec{v}_i \in\mathbb{R}^{30} v i ∈ R 30 at each point. In Figure 10 and Figure 19 , we show the vectors for points whose boundary scores are in the top decile.
Boundary detection on the un-averaged, per-token manifold
Instead of averaging the residual-stream activations for each ( i , w ) (i, w) ( i , w ) , we consider the entire point cloud of size size N ≈ 250,000 N \approx250{,}000 N ≈ 250 , 000 (one point per token). Again, we use PCA to reduce to 30 dimensions. Then, we run the DU method and the hyperplane method with neighborhood size k = 100 k = 100 k = 100 . We use a spectral gap threshold condition (with default threshold τ = 7 \tau= 7 τ = 7 ) for the hyperplane method instead of fixing dimension 2 because the intrinsic dimension is no longer 2. At each ( i , w ) (i, w) ( i , w ) , we average the boundary scores for all tokens at position i i i within a line of width w w w .
3D visualization
For both models, the first principal component of the averaged manifold is dominated by a few outliers, so in Figure 10 and Figure 19 , we plot in PC2-PC3-PC4 coordinates.
Other boundary detection variants
Both CO (Wang et al. (2018)) and BEPS (Li & Maguire [12 ] ) use the vector v ⃗ i : = 1 k ∑ j x i j − x i ∥ x i j − x i ∥ \vec{v}_i := \frac{1}{k}\sum_j \frac{x_{ij}-x_i}{\lVert x_{ij}-x_i\rVert} v i := k 1 ∑ j ∥ x ij − x i ∥ x ij − x i at each point x i x_i x i , where { x i j } \{x_{ij}\} { x ij } are its k k k nearest neighbors. The CO score at point x i x_i x i is
k 2 ∑ j = 1 k m i − 1 m j − 1 v ⃗ i ⋅ v ⃗ j , k^2 \sum_{j=1}^{k} m_i^{-1}m_j^{-1}\vec{v}_i \cdot\vec{v}_j, k 2 j = 1 ∑ k m i − 1 m j − 1 v i ⋅ v j ,
where m i − 1 = ∑ j ∥ x i j − x i ∥ m_i^{-1} = \sum_j \lVert x_{ij}-x_i\rVert m i − 1 = ∑ j ∥ x ij − x i ∥ . The CO score is high on low-density points, regardless of whether they are interior or boundary points, so the CO method struggles with non-uniform density. The difference between our DU method and the CO method is that we removed the term m i − 1 m j − 1 m_i^{-1}m_j^{-1} m i − 1 m j − 1 and normalized the score so that it is always less than or equal to 1.
We tested several other boundary detection variants (see Table 3 ), with results shown in Figure 23 . Each variant uses either the vector v ⃗ i \vec{v}_i v i or a slightly different vector u ⃗ i : = ∑ j ( x i j − x i ) \vec{u}_i := \sum_j(x_{ij}-x_i) u i := ∑ j ( x ij − x i ) where the neighbor-displacement vectors are not normalized, and then each variant has a score that is constructed from the chosen vector. The cosine variant uses v ⃗ i \vec{v}_i v i but measures the cosine between v ⃗ i \vec{v}_i v i and ∑ j v ⃗ j \sum_j \vec{v}_j ∑ j v j instead of taking the dot product; this variant isolates the effect of neighbor alignment between vectors, which was the rationale in Wang et al. (2018). We find that the cosine variant works poorly because the vectors of all neighbors tend to be similar due to the fact that their neighborhoods are similar, regardless of whether they are on a boundary or not. The magnitude variant ∥ v ⃗ i ∥ \lVert\vec{v}_i\rVert ∥ v i ∥ works almost as well as DU on disks and n n n -balls, but as discussed in § 3 , the DU variant is more robust to noise. The two variants that use u ⃗ i \vec{u}_i u i do not work well with non-uniform density because ∥ u ⃗ i ∥ \lVert\vec{u}_i\rVert ∥ u i ∥ is large when the density is low. The DU variant was the best overall performer across varying noise levels, varying dimension, and non-uniform density.
Table 3. Other boundary-detection methods that we tested.
Figure 23. We compare the variants from Table 3 . (A) Scores on the non-uniformly sampled disk from Figure 12 with N = 10,000 N = 10{,}000 N = 10 , 000 points and neighborhood size k = 100 k = 100 k = 100 . AUROC scores are for boundary points (norm > .98 > .98 > .98 ) vs deep interior points (norm < .23 < .23 < .23 ), like in Figure 12 . AUROC scores for boundary vs. interior points on 2D disks and n n n -balls, where interior and boundary points are defined as having norms < .8 < .8 < .8 and > .95 > .95 > .95 , respectively.