Introduction
Feature extraction is a fundamental problem in modern data science, particularly in the analysis of high-dimensional data. Classical linear methods such as principal component analysis (PCA) [38 ] are natural starting points when the dominant variability of the data can be well represented by a low-dimensional linear subspace. However, many modern datasets exhibit intrinsically nonlinear geometric structure that cannot be adequately captured by linear representations alone. To address this challenge, a large class of manifold learning and nonlinear spectral embedding methods has been developed, including kernel PCA [57 ] , Isomap [63 ] , locally linear embedding [55 ] , Laplacian eigenmaps [6 ] , diffusion maps [17 ] , vector diffusion maps [61 ] , t-SNE [66 ] , and UMAP [47 ] . More recently, neural-network-based approaches such as autoencoders [37 ] , denoising autoencoders [69 ] , and variational autoencoders [41 ] have provided additional flexible frameworks for nonlinear representation learning. For downstream tasks such as classification, clustering, and visualization, informative low-dimensional representations are often essential for revealing meaningful structure and enabling reliable statistical analysis.
Existing manifold learning and spectral embedding methods are typically most effective when the observed geometry still reliably reflects the underlying signal structure, such as in clean or signal-dominated settings. In many modern high-dimensional applications, however, the ambient noise can substantially distort pairwise distances, affinities, and neighborhood relations before the final embedding step is even performed. As a result, the observed geometry itself may no longer provide a reliable representation of the latent nonlinear structure. For example, in biomedical imaging such as cryo-electron microscopy, low-dose acquisition often leads to extremely low signal-to-noise ratios [5 ] . At the same time, signals in such applications often possess additional low-complexity structure, such as sparse or compressible representations [51 ] . This additional structure creates an opportunity to partially recover or stabilize the underlying geometry before applying nonlinear spectral embedding methods.
Motivated by these observations, in this paper, we study feature extraction under the signal-plus-noise model
x i = s i + z i ∈ R p , 1 ≤ i ≤ n , (1) \mathbf{x}_i = \mathbf{s}_i + \mathbf{z}_i \in\mathbb{R}^{p}, \qquad1 \le i \le n, \tag*{(1)} x i = s i + z i ∈ R p , 1 ≤ i ≤ n , (1)
where s i \mathbf{s}_i s i denotes the latent signal component and z i \mathbf{z}_i z i denotes the additive noise component. We focus on the setting where the latent signal has nonlinear geometric structure and admits a sparse or compressible representation. We propose an adaptive sparsity-aware projection-assisted spectral embedding method for this problem. The main idea is to first perform an adaptive projection step to denoise the pairwise distances and then apply spectral embedding to the projected data. We first summarize some relevant related works in § 1.1 and then provide an overview of our method and contribution in § 1.2 .
Some Related Works
The behavior of manifold learning and spectral embedding methods has been extensively studied in fixed-dimensional settings. In the noiseless case, a substantial theoretical literature establishes the convergence of graph- and kernel-based constructions to their population or continuum counterparts; see, for example, [7 , 36 , 70 , 64 , 34 , 65 , 26 , 15 , 43 ] . Related analyses have also been developed for specific methods and models, including continuum Isomap [8 ] , locally linear embedding [74 ] , and vector diffusion maps and connection Laplacians [61 , 62 ] . In parallel, a number of robust variants have been proposed in fixed-dimensional signal-plus-noise settings, including perturbation analysis of graph-Laplacian eigenvectors for denoising [48 ] , robust locally linear embedding [13 ] , and robust kernel Isomap [16 ] . Collectively, these works show that moderate noise can often be accommodated when the observed geometry still reflects the latent signal structure with reasonable fidelity.
The situation becomes substantially more challenging in high-dimensional noisy settings, where the main difficulty is not only the perturbation of the final embedding step, but also the distortion of the geometry itself. High-dimensional noise may induce concentration effects and geometric artifacts, so that distances, affinities, and neighborhood relations constructed from the observations become much less informative [1 , 28 , 27 , 10 ] . Nevertheless, when the signal dominates the noise, recent works have shown that direct graph- and kernel-based spectral methods can still recover meaningful low-dimensional structure under suitable conditions. These include kernel spectral embedding with adaptive bandwidth selection [20 ] , robustness analysis for connection graph Laplacians under additive noise [29 ] , graph-Laplacian analysis under high-dimensional noise [22 ] , landmark-based spectral embedding [59 ] , and multiview sensor-fusion methods [23 , 21 ] . Taken together, these results provide theoretical justification for nonlinear spectral embedding in certain high-dimensional signal-plus-noise regimes, provided that the underlying geometry remains sufficiently informative and that the bandwidth is properly chosen.
Much less is understood in low-SNR regimes, where the noise dominates the signal and the observed geometry may no longer provide a reliable basis for direct graph or kernel construction. In this setting, additional low-complexity structure becomes particularly important. For linear methods, sparsity has been widely used to identify informative directions in high-dimensional noisy data through sparse PCA and related approaches. Early sparse PCA methods include penalized regression, regularized low-rank approximation, and penalized matrix decomposition [77 , 60 , 73 ] . Related transform-domain reduction and feature-selection ideas before downstream low-dimensional analysis appear in [71 , 32 , 49 ] , while selection-based methods for sparse or compressible signals in prescribed bases are studied in [40 ] . Subsequent developments include augmented sparse PCA [52 ] , two-stage coordinate-selection procedures [9 ] , and adaptive sparse principal subspace estimation [12 ] . However, these methods are primarily designed for linear covariance structures, and much less is known about how sparsity can be used to stabilize nonlinear geometric structure for manifold learning and spectral embedding in high-dimensional low-SNR settings.
To address this gap, we propose an adaptive sparsity-aware projection-assisted spectral embedding method for feature extraction from high-dimensional noisy data with nonlinear structures under sparse or compressible representations. The key idea is to use adaptive projection to denoise the pairwise geometry before applying nonlinear spectral embedding. Our approach applies across a broad range of SNR levels, while being particularly useful when the noise dominates the signal. An overview of our method and contributions is given in § 1.2 .
An Overview of Main Results and Contributions
Figure 1.1 illustrates the overall workflow of the proposed framework. As in [57 , 6 , 17 , 61 , 20 ] , our algorithm relies on pairwise distances to construct an affinity matrix for spectral embedding. In high-dimensional noisy settings, however, the main challenge is that these pairwise distances may already become unreliable before the final eigendecomposition is performed. In particular, high-dimensional asymptotics reveal rigid geometric effects in which observations tend to become nearly equidistant or nearly orthogonal [35 , 2 ] , while nearest-neighbor structure may become increasingly unreliable through hubness and related distortions [54 , 3 ] . Moreover, high-dimensional noise can substantially alter the effective kernel geometry extracted from the observations [27 ] . Consequently, the main issue is not only whether the spectral embedding step itself is stable, but also whether the input geometry still faithfully reflects the latent signal structure. The goal of our method is thus to denoise the pairwise geometry before applying spectral embedding.
Figure 1.1. Overview of the proposed adaptive sparsity-aware projection-assisted spectral embedding framework. The method first performs adaptive projection to denoise pairwise geometry in high-dimensional noisy observations and then applies spectral embedding to the projected data to recover the latent nonlinear structure.
To address this difficulty, we exploit additional sparsity structure in the latent signal. When the signal admits a sparse representation in a prescribed basis, most of its energy is concentrated on a relatively small number of directions, while the ambient noise is more diffusely spread across coordinates. This separation between concentrated signal energy and diffuse noise motivates an adaptive geometry-denoising step prior to manifold learning. Specifically, we perform a preliminary data-adaptive projection step in which empirically energetic directions are retained and noise-dominated ones are discarded, similar in spirit to earlier transform-domain reduction and feature-screening ideas; see, for example, [71 , 32 , 49 , 40 ] . The resulting projection stabilizes the pairwise geometry before subsequent spectral analysis.
Based on this idea, we propose an adaptive sparsity-aware projection-assisted spectral embedding method in § 2 . The overall procedure consists of two main steps. First, we construct a data-driven projection by selecting directions in a prescribed basis so as to reduce the effect of noise before pairwise distances are computed. The key methodological contribution lies in this step: we introduce an empirical-energy-based thresholding rule (Algorithm 1) that is fully data-driven and, as shown in Proposition 3.4 , adapts to the unknown underlying SNR and sparsity structure of the data. Intuitively, the procedure retains directions whose empirical energies remain distinguishable from the ambient noise level, while filtering out directions dominated by noise. As shown in Theorem rem 3.6, the projection denoises the pairwise geometry of the data and makes subsequent spectral analysis more reliable.
Second, after this denoising projection step, we apply a spectral embedding method with bandwidth selection in the spirit of [20 ] to the projected data. This produces a unified project-then-embed framework that combines adaptive geometry recovery with nonlinear spectral embedding. We show in Theorem 3.8 that, after normalization, the resulting embeddings converge to the eigenfunctions of an integral operator associated with the clean latent signal. Although we adopt [20 ] here for concreteness and tractability, the second step can in principle be replaced by other spectral embedding methods, for example, diffusion-based procedures such as Laplacian eigenmaps [6 ] , diffusion maps [17 ] , and vector diffusion maps [61 ] ; we leave these extensions for future work.
Our theoretical analysis in § 3 shows that the proposed framework applies across a broad range of SNR levels and remains effective even in low-SNR regimes where the noise dominates the signal and direct geometric construction may fail. In addition to the theoretical analysis, § 4 and § 5 compare the empirical performance of the proposed method with [55 , 4 , 17 , 37 , 69 , 20 ] through simulation studies and real data examples. The results demonstrate that the proposed geometry-denoising framework substantially improves the robustness of nonlinear feature extraction in high-dimensional noisy settings, particularly in low-SNR regimes.
Organization and Notations
The rest of the paper is organized as follows. In § 2 , we introduce the proposed method. In § 3 , we state the main assumptions and establish the theoretical guarantees. § 4 and § 5 present simulation studies and real data analyses. Additional simulation and real data results are provided in Appendices § 6 and § 7 , respectively. Supplementary algorithms are given in Appendix § 9 , and technical proofs are deferred to Appendix § 8 .
Conventions. We write C C C , C 0 C_0 C 0 , etc. for generic large positive constants whose values may change from line to line, and ε \varepsilon ε , δ \delta δ , etc. for generic small positive constants. We use ⌊ a ⌋ \lfloor a \rfloor ⌊ a ⌋ for the greatest integer less than or equal to a a a . When a constant depends on a parameter a a a , we indicate this by C ( a ) C(a) C ( a ) or C a C_a C a . For sequences { a n } \{a_n\} { a n } and { b n } \{b_n\} { b n } depending on n n n , a n = O ( b n ) a_n = O(b_n) a n = O ( b n ) means ∣ a n ∣ ≤ C ∣ b n ∣ |a_n| \le C|b_n| ∣ a n ∣ ≤ C ∣ b n ∣ for some constant C > 0 C > 0 C > 0 , while a n = o ( b n ) a_n = o(b_n) a n = o ( b n ) means ∣ a n ∣ ≤ c n ∣ b n ∣ |a_n| \le c_n|b_n| ∣ a n ∣ ≤ c n ∣ b n ∣ for some positive sequence c n ↓ 0 c_n \downarrow0 c n ↓ 0 as n → ∞ n \to\infty n → ∞ . We also use a n ≲ b n a_n \lesssim b_n a n ≲ b n to mean a n = O ( b n ) a_n = O(b_n) a n = O ( b n ) , a n ≳ b n a_n \gtrsim b_n a n ≳ b n to mean b n = O ( a n ) b_n = O(a_n) b n = O ( a n ) , and a n ≍ b n a_n \asymp b_n a n ≍ b n to mean both a n = O ( b n ) a_n = O(b_n) a n = O ( b n ) and b n = O ( a n ) b_n = O(a_n) b n = O ( a n ) . The probabilistic analogues are a n = O P ( b n ) a_n = O_{\mathbb{P}}(b_n) a n = O P ( b n ) and a n = o P ( b n ) a_n = o_{\mathbb{P}}(b_n) a n = o P ( b n ) .
Bold lowercase letters such as x , y \mathbf{x}, \mathbf{y} x , y denote vectors, while bold uppercase letters such as K \mathbf{K} K denote matrices. Calligraphic letters such as K \mathcal{K} K and L \mathcal{L} L denote operators or function spaces, and plain letters such as f , g f, g f , g denote generic functions. For norms, ∥ x ∥ 2 = ( ∑ j = 1 p ∣ x j ∣ 2 ) 1 / 2 \|\mathbf{x}\|_2 = \left(\sum_{j=1}^{p}|x_j|^2\right)^{1/2} ∥ x ∥ 2 = ( ∑ j = 1 p ∣ x j ∣ 2 ) 1/2 denotes the ℓ 2 \ell_2 ℓ 2 -norm of x = ( x 1 , … , x p ) T ∈ R p \mathbf{x} = (x_1,\ldots,x_p)^{\mathsf{T}} \in\mathbb{R}^p x = ( x 1 , … , x p ) T ∈ R p . We denote by ∥ L ∥ \|\mathcal{L}\| ∥ L ∥ and ∥ A ∥ \|\mathbf{A}\| ∥ A ∥ the operator norms of an operator L \mathcal{L} L and a matrix A \mathbf{A} A , respectively. For a matrix A \mathbf{A} A , let Π A \mathbf{\Pi}_{\mathbf{A}} Π A denote the orthogonal projection onto Col ( A ) \operatorname{Col}(\mathbf{A}) Col ( A ) .
Methodology
In this section, we introduce the proposed methodology. The overall framework consists of two main stages: an adaptive projection step for denoising pairwise geometry, followed by nonlinear spectral embedding on the projected data. We first construct an adaptive sparse projection to denoise the pairwise geometry of the observed high-dimensional data in § 2.1 . We then apply a spectral embedding method to the projected samples in § 2.2 . Finally, in § 2.3 , we describe how the resulting embeddings can be used for downstream tasks such as clustering and prediction. For notational convenience, throughout the paper we adopt the convention that for a positive integer n n n , [ n ] = { 1 , 2 , … , n } [n]=\{1,2,\ldots,n\} [ n ] = { 1 , 2 , … , n } .
Adaptive Sparse Projection
To denoise the pairwise geometry, we first construct a data-driven projection from the observed samples { x i } i ∈ [ n ] ⊂ R p \{x_i\}_{i\in[n]}\subset\mathbb{R}^p { x i } i ∈ [ n ] ⊂ R p , which is the key step in our methodology. Let W = { w j } j ∈ [ p ] \mathbf{W}=\{w_j\}_{j\in[p]} W = { w j } j ∈ [ p ] be a prescribed orthonormal basis of R p \mathbb{R}^p R p , for example, the Haar wavelet basis [18 ] . In this paper, we may take W \mathbf{W} W to be a wavelet basis, since many structured signals have local features and are therefore represented by a relatively small number of large coefficients in wavelet bases [46 , 24 , 25 ] . For each 1 ≤ i ≤ n 1\leq i\leq n 1 ≤ i ≤ n and 1 ≤ j ≤ p 1\leq j\leq p 1 ≤ j ≤ p , define
y i j = ( x i − x ˉ ) T w j , (2) y_{ij}=(x_i-\bar{x})^{\mathsf{T}}w_j, \tag*{(2)} y ij = ( x i − x ˉ ) T w j , (2)
where x ˉ = n − 1 ∑ i x i \bar{x}=n^{-1}\sum_i x_i x ˉ = n − 1 ∑ i x i , and compute the empirical energy of the j j j -th direction by
E j = 1 n ∑ i = 1 n y i j 2 . (3) E_j=\frac{1}{n}\sum_{i=1}^{n}y_{ij}^{2}. \tag*{(3)} E j = n 1 i = 1 ∑ n y ij 2 . (3)
We then order { E j } j ∈ [ p ] \{E_j\}_{j\in[p]} { E j } j ∈ [ p ] as E ( 1 ) ≥ E ( 2 ) ≥ ⋯ ≥ E ( p ) E_{(1)}\geq E_{(2)}\geq\cdots\geq E_{(p)} E ( 1 ) ≥ E ( 2 ) ≥ ⋯ ≥ E ( p ) . The basic idea is to retain the basis directions corresponding to the K K K largest empirical energies.
A central issue in this step is the choice of the retained dimension K K K . If K K K is too large, we retain too many noise-dominated directions; if K K K is too small, we may discard directions that still contain useful signal information. To address this issue, we choose K K K in a data-driven way based on the ordered empirical energies. More specifically, we use σ ^ 2 \hat{\sigma}^{2} σ ^ 2 , computed as the average of the smallest s s s empirical energies, as an estimate of the noise variance, and choose K K K as the largest j j j such that E ( j ) ≥ ( 1 + τ ) σ ^ 2 E_{(j)}\geq(1+\tau)\hat{\sigma}^{2} E ( j ) ≥ ( 1 + τ ) σ ^ 2 , where τ \tau τ is a prespecified small positive constant. The role of s s s is to ensure that σ ^ 2 \hat{\sigma}^{2} σ ^ 2 provides a reliable estimate of the noise level. In practice, s s s can be chosen as a small fixed integer. As long as s s s is fixed, it does not affect the theoretical order of K K K under the conditions of Proposition 3.4 . The parameter τ \tau τ controls how conservative the cutoff is: a larger τ \tau τ leads to a smaller K K K , while a smaller τ \tau τ leads to a larger K K K . However, changing τ \tau τ mainly affects directions whose signal energies are comparable to the noise level, which typically carry only a small fraction of the signal information. By contrast, clearly signal-dominated directions remain selected and clearly noise-dominated directions remain excluded. Theoretically, each fixed τ > 0 \tau>0 τ > 0 affects the order of K K K only through multiplicative constants under the conditions of Proposition 3.4 . In this paper, we fix τ = 0.5 \tau=0.5 τ = 0.5 in our experiments. The selection of K K K is summarized in Algorithm 1.
Remark 2.1. The selected projection dimension K K K is controlled jointly by the relative strength between the signal and the noise and by how sparse the signal is in the chosen basis. When the relative strength between the signal and the noise is larger, more basis directions have empirical Algorithm 1 Adaptive selection of the projection dimension K K K
Inputs: Ordered empirical energies { E ( j ) } j = 1 p \{E_{(j)}\}_{j=1}^{p} { E ( j ) } j = 1 p , a small positive fixed number τ \tau τ , and a small fixed integer s s s .
Step one: Compute the estimated noise variance
σ ^ 2 = 1 s ∑ j = 1 s E ( p + 1 − j ) . \widehat{\sigma}^{2}=\frac{1}{s}\sum_{j=1}^{s}E_{(p+1-j)}. σ 2 = s 1 j = 1 ∑ s E ( p + 1 − j ) .
Step two: Compute
K = max { j : E ( j ) ≥ ( 1 + τ ) σ ^ 2 } . (4) K=\max\left\{j:E_{(j)}\geq(1+\tau)\widehat{\sigma}^{2}\right\}. \tag*{(4)} K = max { j : E ( j ) ≥ ( 1 + τ ) σ 2 } . (4)
Output: The selected projection dimension K K K .
energies that remain clearly above the noise level, and the selected dimension becomes larger. By contrast, when relative strength between the signal and the noise is smaller, fewer directions can be reliably distinguished and the selected dimension becomes smaller. Likewise, when the signal is more sparse in the basis, its energy is concentrated on fewer directions, which creates a sharper separation between informative and uninformative directions and makes the choice of K K K smaller. We will illustrate these effects on K K K in Figure 4.6 in § 4 .
Figure 4.6. Selected projection dimension K K K versus sparsity parameter q q q under different σ \sigma σ in the two-disjoint-spheres model. The reported results are based on 250 repetitions.
Once K K K is selected, we retain the K K K basis directions corresponding to the K K K largest empirical energies, and denote the set of their indices by I K \mathcal{I}_K I K . We construct the projection matrix as
P = ( w j ) j ∈ I K ∈ R p × K . (5) \mathrm{P}=(w_j)_{j\in\mathcal{I}_K}\in\mathbb{R}^{p\times K}. \tag*{(5)} P = ( w j ) j ∈ I K ∈ R p × K . (5)
This projection step produces the lower-dimensional representation that will be used in the subsequent spectral embedding procedure.
Spectral Embedding after Projection
Once the projection matrix P \mathrm{P} P in (5) is constructed, we project the original observations into the selected lower-dimensional subspace and then apply a kernel spectral embedding procedure, in the spirit of [20 ] , to the projected data. More specifically, for each i = 1 , … , n i=1,\ldots,n i = 1 , … , n , define
y i = P T ( x i − x ˉ ) ∈ R K . (6) y_i=\mathrm{P}^{\mathsf{T}}(x_i-\bar{x})\in\mathbb{R}^{K}. \tag*{(6)} y i = P T ( x i − x ˉ ) ∈ R K . (6)
Instead of constructing affinities directly from the original high-dimensional observations, we construct them from the projected samples { y i } i = 1 n \{y_i\}_{i=1}^{n} { y i } i = 1 n , whose pairwise geometry is expected to be more robust after the adaptive projection step.
The embedding procedure is then applied to y i y_i y i in (6) . Given a bandwidth parameter h n h_n h n , we construct the kernel matrix K n = ( K ( i , j ) ) K_n=(K(i,j)) K n = ( K ( i , j )) as
K ( i , j ) = exp ( − ∥ y i − y j ∥ 2 2 h n ) , 1 ≤ i , j ≤ n . (7) K(i,j)=\exp\left(-\frac{\lVert y_i-y_j\rVert_2^2}{h_n}\right),\qquad1\leq i,j\leq n. \tag*{(7)} K ( i , j ) = exp ( − h n ∥ y i − y j ∥ 2 2 ) , 1 ≤ i , j ≤ n . (7)
and compute its eigendecomposition
1 n K n = U Λ U T , (8) \frac{1}{n}\mathbf{K}_n=\mathbf{U}\Lambda\mathbf{U}^{\mathsf{T}}, \tag*{(8)} n 1 K n = U Λ U T , (8)
where Λ = diag ( λ 1 , … , λ n ) \Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n) Λ = diag ( λ 1 , … , λ n ) with λ 1 ≥ ⋯ ≥ λ n \lambda_1\ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n , and U = ( u 1 , … , u n ) ∈ R n × n \mathbf{U}=(\mathbf{u}_1,\ldots,\mathbf{u}_n)\in\mathbb{R}^{n\times n} U = ( u 1 , … , u n ) ∈ R n × n . For the embedding step, given an embedding dimension d d d , we define the spectral embeddings as
q i = ( u 1 i , … , u d i ) T ∈ R d , i = 1 , … , n . (9) \mathbf{q}_i=(u_{1i},\ldots,u_{di})^{\mathsf{T}}\in\mathbb{R}^{d},\quad i=1,\ldots,n. \tag*{(9)} q i = ( u 1 i , … , u d i ) T ∈ R d , i = 1 , … , n . (9)
In practice, the embedding dimension d d d is selected based on the specific underlying task. Algorithm S.2 in Appendix § 9 provides a data-driven option for choosing d d d , following [22 ] .
Finally, we note that the construction of the kernel matrix in (7) depends on the choice of a key parameter h n h_n h n . Inspired by [22 ] , in this paper we select the bandwidth based on pairwise distances, allowing it to adapt to the underlying geometry, sparsity, and signal-to-noise ratio. Specifically, we compute all pairwise squared Euclidean distances of { y i } i ∈ [ n ] \{\mathbf{y}_i\}_{i\in[n]} { y i } i ∈ [ n ] , denoted by d i j = ∥ y i − y j ∥ 2 d_{ij}=\lVert\mathbf{y}_i-\mathbf{y}_j\rVert^2 d ij = ∥ y i − y j ∥ 2 , 1 ≤ i ≠ j ≤ n 1\le i\ne j\le n 1 ≤ i = j ≤ n , and define their empirical cumulative distribution function as
G n ( t ) = 2 n ( n − 1 ) ∑ 1 ≤ i < j ≤ n 1 { d i j ≤ t } . (10) G_n(t)=\frac{2}{n(n-1)}\sum_{1\le i<j\le n}\mathbf{1}_{\{d_{ij}\le t\}}. \tag*{(10)} G n ( t ) = n ( n − 1 ) 2 1 ≤ i < j ≤ n ∑ 1 { d ij ≤ t } . (10)
We then set the bandwidth h n h_n h n as the ω \omega ω -quantile of G n ( t ) G_n(t) G n ( t ) , given by
h n : = inf { t ≥ 0 : G n ( t ) ≥ ω } , (11) h_n:=\inf\{t\ge0:G_n(t)\ge\omega\}, \tag*{(11)} h n := inf { t ≥ 0 : G n ( t ) ≥ ω } , (11)
where ω ∈ ( 0 , 1 ) \omega\in(0,1) ω ∈ ( 0 , 1 ) is a prespecified quantile parameter. Practical guidelines for selecting ω \omega ω are discussed in [22 ] . For completeness, we provide Algorithm S.1 in Appendix § 9 for its selection.
Remark 2.2. Two remarks are in order. First, the spectral embedding step above is to provide a concrete nonlinear embedding procedure after the adaptive projection has stabilized the pairwise geometry. For this reason, this step may be replaced by other spectral embedding methods, for example, diffusion based methods such as Laplacian eigenmaps [6 ] , diffusion maps [17 ] , and vector diffusion maps [61 ] . Second, although we focus on the Gaussian kernel function in (7) , our results extend to a broader class of kernel functions under suitable regularity conditions. We will discuss the general kernel assumption and the corresponding extension of our results in Appendix § 8 .§ 2 .
Downstream analysis
The learned embeddings can be used as low-dimensional features for downstream tasks such as clustering and prediction. In this paper, we focus on spectral clustering and classification. For spectral clustering, the setting is relatively direct, since one may apply a standard clustering algorithm directly to the embedded points { q i } i ∈ [ n ] \{\mathbf{q}_i\}_{i\in[n]} { q i } i ∈ [ n ] in (9) . In practice, this can be combined with commonly used methods such as K-means [44 ] . The main point is that clustering is carried out in the learned low-dimensional space rather than in the original noisy ambient space, so the representation produced by the project–then–embed pipeline serves as a denoised feature map for unsupervised analysis.
For the downstream classification, the situation is more delicate, since one typically works with separate training and test sets. In particular, once the embedding { q i } i ∈ [ n ] \{\mathbf{q}_i\}_{i\in[n]} { q i } i ∈ [ n ] is learned from the training data, one cannot simply obtain the test embeddings by rerunning the whole spectral procedure on the test set alone, because this would place the test samples in a different coordinate system and make them no longer directly comparable with the geometry learned from the training set. On the other hand, one also cannot first embed the combined training and test samples and then split them afterward, since this would allow information from the test set to enter the construction of the training representation.
This motivates an out-of-sample extension within the same framework. Suppose the projection matrix P \mathrm{P} P , the bandwidth h n h_n h n , and the leading eigenpairs { ( λ i , u i ) } i = 1 d \{(\lambda_i,\mathbf{u}_i)\}_{i=1}^d {( λ i , u i ) } i = 1 d have already been obtained from the training samples. Given a new observation x j n e w ∈ R p \mathbf{x}^{\mathrm{new}}_j\in\mathbb{R}^p x j new ∈ R p , we first project it using the same matrix P \mathrm{P} P learned from the training stage, and then embed it by a Nyström-type extension [72 ] based on its kernel affinities with the projected training samples in (6) . In this way, the new observation is mapped into the same low-dimensional coordinate system as the training data, so that the training embeddings { q i } i ∈ [ n ] \{\mathbf{q}_i\}_{i\in[n]} { q i } i ∈ [ n ] and test embeddings { q j n e w } j ∈ [ m ] \{\mathbf{q}^{\mathrm{new}}_j\}_{j\in[m]} { q j new } j ∈ [ m ] remain directly comparable. The out-of-sample extension procedure is summarized in Algorithm 2 .
Algorithm 2 Out-of-sample extension
Inputs: New samples { x j n e w } j ∈ [ m ] \{\mathbf{x}^{\mathrm{new}}_j\}_{j\in[m]} { x j new } j ∈ [ m ] , projection matrix P \mathrm{P} P , training mean x ˉ \bar{\mathbf{x}} x ˉ , projected training samples { y i } i = 1 n \{\mathbf{y}_i\}_{i=1}^n { y i } i = 1 n , bandwidth h n h_n h n , eigenpairs { ( λ i , u i ) } i = 1 d \{(\lambda_i,\mathbf{u}_i)\}_{i=1}^d {( λ i , u i ) } i = 1 d with λ d > 0 \lambda_d>0 λ d > 0 .
Step one: projection
Compute the projected new samples
y j n e w = P T ( x j n e w − x ˉ ) ∈ R K , j = 1 , … , m . \mathbf{y}^{\mathrm{new}}_j=\mathrm{P}^{\mathsf{T}}(\mathbf{x}^{\mathrm{new}}_j-\bar{\mathbf{x}})\in\mathbb{R}^K,\qquad j=1,\ldots,m. y j new = P T ( x j new − x ˉ ) ∈ R K , j = 1 , … , m . Step two: Nyström extension
For each j = 1 , … , m j=1,\ldots,m j = 1 , … , m , form the kernel vector
k j n e w = ( exp ( − ∥ y j n e w − y 1 ∥ 2 2 h n ) , … , exp ( − ∥ y j n e w − y n ∥ 2 2 h n ) ) T ∈ R n . \mathbf{k}^{\mathrm{new}}_j=\left(\exp\left(-\frac{\lVert\mathbf{y}^{\mathrm{new}}_j-\mathbf{y}_1\rVert_2^2}{h_n}\right),\ldots,\exp\left(-\frac{\lVert\mathbf{y}^{\mathrm{new}}_j-\mathbf{y}_n\rVert_2^2}{h_n}\right)\right)^{\mathsf{T}}\in\mathbb{R}^n. k j new = ( exp ( − h n ∥ y j new − y 1 ∥ 2 2 ) , … , exp ( − h n ∥ y j new − y n ∥ 2 2 ) ) T ∈ R n . Let
Λ d = diag ( λ 1 , … , λ d ) and U d = ( u 1 , … , u d ) ∈ R n × d . \mathbf{\Lambda}_d=\operatorname{diag}(\lambda_1,\ldots,\lambda_d)\quad\text{and}\quad\mathbf{U}_d=(\mathbf{u}_1,\ldots,\mathbf{u}_d)\in\mathbb{R}^{n\times d}. Λ d = diag ( λ 1 , … , λ d ) and U d = ( u 1 , … , u d ) ∈ R n × d . Define
q j n e w = 1 n Λ d − 1 U d T k j n e w ∈ R d . \mathbf{q}^{\mathrm{new}}_j=\frac{1}{n}\mathbf{\Lambda}_d^{-1}\mathbf{U}_d^{\mathsf{T}}\mathbf{k}^{\mathrm{new}}_j\in\mathbb{R}^d. q j new = n 1 Λ d − 1 U d T k j new ∈ R d . Output: Out-of-sample embeddings { q j n e w } j ∈ [ m ] \{\mathbf{q}^{\mathrm{new}}_j\}_{j\in[m]} { q j new } j ∈ [ m ] .
The out-of-sample extension uses exactly the same projection matrix P \mathrm{P} P , bandwidth h n h_n h n , and leading eigenpairs learned from the training data. As a result, new observations can be mapped into the same embedding space without repeating the full training procedure. After this extension step, one may train a standard classifier on the training embeddings { q i } i ∈ [ n ] \{\mathbf{q}_i\}_{i\in[n]} { q i } i ∈ [ n ] obtained in (9) together with their labels, and then evaluate it on the out-of-sample test embeddings { q j n e w } j ∈ [ m ] \{\mathbf{q}^{\mathrm{new}}_j\}_{j\in[m]} { q j new } j ∈ [ m ] obtained in Algorithm 2 . One can use simple classifiers such as a multilayer perceptron (MLP) [56 ] and linear discriminant analysis (LDA) [33 ] , though other classifiers can also be used in exactly the same way.
Main Results
In this section, we develop the theoretical framework for the proposed method and present its main convergence results. Our goal is to quantify how accurately the spectral embeddings in (9) , after normalization, approximate the eigenfunctions of an integral operator defined by the clean signal distribution. We begin by introducing the structural assumptions on the signal, the noise, and the sparsity representation in § 3.1 . We then study the recovery of pairwise distances after adaptive projection in § 3.2 , followed by the spectral convergence of the resulting kernel embedding constructed from the projected data in (9) in § 3.3 .
Notations and assumptions
Throughout the paper, we follow the setup of [29 , 22 , 59 ] and consider the signal-plus-noise model (1) . For the signal components s i \mathbf{s}_i s i , we follow [14 , 59 , 74 , 20 ] and impose the following assumption.
Assumption 3.1. The signals { s i } i ∈ [ n ] \{\mathbf{s}_i\}_{i\in[n]} { s i } i ∈ [ n ] are independent R p \mathbb{R}^{p} R p -valued random vectors with common distribution μ s \mu_s μ s on the Borel σ \sigma σ -algebra B ( R p ) \mathcal{B}(\mathbb{R}^{p}) B ( R p ) . μ s \mu_s μ s is supported on S : = ι ( M ) \mathcal{S}:=\iota(\mathcal{M}) S := ι ( M ) , where M \mathcal{M} M is a fixed d d d -dimensional Riemannian manifold with d ≥ 1 d\ge1 d ≥ 1 , and ι : M → R p \iota:\mathcal{M}\to\mathbb{R}^{p} ι : M → R p is a smooth isometric embedding. The linear span of ι ( M ) \iota(\mathcal{M}) ι ( M ) has dimension r r r for some fixed integer r < p r<p r < p . Let V V V denote the Riemannian volume measure on M \mathcal{M} M . Assume that μ s \mu_s μ s is absolutely continuous with respect to ι # V \iota_{\#}V ι # V , the pushforward of V V V under ι \iota ι , defined by ( ι # V ) ( A ) = V ( ι − 1 ( A ) ) (\iota_{\#}V)(A)=V(\iota^{-1}(A)) ( ι # V ) ( A ) = V ( ι − 1 ( A )) for A ∈ B ( R p ) A\in\mathcal{B}(\mathbb{R}^{p}) A ∈ B ( R p ) .
Assumption 3.1 distinguishes the intrinsic manifold dimension d d d from the dimension r r r of the linear signal space. The role of the projection step is to exploit the latter before constructing any distance-based affinity. Based on Assumption 3.1, there exists a rotation matrix R = ( r 1 , … , r p ) ∈ R p × p R=(\mathbf{r}_1,\ldots,\mathbf{r}_p)\in\mathbb{R}^{p\times p} R = ( r 1 , … , r p ) ∈ R p × p whose first r r r columns form an orthonormal basis of span { ι ( M ) } \operatorname{span}\{\iota(\mathcal{M})\} span { ι ( M )} , such that, for each s i ∈ ι ( M ) \mathbf{s}_i\in\iota(\mathcal{M}) s i ∈ ι ( M ) ,
R T s i = ( ( s i 0 ) T , 0 , … , 0 ) T ∈ R p , i = 1 , … , n , (12) R^{\mathsf{T}}\mathbf{s}_i=\left((\mathbf{s}_i^0)^{\mathsf{T}},0,\ldots,0\right)^{\mathsf{T}}\in\mathbb{R}^{p},\qquad i=1,\ldots,n, \tag*{(12)} R T s i = ( ( s i 0 ) T , 0 , … , 0 ) T ∈ R p , i = 1 , … , n , (12)
where s i 0 = ( s i 1 , … , s i r ) T ∈ R r \mathbf{s}_i^0=(s_{i1},\ldots,s_{ir})^{\mathsf{T}}\in\mathbb{R}^{r} s i 0 = ( s i 1 , … , s i r ) T ∈ R r denotes the reduced coordinates. Hence, we write R r = ( r 1 , … , r r ) ∈ R p × r R_r=(\mathbf{r}_1,\ldots,\mathbf{r}_r)\in\mathbb{R}^{p\times r} R r = ( r 1 , … , r r ) ∈ R p × r and define
T : R p → R r , T ( s ) = R r T s . (13) T:\mathbb{R}^{p}\to\mathbb{R}^{r},\qquad T(\mathbf{s})=R_r^{\mathsf{T}}\mathbf{s}. \tag*{(13)} T : R p → R r , T ( s ) = R r T s . (13)
Let μ : = T # μ s \mu:=T_{\#}\mu_s μ := T # μ s be the pushforward probability measure induced by the reduced signal coordinates. Thus, { s i 0 } i ∈ [ n ] \{\mathbf{s}_i^0\}_{i\in[n]} { s i 0 } i ∈ [ n ] are i.i.d. from μ \mu μ . Moreover, we define the reduced signal manifold
M 0 : = T ( ι ( M ) ) ⊂ R r . \mathcal{M}^{0}:=T(\iota(\mathcal{M}))\subset\mathbb{R}^{r}. M 0 := T ( ι ( M )) ⊂ R r .
Since T T T restricts to a linear isometry on span ( ι ( M ) ) \operatorname{span}(\iota(\mathcal{M})) span ( ι ( M )) , the composition T ∘ ι : M → R r T \circ\iota:\mathcal{M}\to\mathbb{R}^{r} T ∘ ι : M → R r is also a smooth isometric embedding. Thus M 0 \mathcal{M}^{0} M 0 is a d d d -dimensional Riemannian submanifold of R r \mathbb{R}^{r} R r , with induced volume measure V 0 = ( T ∘ ι ) # V V_{0}=(T\circ\iota)_{\#}V V 0 = ( T ∘ ι ) # V . Assumption 3.1 implies μ \mu μ is absolutely continuous with respect to V 0 V_{0} V 0 , and we can therefore write
f μ : = d μ d V 0 . (14) f_{\mu}:=\frac{\mathrm{d}\mu}{\mathrm{d}V_{0}}. \tag*{(14)} f μ := d V 0 d μ . (14)
We next impose regularity conditions on the reduced signal distribution μ \mu μ and the additive noise in (1) . Those assumptions are commonly used in the literature; see, for example, [14 , 20 ] .
Assumption 3.2. We assume that M 0 \mathcal{M}^{0} M 0 is compact and that the reduced signal measure μ \mu μ admits a continuous density f μ f_{\mu} f μ , bounded above and below by some positive constants on M 0 \mathcal{M}^{0} M 0 with respect to V 0 V_{0} V 0 . We also assume that Σ = Cov ( s i 0 ) \Sigma=\operatorname{Cov}(s_{i}^{0}) Σ = Cov ( s i 0 ) is positive definite. We further assume that the noise vectors { z i } i ∈ [ n ] \{z_{i}\}_{i\in[n]} { z i } i ∈ [ n ] are independent of the signals { s i } i ∈ [ n ] \{s_{i}\}_{i\in[n]} { s i } i ∈ [ n ] , and are independent sub-Gaussian random vectors with independent entries, and
E ( z i ) = 0 , Cov ( z i ) = σ 2 I p . (15) \mathbb{E}(z_{i})=0,\qquad\operatorname{Cov}(z_{i})=\sigma^{2}I_{p}. \tag*{(15)} E ( z i ) = 0 , Cov ( z i ) = σ 2 I p . (15) Moreover, for some 0 < α < ∞ 0<\alpha<\infty 0 < α < ∞ , we assume that p ≍ n α p\asymp n^{\alpha} p ≍ n α .
Let λ 1 0 ≥ ⋯ ≥ λ r 0 > 0 \lambda_{1}^{0}\geq\cdots\geq\lambda_{r}^{0}>0 λ 1 0 ≥ ⋯ ≥ λ r 0 > 0 denote the eigenvalues of Σ \Sigma Σ . We define the signal strength by
Θ = tr ( Σ ) = ∑ j = 1 r λ j 0 . (16) \Theta=\operatorname{tr}(\Sigma)=\sum_{j=1}^{r}\lambda_{j}^{0}. \tag*{(16)} Θ = tr ( Σ ) = j = 1 ∑ r λ j 0 . (16)
Based on the model (1) , we see that the overall signal-to-noise ratio of noisy samples { x i } i ∈ [ n ] \{x_{i}\}_{i\in[n]} { x i } i ∈ [ n ] can be defined as
SNR ≡ SNR ( n ) : = Θ p σ 2 . (17) \operatorname{SNR}\equiv\operatorname{SNR}(n):=\frac{\Theta}{p\sigma^{2}}. \tag*{(17)} SNR ≡ SNR ( n ) := p σ 2 Θ . (17)
We then impose a sparsity assumption motivated by [40 , 52 ] , which encodes the sparsity structure that makes adaptive projection possible. Let W = ( w 1 , … , w p ) ∈ R p × p W=(w_{1},\ldots,w_{p})\in\mathbb{R}^{p\times p} W = ( w 1 , … , w p ) ∈ R p × p be the orthonormal basis used in (2) . For each k = 1 , … , r k=1,\ldots,r k = 1 , … , r , write the k k k -th signal direction r k r_{k} r k of R p \mathbb{R}^{p} R p in this basis as
r k = ∑ j = 1 p a j k w j ∈ R p . (18) r_{k}=\sum_{j=1}^{p}a_{jk}w_{j}\in\mathbb{R}^{p}. \tag*{(18)} r k = j = 1 ∑ p a j k w j ∈ R p . (18)
Assumption 3.3. Assume that for some q ∈ ( 0 , 2 ) q\in(0,2) q ∈ ( 0 , 2 ) and constants 0 < c k ≤ C k < ∞ 0<c_{k}\leq C_{k}<\infty 0 < c k ≤ C k < ∞ ,
c k j − 1 / q ≤ ∣ a ( j ) k ∣ ≤ C k j − 1 / q , j = 1 , … , p , (19) c_{k}j^{-1/q}\leq\lvert a_{(j)k}\rvert\leq C_{k}j^{-1/q},\qquad j=1,\ldots,p, \tag*{(19)} c k j − 1/ q ≤ ∣ a ( j ) k ∣ ≤ C k j − 1/ q , j = 1 , … , p , (19) where ∣ a ( 1 ) k ∣ ≥ ⋯ ≥ ∣ a ( p ) k ∣ \lvert a_{(1)k}\rvert\geq\cdots\geq\lvert a_{(p)k}\rvert ∣ a ( 1 ) k ∣ ≥ ⋯ ≥ ∣ a ( p ) k ∣ denotes the decreasing rearrangement of { ∣ a j k ∣ } j ∈ [ p ] \{\lvert a_{jk}\rvert\}_{j\in[p]} {∣ a j k ∣ } j ∈ [ p ] .
Smaller values of q q q in (19) correspond to faster energy decay and stronger concentration of the signal on a few basis directions. Larger values of q q q spread the signal more evenly across the basis and therefore make the selection of directions less effective.
Finally, to streamline the statements of our results, we adopt the notion of stochastic domination [30 ] throughout the remainder of the paper. Let X = { X ( n ) ( u ) : n ∈ N , u ∈ U ( n ) } X = \{X^{(n)}(u) : n \in\mathbb{N},\ u \in U^{(n)}\} X = { X ( n ) ( u ) : n ∈ N , u ∈ U ( n ) } and Y = { Y ( n ) ( u ) : n ∈ N , u ∈ U ( n ) } Y = \{Y^{(n)}(u) : n \in\mathbb{N},\ u \in U^{(n)}\} Y = { Y ( n ) ( u ) : n ∈ N , u ∈ U ( n ) } be two families of nonnegative random variables, where U ( n ) U^{(n)} U ( n ) is a possibly n n n -dependent parameter set. We say that X X X is stochastically dominated by Y Y Y , uniformly over u ∈ U ( n ) u \in U^{(n)} u ∈ U ( n ) , if for every small ε > 0 \varepsilon> 0 ε > 0 and large D > 0 D > 0 D > 0 , there exists n 0 ( ε , D ) ∈ N n_0(\varepsilon,D) \in\mathbb{N} n 0 ( ε , D ) ∈ N such that
sup u ∈ U ( n ) P ( X ( n ) ( u ) > n ε Y ( n ) ( u ) ) ≤ n − D , n ≥ n 0 ( ε , D ) . \sup_{u \in U^{(n)}} \mathbb{P}\left(X^{(n)}(u) > n^{\varepsilon}Y^{(n)}(u)\right) \le n^{-D}, \qquad n \ge n_0(\varepsilon,D). u ∈ U ( n ) sup P ( X ( n ) ( u ) > n ε Y ( n ) ( u ) ) ≤ n − D , n ≥ n 0 ( ε , D ) .
We then write X ≺ Y X \prec Y X ≺ Y or equivalently X = O ≺ ( Y ) X = O_{\prec}(Y) X = O ≺ ( Y ) .
Recovery of Pairwise Distances
Recall the signal strength Θ \Theta Θ , signal-to-noise ratio SNR, and the sparsity parameter q q q in (16) , (17) and (19) . We begin by quantifying the projection dimension K K K selected by Algorithm 1.
Proposition 3.4 (Selected projection dimension). Suppose Assumptions 3.1, 3.2, and 3.3 hold and σ 2 / Θ = o ( 1 ) \sigma^2/\Theta= o(1) σ 2 /Θ = o ( 1 ) . Then, with high probability, for sufficiently large n n n , for any fixed constants s s s and τ \tau τ in Algorithm 1
K ≍ { ( Θ / σ 2 ) q / 2 , if SNR ≲ p 2 / q − 1 , p , if SNR ≳ p 2 / q − 1 . (20) K \asymp\begin{cases}
(\Theta/\sigma^2)^{q/2}, & \text{if SNR} \lesssim p^{2/q-1},\\
p, & \text{if SNR} \gtrsim p^{2/q-1}.
\end{cases} \tag*{(20)} K ≍ { ( Θ/ σ 2 ) q /2 , p , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 . (20)
Once K K K and the associated directions are chosen, we next study how accurately the selected projection preserves the latent signal pairwise geometry. The projection P P P in (5) obtained by Algorithm 1 reduces the number of noise coordinates from p p p to K K K , motivating the retained-noise scale K σ 2 K\sigma^2 K σ 2 . We define the effective SNR after projection as follows
SNR e f f : = { ( Θ σ 2 ) 1 − q / 2 , if SNR ≲ p 2 / q − 1 , Θ σ 2 p , if SNR ≳ p 2 / q − 1 . (21) \operatorname{SNR}_{\mathrm{eff}} := \begin{cases}
\left(\dfrac{\Theta}{\sigma^2}\right)^{1-q/2}, & \text{if SNR} \lesssim p^{2/q-1},\\
\dfrac{\Theta}{\sigma^2 p}, & \text{if SNR} \gtrsim p^{2/q-1}.
\end{cases} \tag*{(21)} SNR eff := ⎩ ⎨ ⎧ ( σ 2 Θ ) 1 − q /2 , σ 2 p Θ , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 . (21)
Recall (6) that y i = P T ( x i − x ˉ ) y_i = \mathbf{P}^{\mathsf{T}}(x_i - \bar{x}) y i = P T ( x i − x ˉ ) is the corresponding projected data. The resulting pairwise-distance error ∥ y i − y j ∥ 2 2 \lVert y_i-y_j\rVert_2^2 ∥ y i − y j ∥ 2 2 and ∥ s i − s j ∥ 2 2 \lVert s_i-s_j\rVert_2^2 ∥ s i − s j ∥ 2 2 naturally decomposes into two sources: a bias caused by truncating weak signal directions, and a stochastic error caused by the projected noise.
Next, we define two rates for the two sources of error as
ψ n , b i a s ≔ { 1 S N R e f f , if SNR ≲ p 2 / q − 1 , p 1 − 2 / q , if SNR ≳ p 2 / q − 1 , (22) \psi_{n,\mathrm{bias}} \coloneqq\begin{cases}
\frac{1}{\mathrm{SNR}_{\mathrm{eff}}}, & \text{if SNR} \lesssim p^{2/q-1},\\
p^{1-2/q}, & \text{if SNR} \gtrsim p^{2/q-1},
\end{cases} \tag*{(22)} ψ n , bias : = { SNR eff 1 , p 1 − 2/ q , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 , (22)
and
ψ n , n o i s e ≔ { 1 S N R e f f + σ ( Θ σ 2 ) ( ( q − 1 ) + ) / 2 , if SNR ≲ p 2 / q − 1 , 1 S N R e f f + σ p ( 1 − 1 / q ) + , if SNR ≳ p 2 / q − 1 , (23) \psi_{n,\mathrm{noise}} \coloneqq\begin{cases}
\frac{1}{\mathrm{SNR}_{\mathrm{eff}}}+\sigma\left(\frac{\Theta}{\sigma^2}\right)^{((q-1)_+)/2}, & \text{if SNR} \lesssim p^{2/q-1},\\
\frac{1}{\mathrm{SNR}_{\mathrm{eff}}}+\sigma p^{(1-1/q)_+}, & \text{if SNR} \gtrsim p^{2/q-1},
\end{cases} \tag*{(23)} ψ n , noise : = { SNR eff 1 + σ ( σ 2 Θ ) (( q − 1 ) + ) /2 , SNR eff 1 + σ p ( 1 − 1/ q ) + , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 , (23)
Moreover, we define the combined rate
ψ n ≔ ψ n , b i a s + ψ n , n o i s e . (24) \psi_n \coloneqq\psi_{n,\mathrm{bias}}+\psi_{n,\mathrm{noise}}. \tag*{(24)} ψ n : = ψ n , bias + ψ n , noise . (24)
Theorem 3.6 (Uniform recovery of pairwise distances). Suppose Assumptions 3.1 3.1 3.1 , 3.2 3.2 3.2 , and 3.3 3.3 3.3 hold. Then
max 1 ≤ i < j ≤ n ∣ ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ = O P ( ψ n ) . (25) \max_{1\le i<j\le n}\left|\lVert y_i-y_j\rVert_2^2-\lVert s_i-s_j\rVert_2^2\right| = O_{\mathbb{P}}(\psi_n). \tag*{(25)} 1 ≤ i < j ≤ n max ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 = O P ( ψ n ) . (25)
Remark 3.7. Theorem 3.6 3.6 3.6 shows that pairwise-distance recovery behaves differently in different SNR regimes. When SNR ≲ p 2 / q − 1 \lesssim p^{2/q-1} ≲ p 2/ q − 1 , the selected projection dimension is smaller, and the resulting error is controlled by the effective post-projection signal-to-noise ratio. When SNR ≳ p 2 / q − 1 \gtrsim p^{2/q-1} ≳ p 2/ q − 1 *, the selected projection dimension is of order p p p , so the rate reflects the full scale after projection.
The sparsity parameter q q q determines how favorable this recovery is. For 0 < q ≤ 1 0<q\le1 0 < q ≤ 1 ,
ψ n ≃ { 1 S N R e f f + σ , if SNR ≲ p 2 / q − 1 , p 1 − 2 / q + σ , if SNR ≳ p 2 / q − 1 , \psi_n \simeq\begin{cases}
\frac{1}{\mathrm{SNR}_{\mathrm{eff}}}+\sigma, & \text{if SNR} \lesssim p^{2/q-1},\\
p^{1-2/q}+\sigma, & \text{if SNR} \gtrsim p^{2/q-1},
\end{cases} ψ n ≃ { SNR eff 1 + σ , p 1 − 2/ q + σ , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 ,
and for 1 < q < 2 1<q<2 1 < q < 2 ,
ψ n ≃ { 1 S N R e f f + σ ( Θ σ 2 ) ( q − 1 ) / 2 , if SNR ≲ p 2 / q − 1 , p 1 − 2 / q + σ p 1 − 1 / q , if SNR ≳ p 2 / q − 1 . \psi_n \simeq\begin{cases}
\frac{1}{\mathrm{SNR}_{\mathrm{eff}}}+\sigma\left(\frac{\Theta}{\sigma^2}\right)^{(q-1)/2}, & \text{if SNR} \lesssim p^{2/q-1},\\
p^{1-2/q}+\sigma p^{1-1/q}, & \text{if SNR} \gtrsim p^{2/q-1}.
\end{cases} ψ n ≃ { SNR eff 1 + σ ( σ 2 Θ ) ( q − 1 ) /2 , p 1 − 2/ q + σ p 1 − 1/ q , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 .
Smaller values of q q q lead to stronger concentration of the signal on a few directions and hence better recovery, whereas larger values of q q q spread the signal more broadly and lead to a larger error rate.
We point out that the rate bound in Theorem $3.6$ does not require the condition σ 2 / Θ = o ( 1 ) \sigma^2/\Theta=o(1) σ 2 /Θ = o ( 1 ) imposed in Proposition 3.4 3.4 3.4 . However, if σ ≲ n − c \sigma\lesssim n^{-c} σ ≲ n − c for some fixed c > 0 c>0 c > 0 , consistency holds across all the SNR regimes and sparsity levels discussed above. Specifically, for any fixed q ∈ ( 0 , 2 ) q\in(0,2) q ∈ ( 0 , 2 ) and p ≃ n α p\simeq n^\alpha p ≃ n α as in Assumptions 3.2 3.2 3.2 and $3.3, respectively, Theorem 3.6 3.6 3.6 implies that there exists a fixed c ′ > 0 c'>0 c ′ > 0 such that
max 1 ≤ i < j ≤ n ∣ ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ = O P ( n − c ′ ) . \max_{1\le i<j\le n}\left|\lVert y_i-y_j\rVert_2^2-\lVert s_i-s_j\rVert_2^2\right| = O_{\mathbb{P}}(n^{-c'}). 1 ≤ i < j ≤ n max ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 = O P ( n − c ′ ) .
Theorem 3.6 provides the algorithmic justification for the adaptive projection step. It shows that, after selecting the basis directions with large enough empirical energy, the projected observations retain the essential pairwise geometry of the underlying signals. In this sense, the projection step serves as a geometric denoising procedure: it suppresses noise-dominated directions while preserving the distance information needed for the subsequent kernel construction. This is precisely why the projected data, rather than the original observations, form a more reliable input for the spectral embedding algorithm.
Convergence of Spectral Embedding
We now state the spectral convergence results for K n \mathbf{K}_n K n in (7) . Recall that μ \mu μ is the distribution of the reduced signal coordinates s i 0 \mathbf{s}_i^0 s i 0 on M 0 ⊂ R r \mathcal{M}^0 \subset\mathbb{R}^r M 0 ⊂ R r as in Assumption 3.2. Let U ∈ R r U \in\mathbb{R}^r U ∈ R r and V ∈ R r V \in\mathbb{R}^r V ∈ R r be i.i.d. random vectors with distribution μ \mu μ , and set D = ∥ U − V ∥ 2 2 D = \lVert U - V \rVert_2^2 D = ∥ U − V ∥ 2 2 . Denote the cumulative distribution function of D D D by
G ( t ) : = P ( D ≤ t ) , (26) G(t) := \mathbb{P}(D \le t), \tag*{(26)} G ( t ) := P ( D ≤ t ) , (26)
and define the population bandwidth h h h by
h : = inf { t ≥ 0 : G ( t ) ≥ ω } , (27) h := \inf\{t \ge0 : G(t) \ge\omega\}, \tag*{(27)} h := inf { t ≥ 0 : G ( t ) ≥ ω } , (27)
with ω \omega ω as in (11) .
Using this bandwidth h h h , we define the population kernel operator K : L 2 ( R r , μ ) → L 2 ( R r , μ ) \mathcal{K}: L^2(\mathbb{R}^r,\mu) \to L^2(\mathbb{R}^r,\mu) K : L 2 ( R r , μ ) → L 2 ( R r , μ ) by
( K g ) ( u ) : = ∫ M 0 exp ( − ∥ u − v ∥ 2 2 h ) g ( v ) μ ( d v ) , u ∈ R r . (\mathcal{K}g)(u) := \int_{\mathcal{M}^0} \exp\left(-\frac{\lVert u-v\rVert_2^2}{h}\right)g(v)\,\mu(\mathrm{d}v), \qquad u \in\mathbb{R}^r. ( K g ) ( u ) := ∫ M 0 exp ( − h ∥ u − v ∥ 2 2 ) g ( v ) μ ( d v ) , u ∈ R r .
Let { ( γ i , ϕ i ) } i ≥ 1 \{(\gamma_i,\phi_i)\}_{i\ge1} {( γ i , ϕ i ) } i ≥ 1 denote the eigenvalue-eigenfunction pairs of K \mathcal{K} K , with { ϕ i } \{\phi_i\} { ϕ i } orthonormal in L 2 ( R r , μ ) L^2(\mathbb{R}^r,\mu) L 2 ( R r , μ ) , ordered so that γ 1 ≥ γ 2 ≥ ⋯ ≥ 0 \gamma_1 \ge\gamma_2 \ge\cdots\ge0 γ 1 ≥ γ 2 ≥ ⋯ ≥ 0 .
Since our observed data live in the space R p \mathbb{R}^p R p , it is convenient to introduce the corresponding operator on the embedded signal space. Recall that μ s \mu_s μ s is the distribution of the clean signals, supported on the embedded manifold S = ι ( M ) ⊂ R p \mathcal{S}=\iota(\mathcal{M}) \subset\mathbb{R}^p S = ι ( M ) ⊂ R p as in Assumption 3.1 . We define the corresponding population operator K ~ : L 2 ( R p , μ s ) → L 2 ( R p , μ s ) \widetilde{\mathcal{K}}: L^2(\mathbb{R}^p,\mu_s) \to L^2(\mathbb{R}^p,\mu_s) K : L 2 ( R p , μ s ) → L 2 ( R p , μ s ) by
( K ~ g ) ( x ) : = ∫ S exp ( − ∥ x − y ∥ 2 2 h ) g ( y ) μ s ( d y ) , x ∈ S . (28) (\widetilde{\mathcal{K}}g)(x) := \int_{\mathcal{S}} \exp\left(-\frac{\lVert x-y\rVert_2^2}{h}\right)g(y)\,\mu_s(\mathrm{d}y), \qquad x \in\mathcal{S}. \tag*{(28)} ( K g ) ( x ) := ∫ S exp ( − h ∥ x − y ∥ 2 2 ) g ( y ) μ s ( d y ) , x ∈ S . (28)
Recall R R R in (12) and R r R_r R r in (13) . For x ∈ S x \in\mathcal{S} x ∈ S , let u u u denote the first r r r coordinates of R T x R^{\mathsf{T}}x R T x and define
ϕ ~ i ( x ) : = ϕ i ( u ) , i ≥ 1. \widetilde{\phi}_i(x) := \phi_i(u), \qquad i \ge1. ϕ i ( x ) := ϕ i ( u ) , i ≥ 1.
Since u ↦ R r u u \mapsto R_r u u ↦ R r u preserves distances and transports μ \mu μ to μ s \mu_s μ s , the functions { ϕ ~ i } \{\widetilde{\phi}_i\} { ϕ i } are orthonormal eigenfunctions of K ~ \widetilde{\mathcal{K}} K with the same eigenvalues { γ i } \{\gamma_i\} { γ i } . For any fixed δ > 0 \delta> 0 δ > 0 , define
M ( δ ) : = # { i ≥ 1 : γ i ≥ δ } . (29) M(\delta) := \#\{i \ge1 : \gamma_i \ge\delta\}. \tag*{(29)} M ( δ ) := # { i ≥ 1 : γ i ≥ δ } . (29)
For a simple positive eigenvalue γ i \gamma_i γ i , let
g i = { γ 1 − γ 2 , i = 1 , min { γ i − 1 − γ i , γ i − γ i + 1 } , i > 1. (30) g_i =
\begin{cases}
\gamma_1-\gamma_2, & i=1,\\
\min\{\gamma_{i-1}-\gamma_i,\gamma_i-\gamma_{i+1}\}, & i>1.
\end{cases} \tag*{(30)} g i = { γ 1 − γ 2 , min { γ i − 1 − γ i , γ i − γ i + 1 } , i = 1 , i > 1. (30)
We then turn to the empirical operator constructed from the noisy observations. This operator is built from the projected data { y j } j ∈ [ n ] \{y_j\}_{j\in[n]} { y j } j ∈ [ n ] in (6) . Let μ ^ n \widehat{\mu}_n μ n be the empirical distribution of the noisy samples { x j } j = 1 n ⊂ R p \{x_j\}_{j=1}^n\subset\mathbb{R}^p { x j } j = 1 n ⊂ R p , that is,
μ ^ n : = 1 n ∑ j = 1 n δ x j . \widehat{\mu}_n := \frac{1}{n}\sum_{j=1}^{n}\delta_{x_j}. μ n := n 1 j = 1 ∑ n δ x j .
Recall P ∈ R p × K \mathrm{P}\in\mathbb{R}^{p\times K} P ∈ R p × K in (5) . We define the corresponding empirical operator K ^ n : L 2 ( R p , μ ^ n ) → L 2 ( R p , μ ^ n ) \widehat{\mathcal{K}}_n:L^2(\mathbb{R}^p,\widehat{\mu}_n)\to L^2(\mathbb{R}^p,\widehat{\mu}_n) K n : L 2 ( R p , μ n ) → L 2 ( R p , μ n ) by
( K ^ n g ) ( x ) : = ∫ exp ( − ∥ P T x − P T y ∥ 2 2 h n ) g ( y ) μ ^ n ( d y ) = 1 n ∑ j = 1 n exp ( − ∥ P T ( x − x j ) ∥ 2 2 h n ) g ( x j ) , x ∈ R p . (\widehat{\mathcal{K}}_n g)(\mathbf{x}) := \int\exp\left(-\frac{\lVert\mathrm{P}^{\mathsf{T}}\mathbf{x}-\mathrm{P}^{\mathsf{T}}\mathbf{y}\rVert_2^2}{h_n}\right)g(\mathbf{y})\,\widehat{\mu}_n(\mathrm{d}\mathbf{y})
= \frac{1}{n}\sum_{j=1}^{n}\exp\left(-\frac{\lVert\mathrm{P}^{\mathsf{T}}(\mathbf{x}-\mathbf{x}_j)\rVert_2^2}{h_n}\right)g(\mathbf{x}_j),\qquad\mathbf{x}\in\mathbb{R}^p. ( K n g ) ( x ) := ∫ exp ( − h n ∥ P T x − P T y ∥ 2 2 ) g ( y ) μ n ( d y ) = n 1 j = 1 ∑ n exp ( − h n ∥ P T ( x − x j ) ∥ 2 2 ) g ( x j ) , x ∈ R p .
By construction of K ^ n \widehat{\mathcal{K}}_n K n , the nonzero eigenvalues of K ^ n \widehat{\mathcal{K}}_n K n coincide with those of n − 1 K n n^{-1}\mathbf{K}_n n − 1 K n . Recall from (8) that
1 n K n = U Λ U T , Λ = diag ( λ 1 , … , λ n ) , U = ( u 1 , … , u n ) . \frac{1}{n}\mathbf{K}_n=\mathbf{U}\boldsymbol{\Lambda}\mathbf{U}^{\mathsf{T}},\qquad\boldsymbol{\Lambda}=\operatorname{diag}(\lambda_1,\ldots,\lambda_n),\qquad\mathbf{U}=(\mathbf{u}_1,\ldots,\mathbf{u}_n). n 1 K n = U Λ U T , Λ = diag ( λ 1 , … , λ n ) , U = ( u 1 , … , u n ) .
For each λ i > 0 \lambda_i>0 λ i > 0 , the corresponding normalized empirical eigenfunction is given by
ϕ ^ i ( n ) ( x ) : = 1 λ i n ∑ j = 1 n exp ( − ∥ P T ( x − x j ) ∥ 2 2 h n ) u i j , x ∈ R p . (31) \widehat{\phi}_i^{(n)}(\mathbf{x}) := \frac{1}{\lambda_i\sqrt{n}}\sum_{j=1}^{n}\exp\left(-\frac{\lVert\mathrm{P}^{\mathsf{T}}(\mathbf{x}-\mathbf{x}_j)\rVert_2^2}{h_n}\right)u_{ij},\qquad\mathbf{x}\in\mathbb{R}^p. \tag*{(31)} ϕ i ( n ) ( x ) := λ i n 1 j = 1 ∑ n exp ( − h n ∥ P T ( x − x j ) ∥ 2 2 ) u ij , x ∈ R p . (31)
We now present the convergence results. Recall ψ n \psi_n ψ n in (24) , G G G in (26) , h h h in (27) , M ( δ ) M(\delta) M ( δ ) in (29) and g i g_i g i in (30) .
Theorem 3.8 (Spectral convergence). Suppose Assumptions 3.1, 3.2, and 3.3 hold. Assume ω ∈ ( 0 , 1 ) \omega\in(0,1) ω ∈ ( 0 , 1 ) is chosen such that G G G has a density ν \nu ν in a neighbourhood of h h h , continuous at h h h with ν ( h ) > 0 \nu(h)>0 ν ( h ) > 0 . Then
max i ∈ [ n ] ∣ λ i − γ i ∣ = O ≺ ( ψ n + 1 n ) . \max_{i\in[n]}|\lambda_i-\gamma_i|=O_{\prec}\left(\psi_n+\frac{1}{\sqrt{n}}\right). i ∈ [ n ] max ∣ λ i − γ i ∣ = O ≺ ( ψ n + n 1 ) . Moreover, for any fixed δ > 0 \delta>0 δ > 0 and any 1 ≤ i ≤ M ( δ ) 1\le i\le M(\delta) 1 ≤ i ≤ M ( δ ) with g i > 0 g_i>0 g i > 0 , there exists some s i ∈ { − 1 , 1 } s_i\in\{-1,1\} s i ∈ { − 1 , 1 } such that, for any x ∈ S \mathbf{x}\in\mathcal{S} x ∈ S , we have
∣ λ i ϕ ^ i ( n ) ( x ) − s i γ i ϕ ~ i ( x ) ∣ = O ≺ ( ψ n + 1 n + 1 g i ( ψ n 1 / 2 + 1 n ) ) . \left|\sqrt{\lambda_i}\widehat{\phi}_i^{(n)}(\mathbf{x})-s_i\sqrt{\gamma_i}\widetilde{\phi}_i(\mathbf{x})\right|=O_{\prec}\left(\psi_n+\frac{1}{\sqrt{n}}+\frac{1}{g_i}\left(\psi_n^{1/2}+\frac{1}{\sqrt{n}}\right)\right). λ i ϕ i ( n ) ( x ) − s i γ i ϕ i ( x ) = O ≺ ( ψ n + n 1 + g i 1 ( ψ n 1/2 + n 1 ) ) .
Theorem 3.8 provides the methodological justification for the full project–then–embed procedure. It shows that, after the projection step denoises the pairwise geometry, the kernel matrix constructed from the projected observations still recovers the population spectral structure associated with the underlying signal manifold. Consequently, the spectral embeddings in (9) can be interpreted as reliable low-dimensional features that retain the intrinsic nonlinear geometry while remaining robust to high-dimensional noise.
Finally, we point out that the spectral convergence results extend to a broader class of kernel functions under suitable regularity conditions. We defer the precise assumptions and formal statements to Appendix § 8 .§ 2 .
Numerical Simulations
In this section, we conduct extensive Monte-Carlo simulations to evaluate the empirical performance of the proposed method (denoted as SPASE) on downstream classification and spectral clustering tasks. For comparison, we also include several commonly used manifold learning methods, including Isomap [63 ] (denoted as Isomap), locally linear embedding [55 ] (denoted as LLE), t-SNE [66 ] (denoted as t-SNE), Diffusion Maps [17 ] (denoted as DM), autoencoders [37 ] (denoted as AE), denoising autoencoders [69 ] (denoted as DAE), and kernel spectral embedding in [20 ] (denoted as KSE). We first compare downstream performance in § 4.2 , then examine recovery of clean pairwise distances, sensitivity to the prescribed basis, and the choice of projection dimension in § 4.3 –§ 4.5 .
Simulation Setup
We first describe the common data-generating mechanism used throughout the simulation study. For (1.1), we choose the noise z j ∼ i . i . d . N ( 0 , σ 2 I p ) z_j \overset{\mathrm{i.i.d.}}{\sim} \mathcal{N}(0,\sigma^2 I_p) z j ∼ i.i.d. N ( 0 , σ 2 I p ) , and construct the signal s j ∈ R p s_j \in\mathbb{R}^p s j ∈ R p through (12) . Specifically, we first generate latent coordinates s j 0 = ( s j , 1 0 , s j , 2 0 , s j , 3 0 ) T ∈ R 3 s_j^0=(s_{j,1}^0,s_{j,2}^0,s_{j,3}^0)^{\mathsf{T}}\in\mathbb{R}^3 s j 0 = ( s j , 1 0 , s j , 2 0 , s j , 3 0 ) T ∈ R 3 on a latent manifold Ω ⊂ R 3 \Omega\subset\mathbb{R}^3 Ω ⊂ R 3 . We then randomly choose three distinct indices 1 ≤ i 1 < i 2 < i 3 ≤ p 1\le i_1<i_2<i_3\le p 1 ≤ i 1 < i 2 < i 3 ≤ p and define s ~ j = ( s ~ j , 1 , … , s ~ j , p ) T ∈ R p \widetilde{s}_j=(\widetilde{s}_{j,1},\ldots,\widetilde{s}_{j,p})^{\mathsf{T}}\in\mathbb{R}^p s j = ( s j , 1 , … , s j , p ) T ∈ R p by
s ~ j , ℓ = { s j , k 0 , ℓ = i k , k = 1 , 2 , 3 , 0 , ℓ ∉ { i 1 , i 2 , i 3 } . \widetilde{s}_{j,\ell} =
\begin{cases}
s_{j,k}^0, & \ell=i_k,\ k=1,2,3,\\
0, & \ell\notin\{i_1,i_2,i_3\}.
\end{cases} s j , ℓ = { s j , k 0 , 0 , ℓ = i k , k = 1 , 2 , 3 , ℓ ∈ / { i 1 , i 2 , i 3 } .
Next, we construct R ∈ R p × p R\in\mathbb{R}^{p\times p} R ∈ R p × p using the Haar basis induced by level-4 discrete multiresolution decomposition (see, for example, [45 , 18 ] ), denoted by H = { h j } j = 1 p H=\{h_j\}_{j=1}^p H = { h j } j = 1 p . Recall the sparsity parameter q q q in Assumption 3.3. Larger q q q gives slower decay of the coefficient magnitudes ℓ − 1 / q \ell^{-1/q} ℓ − 1/ q in the construction below. For each k = 1 , 2 , 3 k=1,2,3 k = 1 , 2 , 3 , we generate
r ~ i k = ∑ ℓ = 1 p ℓ − 1 / q h π k ( ℓ ) . \widetilde{r}_{i_k}=\sum_{\ell=1}^{p}\ell^{-1/q}h_{\pi_k(\ell)}. r i k = ℓ = 1 ∑ p ℓ − 1/ q h π k ( ℓ ) .
where, for each k = 1 , 2 , 3 k=1,2,3 k = 1 , 2 , 3 , { π k ( ℓ ) } ℓ ∈ [ p ] \{\pi_k(\ell)\}_{\ell\in[p]} { π k ( ℓ ) } ℓ ∈ [ p ] is an independently generated random permutation of [ p ] [p] [ p ] . We then orthonormalize the three vectors ( r ~ i 1 , r ~ i 2 , r ~ i 3 ) (\widetilde{r}_{i_1},\widetilde{r}_{i_2},\widetilde{r}_{i_3}) ( r i 1 , r i 2 , r i 3 ) to obtain ( r i 1 , r i 2 , r i 3 ) (r_{i_1},r_{i_2},r_{i_3}) ( r i 1 , r i 2 , r i 3 ) , and let R R R be an orthogonal completion whose i 1 i_1 i 1 -th, i 2 i_2 i 2 -th, and i 3 i_3 i 3 -th columns are precisely these three vectors r i 1 , r i 2 , r i 3 ∈ R p r_{i_1},r_{i_2},r_{i_3}\in\mathbb{R}^p r i 1 , r i 2 , r i 3 ∈ R p . Finally, we set
s j = R s ~ j ∈ R p . s_j=R\widetilde{s}_j\in\mathbb{R}^p. s j = R s j ∈ R p .
To assess performance across different geometric settings, we consider Ω \Omega Ω consisting of two 2-dimensional spheres embedded in R 3 \mathbb{R}^3 R 3 , where the two spheres correspond to the two class labels. We study two choices of their locations and radii: in the first, the spheres are disjoint, both with radius 2 and centered at ( 1.5 , 1.5 , 1.5 ) T (1.5,1.5,1.5)^{\mathsf{T}} ( 1.5 , 1.5 , 1.5 ) T and ( − 1.5 , − 1.5 , − 1.5 ) T (-1.5,-1.5,-1.5)^{\mathsf{T}} ( − 1.5 , − 1.5 , − 1.5 ) T ; in the second, they are concentric, centered at the origin with radii 1 and 4. These latent structures are displayed in Figure 4.1 .
Figure 4.1. Illustration of the two parameter settings of the latent two-sphere model. Different colors denote different class labels.
Unless otherwise specified, we fix q = 1 q=1 q = 1 , set the dimension to be p = 10000 p=10000 p = 10000 , and generate 500 observations uniformly from each sphere, so that the total sample size is n = 1000 n=1000 n = 1000 . We compare the proposed method with the competing approaches on the two parameter settings of the latent two-sphere model in Figure 4.1 under a range of noise levels σ ∈ { 0.1 , 0.2 , 0.3 , 0.4 , 0.5 } \sigma\in\{0.1,0.2,0.3,0.4,0.5\} σ ∈ { 0.1 , 0.2 , 0.3 , 0.4 , 0.5 } . For the main comparison, the prescribed basis W W W in our proposed method is taken to be the same level-4 Haar basis H H H used to construct R R R . Sensitivity to basis misspecification is examined separately in § 4.4 . For classification, we use a 70/30 training–testing split, train a shallow neural network with one hidden layer of 16 ReLU units on the training embeddings, and report the classification accuracy on the test embeddings. For spectral clustering, we apply k k k -means and report the Adjusted Rand Index (ARI) [39 ] , which takes value between 0 and 1. Each experiment setup is repeated 250 times, and the reported accuracies and ARIs are averaged over these repetitions.
Classification and Clustering
The downstream classification and clustering results are reported in Figure 4.2 and Figure 4.3 .
Figure 4.2. Classification accuracy and clustering ARI for the two disjoint spheres model across varying noise levels. The reported results are based on 250 repetitions.
Figure 4.3. Classification accuracy and clustering ARI for the two-concentric-spheres model across varying noise levels. The reported results are based on 250 repetitions.
Figure 4.2 shows that, in this relatively simple two-disjoint-spheres setting, most methods perform reasonably well when the noise level is small. For classification, SPASE, KSE, Isomap, LLE, DM, and t-SNE all achieve high accuracy at low noise levels, whereas AE and DAE deteriorate rapidly as σ \sigma σ increases and approach chance-level accuracy under heavier noise. For clustering, the difference becomes more pronounced under heavier noise: SPASE and KSE remain robust, while the remaining methods show substantially larger degradation, especially AE, DAE, and t-SNE. At σ = 0.5 \sigma= 0.5 σ = 0.5 , SPASE and KSE achieve classification accuracies of 98.29% and 98.18% and ARIs of 0.924 and 0.941, respectively. Although several methods work well when the geometry is simple and the noise is mild, SPASE and KSE are the most stable at the larger noise levels.
Figure 4.3 presents results for the much more demanding two-concentric-spheres setting. As noise increases, most competing methods deteriorate in both classification and clustering. SPASE remains the most robust across the range of σ \sigma σ : its classification accuracy remains almost perfect and its clustering ARI remains high as noise increases. Among the baselines, KSE has the highest clustering ARI, but its performance is clearly below that of SPASE under moderate and high noise. At σ = 0.5 \sigma= 0.5 σ = 0.5 , SPASE attains 99.27% classification accuracy and an ARI of 0.950, compared with 50.38% and 0.020 for KSE. KSE also performs well at lower noise levels because it incorporates kernel smoothing prior to spectral embedding, partially mitigating the effect of high-dimensional noise. However, unlike our adaptive projection strategy, it constructs the kernel directly from the noisy observations, and its performance deteriorates more substantially as the noise level increases. These results support the main motivation of SPASE: reducing noise-induced distortion of pairwise distances before spectral embedding. We examine this effect directly through pairwise-distance recovery in § 4.3 .
Recovery of Pairwise Distances
We next examine the recovery of clean pairwise distances using the concentric-sphere setting as illustrated in Figure 4.1 . For a projection matrix P ^ ∈ R p × k \hat{\mathbf{P}} \in\mathbb{R}^{p \times k} P ^ ∈ R p × k , we write u ^ i = P ^ T ( x i − x ˉ ) ∈ R k \hat{\mathbf{u}}_i = \hat{\mathbf{P}}^{\mathsf{T}}(\mathbf{x}_i - \bar{\mathbf{x}}) \in\mathbb{R}^k u ^ i = P ^ T ( x i − x ˉ ) ∈ R k for the projected observations. We compare their squared pairwise distances with those between the clean signals using the relative error
E d i s t ( P ^ ) = { ∑ i < j ( ∥ u ^ i − u ^ j ∥ 2 2 − ∥ s i − s j ∥ 2 2 ) 2 } 1 / 2 { ∑ i < j ∥ s i − s j ∥ 2 4 } 1 / 2 . (32) \mathcal{E}_{\mathrm{dist}}(\hat{\mathbf{P}}) =
\frac{
\left\{
\sum_{i<j}
\left(
\lVert\hat{\mathbf{u}}_i-\hat{\mathbf{u}}_j\rVert_2^2
-
\lVert\mathbf{s}_i-\mathbf{s}_j\rVert_2^2
\right)^2
\right\}^{1/2}
}{
\left\{
\sum_{i<j}
\lVert\mathbf{s}_i-\mathbf{s}_j\rVert_2^4
\right\}^{1/2}
}. \tag*{(32)} E dist ( P ^ ) = { ∑ i < j ∥ s i − s j ∥ 2 4 } 1/2 { ∑ i < j ( ∥ u ^ i − u ^ j ∥ 2 2 − ∥ s i − s j ∥ 2 2 ) 2 } 1/2 . (32)
Alongside SPASE and no projection, i.e., P ^ = I p \hat{\mathbf{P}} = \mathbf{I}_p P ^ = I p , we include PCA and random orthonormal projections with dimensions k k k matched to the SPASE-selected K K K , and an oracle projection R \mathbf{R} R as in (12) onto the true three-dimensional signal space. All data-dependent projections are estimated from the training sample, and the relative error is evaluated on the test observations. The oracle also projects the noisy observations, so noise within the true signal space remains and its error need not be zero.
Figure 4.4 shows that projection substantially reduces the distortion of pairwise distances. At σ = 0.5 \sigma= 0.5 σ = 0.5 , the mean relative errors are 224.24 without projection, 0.833 for random projection, 0.488 for PCA, 0.313 for SPASE, and 0.276 for the oracle. SPASE achieves an error much closer to the oracle benchmark, although its projection P \mathbf{P} P in (5) is estimated from the noisy observations without knowledge of the true signal space.
This comparison illustrates the role of energy-based projection in recovering the clean pairwise geometry. In particular, at the highest noise level, the distances used by SPASE for kernel construction are much closer to the clean signal distances than those used by direct KSE. This difference is consistent with the higher classification accuracy and clustering ARI of SPASE in the concentric-sphere setting discussed in § 4.2 .
Figure 4. Relative error in squared pairwise distances for concentric spheres, averaged over 250 repetitions. Curves compare Raw (no projection), Random, SPASE, PCA, and Oracle (true signal space). Random and PCA use the SPASE-selected dimension. All projections act on noisy observations. The vertical scale is logarithmic.
Basis Misspecification
In § 4.1 , the working basis W in (2) is chosen as the level-4 Haar basis H used to generate the signals. In practice, however, the basis in which the signals admit a sparse representation is generally unknown. We therefore evaluate sensitivity to the choice of W by comparing the downstream classification performance of the matched basis with a level-2 Haar basis and level-4 Daubechies bases of orders 2 and 4 [18 ] . The alternative implementations are denoted as Haar L2, db2 L4, and db4 L4. We retain the same signal-generating mechanism and all other settings.
Figure 4.5 shows that SPASE maintains high classification accuracy with all four bases across the tested noise levels. For disjoint spheres at σ = 0.5 \sigma= 0.5 σ = 0.5 , the accuracies for Haar L4, Haar L2, db4 L4, and db2 L4 are 98.29%, 98.31%, 97.87%, and 97.82%, respectively. For comparison, KSE attains 98.18%, comparable to these four implementations. In the more challenging concentric-sphere setting at σ = 0.5 \sigma= 0.5 σ = 0.5 , the corresponding accuracies are 99.27%, 99.08%, 98.30%, and 97.34%, while KSE attains 50.38%. Thus, although changing the working basis leads to some loss of accuracy in the concentric-sphere setting, SPASE retains a substantial advantage over KSE and other methods. These results indicate that SPASE can maintain strong performance even when the working basis differs from the signal-generating basis.
Figure 4.5. Classification accuracy under basis misspecification for disjoint spheres (left) and concentric spheres (right). SPASE uses the matched Haar-L4 basis; Haar L2, db4 L4, and db2 L4 use the alternative working bases. The reported results are based on 250 repetitions.
Choice of Projection Dimension
We conduct two experiments to examine the choice of projection dimension. The first studies how the dimension K selected by Algorithm 1 adapts to sparsity and noise. The second evaluates classification accuracy across fixed projection dimensions and examines whether the adaptive selection achieves near-optimal downstream performance among them.
For the first experiment, we consider the two-disjoint-spheres setting and follow the setup in § 4.1 , with q ∈ { 0.2 , 0.3 , … , 1.6 } q \in\{0.2, 0.3, \ldots, 1.6\} q ∈ { 0.2 , 0.3 , … , 1.6 } and σ ∈ { 0.1 , 0.15 , 0.2 } \sigma\in\{0.1, 0.15, 0.2\} σ ∈ { 0.1 , 0.15 , 0.2 } . For each configuration, we apply Algorithm 1 over 250 repetitions and report the median selected dimension.
Figure 4.6 shows two clear patterns. First, the median selected dimension increases with q q q . As the coefficient magnitudes ℓ − 1 / q \ell^{-1/q} ℓ − 1/ q decay more slowly, the signal energy is spread across more basis directions, and the procedure retains more directions. Second, at a given q q q , the median selected dimension generally decreases as the noise level increases. These patterns agree with Proposition 3.4 , which characterizes how the selected dimension depends jointly on sparsity and the signal-to-noise ratio.
We next examine classification accuracy as the projection dimension varies in the concentric-sphere setting at σ = 0.3 \sigma= 0.3 σ = 0.3 and 0.5 0.5 0.5 . We compare energy-based projection, PCA, and random orthonormal projection at fixed dimensions k k k ranging from 1 to 512, each followed by KSE. At each fixed k k k , the energy-based projection retains the k k k directions with the largest empirical energies as in (3) . We also report the performance of SPASE, which selects K separately in each repetition, and use direct KSE as a reference. All methods use the same observations and training–testing splits.
Figure 4.7 shows that energy-based projection followed by KSE achieves higher mean classification accuracy than PCA+KSE and random projection followed by KSE at every tested dimension for both noise levels. At σ = 0.3 \sigma= 0.3 σ = 0.3 , adaptive SPASE selects a median dimension of 19 and attains nearly 100% accuracy; all tested dimensions between 3 and 128 also yield nearly perfect accuracy. At σ = 0.5 \sigma= 0.5 σ = 0.5 , the median selected dimension is 11, and adaptive SPASE achieves 99.27% accuracy, close to the highest mean accuracy on the tested grid, 99.34% at k = 16 k = 16 k = 16 . The tested dimensions between 8 and 32 yield accuracies ranging from 98.87% to 99.34%. At both noise levels, the median dimension selected by Algorithm 1 lies within a broad high-accuracy region, and SPASE performs close to the best accuracy on the tested grid.
Figure 4.7. Concentric-sphere classification accuracy versus the imposed projection dimension k k k . The vertical dashed line marks the median dimension K K K selected by SPASE (19 19 19 at σ = 0.3 \sigma= 0.3 σ = 0.3 and 11 11 11 at σ = 0.5 \sigma= 0.5 σ = 0.5 ). The horizontal line gives the accuracy of direct KSE. The reported results are based on 250 repetitions.
These findings indicate both the advantage of energy-based projection and the effectiveness of the adaptive dimension selection. Moreover, as discussed in § 2.1 , τ \tau τ as in (4) controls the energy-based selection cutoff. The broad high-accuracy regions suggest that moderate changes in τ \tau τ may have little effect on performance when the selected dimensions remain within these regions. This further demonstrates the robustness of SPASE.
Data Application
Data Description and Setup
Histopathology images exhibit complex local texture patterns together with substantial variability introduced by staining conditions, tissue preparation, and imaging artifacts. Although these images are represented in a high-dimensional pixel space, their intrinsic variability is believed to be governed by a much lower-dimensional manifold reflecting tissue morphology. Consequently, histopathology provides an appropriate setting for evaluating whether adaptive projection can improve the stability of manifold estimation under controlled additive perturbations of histopathology images.
To assess the practical performance of the proposed method, we use the PathMNIST dataset from the MedMNIST collection [75 , 76 ] . MedMNIST is an open-sourced lightweight benchmark suite designed for standardized evaluation on medical imaging tasks, and PathMNIST is one of its most widely used subsets. PathMNIST consists of hematoxylin and eosin (H&E) stained histological images of colorectal tissue and defines a 9-class classification problem. The class labels are: 0 (adipose), 1 (background), 2 (debris), 3 (lymphocytes), 4 (mucus), 5 (smooth muscle), 6 (normal colon mucosa), 7 (cancer-associated stroma), and 8 (colorectal adenocarcinoma epithelium). Each image has resolution 28 × 28 28 \times28 28 × 28 with three color channels, so that after vectorization each observation lies in R 2352 \mathbb{R}^{2352} R 2352 . This dataset provides a useful real-data testbed for our method: the observations are high-dimensional and strongly structured, and the downstream classification tasks remain sensitive to the quality of the learned representation. The adaptive projection is expected to suppress noise-dominated wavelet directions while preserving spatially localized morphological structures, thereby producing a more stable affinity graph for the subsequent spectral embedding. We therefore expect the proposed method to be particularly useful for this application, where robust recovery of the intrinsic data geometry is critical for downstream classification.
We evaluate the competing methods on downstream binary classification tasks formed by selecting two pairs of PathMNIST classes: 0 vs. 1 (adipose vs. background) and 6 vs. 7 (normal colon mucosa vs. cancer-associated stroma). The two class pairs were selected to represent different levels of classification difficulty. Classes 0 and 1 exhibit markedly different visual appearances, providing an easier discrimination task. In contrast, classes 6 and 7 share similar histological textures and differ through relatively subtle structural patterns, making them considerably more challenging and therefore a more stringent test of representation quality. Figure 5.1 shows examples from each class pair. We evaluate the proposed method against the following competing methods: Isomap, LLE, t-SNE, Diffusion Maps (DM), autoencoders (AE), denoising autoencoders (DAE), and KSE.
Figure 5.1. Example of PathMNIST images from classes 0 (adipose), 1 (background), 6 (normal colon mucosa), and 7 (cancer-associated stroma).
We consider two complementary evaluation tasks. In the first, we study robustness to ambient noise: for each class pair, we sample 500 observations from each class, add independent Gaussian noise with varying standard deviation σ \sigma σ , and report the resulting classification accuracy. In the second, we study sample efficiency: we vary the number of sampled observations per class, fix the noise level at σ = 0.3 \sigma= 0.3 σ = 0.3 , and again report the resulting classification accuracy. In the two tasks, the goal is to assess whether the learned representation remains informative when the data are either increasingly corrupted or limited in number.
In all experiments, we use a 70/30 training–testing split and use the vectorized two-dimensional discrete Haar wavelet basis induced by level-3 discrete multiresolution decomposition as the basis W in our proposed method. We use a downstream classifier with the same one-hidden-layer, 16-ReLU-unit architecture as in § 4.1 . For each setup, we conduct the analysis over 100 independent resamples of the data and report the mean performance across these runs.
Accuracy of Classification
The results for the PathMNIST class pairs are reported in Figure 5.2 and Figure 5.3 . SPASE is competitive on the easier pair and has a larger advantage over KSE on the harder pair as the noise level increases.
(a) Accuracy vs. Noise Level
(b) Accuracy vs. Sample Size
Figure 5.2. Classification accuracy for PathMNIST classes 0 and 1 (adipose vs. background). The left panel shows performance under increasing noise with 500 samples per class; the right panel shows performance under varying sample sizes with fixed noise level σ = 0.3 \sigma= 0.3 σ = 0.3 .
Figure 5.3. Classification accuracy for PathMNIST classes 6 and 7 (normal colon mucosa vs. cancer-associated stroma). The left panel shows performance under increasing noise with 500 samples per class; the right panel shows performance under varying sample sizes with fixed noise level σ = 0.3 \sigma= 0.3 σ = 0.3 .
Figure 5.2 corresponds to the easy task classes 0 vs. 1 (adipose vs. background). In this case, all methods achieve relatively high classification accuracy, and SPASE remains consistently competitive and stable across both the noise-robustness and sample-size experiments.
Figure 5.3 corresponds to the difficult task classes 6 vs. 7 (normal colon mucosa vs. cancer-associated stroma). In this setting, SPASE consistently outperforms the competing methods as the noise level increases. At σ = 0.1 \sigma= 0.1 σ = 0.1 , SPASE and KSE, the strongest competing method, achieve comparable classification accuracies of 90.7% and 90.5%, respectively. At the highest noise level σ = 0.5 \sigma= 0.5 σ = 0.5 , however, SPASE maintains an accuracy of 76.7%, compared with 70.4% for KSE, corresponding to an improvement of approximately 6.3 percentage points.
A similar pattern is observed in the sample-size experiment. With only 300 observations per class, SPASE achieves an accuracy of 83.9%, compared with 80.2% for KSE, an improvement of approximately 3.7 percentage points. As the sample size increases, the gap narrows: with 1500 observations per class, SPASE and KSE achieve accuracies of 87.7% and 86.7%, respectively. These comparisons indicate that the benefit of adaptive projection is particularly visible in the more challenging regimes of stronger noise and limited sample size.
For the tissue images, we do not know in advance which basis best concentrates the signal. We chose the level-3 two-dimensional Haar basis because its detail coefficients describe local intensity contrasts at several spatial scales. This gives us a way to represent tissue texture without choosing the basis from the class labels or the classification results. In § 4.4 , several working bases gave high accuracy even though only one matched the generating basis. Here the same Haar basis was used for both tissue pairs, and the energy-based rule determined which of its directions to retain.
The comparison of normal colon mucosa with cancer-associated stroma illustrates the proposed role of screening. The two tissues have similar textures. Direct KSE uses distances between the full images, so differences due to noise in many pixels can accumulate in each squared distance. SPASE first screens the Haar directions by their variation across images. If the local contrasts that distinguish the tissues vary enough to be retained, weaker directions can be discarded before their noise enters the distance calculation. The near tie under mild added noise and the gain of 6.3 percentage points over KSE at σ = 0.5 \sigma= 0.5 σ = 0.5 in Figure 5.3 are consistent with this explanation.
Additional Simulation Results
In this appendix, we report additional downstream classification and clustering results for the two-moons model, which are omitted from the main text for brevity. The data are generated in the same way as in Section 4.1, with the following two-moons latent coordinates. More specifically, the first two latent coordinates are generated from a two-moons model (see, e.g., [53 ] ), while the third coordinate is independently sampled from a uniform distribution on [ − 0.15 , 0.15 ] \left[-0.15,0.15\right] [ − 0.15 , 0.15 ] , as illustrated in Figure A.1.
Figure A.1. The two-moons manifold. Different colors denote different class labels.
Figure A.2 reports the downstream classification accuracy and clustering ARI across varying noise levels. For classification, SPASE with the matched Haar-L4 basis achieves the highest mean accuracy among the plotted methods at each of the five noise levels. Additional runs with the alternative bases display a similar pattern, with Haar-L2 and db4-L4 remaining close to the matched implementation over most noise levels, while db2-L4 exhibits a more noticeable loss under stronger noise. At σ = 0.5 \sigma= 0.5 σ = 0.5 , the classification accuracies of SPASE with Haar-L4, Haar-L2, db4-L4, and db2-L4 are approximately 68.8%, 67.3%, 65.3%, and 60.3%, respectively, compared with 50.2% for KSE and accuracies close to chance level for most of the remaining baselines.
For clustering, SPASE’s mean ARI decreases from 0.310 at σ = 0.1 \sigma= 0.1 σ = 0.1 to 0.202 at σ = 0.5 \sigma= 0.5 σ = 0.5 . At the lowest noise level, t-SNE has a similar ARI of 0.309, but its performance deteriorates more rapidly as noise increases. At σ = 0.5 \sigma= 0.5 σ = 0.5 , KSE has an ARI of 0.005, while most remaining baselines are close to zero. Additional runs with Haar-L2, db4-L4, and db2-L4 give ARIs of 0.183, 0.157, and 0.094, respectively. Although the absolute ARIs are lower than in the sphere examples, SPASE retains more clustering information as the noise increases.
On the two-moons data, SPASE improves on direct KSE in both classification and clustering across the tested noise levels. At σ = 0.5 \sigma= 0.5 σ = 0.5 , this advantage persists with each of the three alternative bases, although the gains are smaller with db2-L4 than with Haar-L2 or db4-L4. These results complement the basis comparisons in § 4.4 .
Figure A.2. Classification accuracy and clustering ARI for the two-moons model across varying noise levels. The reported results are based on 250 repetitions.
Additional Real-Data Results
In this appendix, we report additional real-data results for the PathMNIST classification task formed by classes 2 and 8, corresponding to debris and colorectal adenocarcinoma epithelium, respectively. This class pair is omitted from the main text for brevity.
Figure B.1 reports the results for classes 2 vs. 8 (debris vs. colorectal adenocarcinoma epithelium). As the noise level increases, most baseline methods deteriorate steadily, whereas the proposed method has the highest mean accuracy at the four larger noise levels. KSE is again the closest competing baseline and is slightly more accurate than SPASE at σ = 0.1 \sigma= 0.1 σ = 0.1 . The same pattern appears in the sample-size experiment: SPASE leads at smaller sample sizes, but its mean accuracy is nearly identical to that of KSE at 1500 observations per class. Overall, SPASE is among the most accurate methods across both the noise-robustness and sample-size experiments.
Figure B.1. Classification accuracy for PathMNIST classes 2 and 8 (debris vs. colorectal adenocarcinoma epithelium). The left panel shows performance under increasing noise with 500 samples per class; the right panel shows performance under varying sample sizes with fixed noise level σ = 0.3 \sigma= 0.3 σ = 0.3 .
Technical Proofs
Proofs for Recovery of Pairwise Distances
In this subsection, we prove Proposition 3.4 and Theorem 3.6 . Define
A : = W T ( r 1 , … , r r ) ∈ R p × r , (33) A := \mathbf{W}^{\mathsf{T}}(r_1,\ldots,r_r) \in\mathbb{R}^{p \times r}, \tag*{(33)} A := W T ( r 1 , … , r r ) ∈ R p × r , (33)
so that, for each k = 1 , … , r k=1,\ldots,r k = 1 , … , r ,
r k = ∑ j = 1 p a j k w j . (34) r_k = \sum_{j=1}^{p} a_{jk}w_j. \tag*{(34)} r k = j = 1 ∑ p a j k w j . (34)
Let A j ⋅ A_{j\cdot} A j ⋅ denote the j j j -th row of A A A , and define the Euclidean row norms by
ρ j : = ∥ A j ⋅ ∥ 2 , j = 1 , … , p . (35) \rho_j := \lVert A_{j\cdot}\rVert_2,\qquad j=1,\ldots,p. \tag*{(35)} ρ j := ∥ A j ⋅ ∥ 2 , j = 1 , … , p . (35)
Lemma C.1 (Decay of row norms). Under Assumption 3.3, there exist constants 0 < c − ≤ c + < ∞ 0<c_- \le c_+<\infty 0 < c − ≤ c + < ∞ , depending only on ( c k ) k ∈ [ r ] (c_k)_{k\in[r]} ( c k ) k ∈ [ r ] , ( C k ) k ∈ [ r ] (C_k)_{k\in[r]} ( C k ) k ∈ [ r ] , q q q , and r r r , such that
c − m − 1 / q ≤ ρ ( m ) ≤ c + m − 1 / q , m = 1 , … , p , c_-m^{-1/q}\le\rho_{(m)}\le c_+m^{-1/q},\qquad m=1,\ldots,p, c − m − 1/ q ≤ ρ ( m ) ≤ c + m − 1/ q , m = 1 , … , p , where ρ ( 1 ) ≥ ρ ( 2 ) ≥ ⋯ ≥ ρ ( p ) \rho_{(1)}\ge\rho_{(2)}\ge\cdots\ge\rho_{(p)} ρ ( 1 ) ≥ ρ ( 2 ) ≥ ⋯ ≥ ρ ( p ) denotes the nonincreasing rearrangement of { ρ j } j = 1 p \{\rho_j\}_{j=1}^{p} { ρ j } j = 1 p .
Proof. We first prove the upper bound. For t > 0 t>0 t > 0 , define
S t : = { j : ρ j ≥ t } . (36) S_t:=\{j:\rho_j\ge t\}. \tag*{(36)} S t := { j : ρ j ≥ t } . (36)
For any j ∈ S t j\in S_t j ∈ S t , we have ρ j 2 = ∑ k = 1 r a j k 2 ≥ t 2 \rho_j^2=\sum_{k=1}^r a_{jk}^2\ge t^2 ρ j 2 = ∑ k = 1 r a j k 2 ≥ t 2 , so there exists some k ∈ [ r ] k\in[r] k ∈ [ r ] such that ∣ a j k ∣ ≥ t / r |a_{jk}|\ge t/\sqrt{r} ∣ a j k ∣ ≥ t / r . Hence
S t ⊆ ⋃ k = 1 r { j : ∣ a j k ∣ ≥ t / r } , S_t\subseteq\bigcup_{k=1}^r\{j:|a_{jk}|\ge t/\sqrt{r}\}, S t ⊆ k = 1 ⋃ r { j : ∣ a j k ∣ ≥ t / r } ,
and therefore
∣ S t ∣ ≤ ∑ k = 1 r # { j : ∣ a j k ∣ ≥ t / r } . (37) |S_t|\le\sum_{k=1}^r\#\{j:|a_{jk}|\ge t/\sqrt{r}\}. \tag*{(37)} ∣ S t ∣ ≤ k = 1 ∑ r # { j : ∣ a j k ∣ ≥ t / r } . (37)
By Assumption 3.3, for each k ∈ [ r ] k\in[r] k ∈ [ r ] and u > 0 u>0 u > 0 ,
# { j : ∣ a j k ∣ ≥ u } ≤ ( C k / u ) q . \#\{j:|a_{jk}|\ge u\}\le(C_k/u)^q. # { j : ∣ a j k ∣ ≥ u } ≤ ( C k / u ) q .
Taking u = t / r u=t/\sqrt{r} u = t / r , we obtain
# { j : ∣ a j k ∣ ≥ t / r } ≤ ( C k r / t ) q . \#\{j:|a_{jk}|\ge t/\sqrt{r}\}\le(C_k\sqrt{r}/t)^q. # { j : ∣ a j k ∣ ≥ t / r } ≤ ( C k r / t ) q .
Combining this with (C.5), we get
∣ S t ∣ ≤ ∑ k = 1 r ( C k r / t ) q ≤ ( c + / t ) q |S_t|\le\sum_{k=1}^r(C_k\sqrt{r}/t)^q\le(c_+/t)^q ∣ S t ∣ ≤ k = 1 ∑ r ( C k r / t ) q ≤ ( c + / t ) q
for some constant c + > 0 c_+>0 c + > 0 depending only on ( C k ) k ∈ [ r ] (C_k)_{k\in[r]} ( C k ) k ∈ [ r ] , q q q , and r r r . Setting t = ρ ( m ) t=\rho_{(m)} t = ρ ( m ) yields
m ≤ ∣ S ρ ( m ) ∣ ≤ ( c + / ρ ( m ) ) q , m\le|S_{\rho_{(m)}}|\le(c_+/\rho_{(m)})^q, m ≤ ∣ S ρ ( m ) ∣ ≤ ( c + / ρ ( m ) ) q ,
which implies
ρ ( m ) ≤ c + m − 1 / q . \rho_{(m)}\le c_+m^{-1/q}. ρ ( m ) ≤ c + m − 1/ q .
We next prove the lower bound. For each j = 1 , … , p j=1,\ldots,p j = 1 , … , p and each k ∈ [ r ] k\in[r] k ∈ [ r ] , we have
ρ j = ( ∑ ℓ = 1 r a j ℓ 2 ) 1 / 2 ≥ ∣ a j k ∣ . \rho_j=\left(\sum_{\ell=1}^r a_{j\ell}^2\right)^{1/2}\ge|a_{jk}|. ρ j = ( ℓ = 1 ∑ r a j ℓ 2 ) 1/2 ≥ ∣ a j k ∣.
Therefore, for every fixed k ∈ [ r ] k\in[r] k ∈ [ r ] , the decreasing rearrangements satisfy
ρ ( m ) ≥ ∣ a ( m ) k ∣ , m = 1 , … , p . \rho_{(m)}\ge|a_{(m)k}|,\qquad m=1,\ldots,p. ρ ( m ) ≥ ∣ a ( m ) k ∣ , m = 1 , … , p .
By Assumption 3.3,
∣ a ( m ) k ∣ ≥ c k m − 1 / q . |a_{(m)k}|\ge c_km^{-1/q}. ∣ a ( m ) k ∣ ≥ c k m − 1/ q .
Hence, for each k ∈ [ r ] k\in[r] k ∈ [ r ] ,
ρ ( m ) ≥ c k m − 1 / q . \rho_{(m)}\ge c_km^{-1/q}. ρ ( m ) ≥ c k m − 1/ q .
This implies
ρ ( m ) ≥ c − m − 1 / q , m = 1 , … , p , \rho_{(m)}\ge c_-m^{-1/q},\qquad m=1,\ldots,p, ρ ( m ) ≥ c − m − 1/ q , m = 1 , … , p ,
for some constant c − > 0 c_->0 c − > 0 . Combining the upper and lower bounds completes the proof.
Lemma C.1 shows that the ordered row norms ρ ( m ) \rho^{(m)} ρ ( m ) inherit the same decay. We next show that the empirical coordinate energies concentrate uniformly around their population counterparts, which allows Algorithm 1 to recover the correct order of the selected projection dimension. Recall that Σ = Cov ( s i 0 ) \Sigma= \operatorname{Cov}(s_i^0) Σ = Cov ( s i 0 ) with s i 0 s_i^0 s i 0 as in (12) . The population variance corresponding to the sample energy E j E_j E j in (3) is
κ j : = Var ( x i T w j ) = σ 2 + A j Σ A j T , j = 1 , … , p . (38) \kappa_j := \operatorname{Var}(x_i^{\mathsf T}w_j) = \sigma^2 + A_j\Sigma A_j^{\mathsf T}, \qquad j=1,\ldots,p. \tag*{(38)} κ j := Var ( x i T w j ) = σ 2 + A j Σ A j T , j = 1 , … , p . (38)
Because the energy uses denominator n n n after sample centering, E E j = ( 1 − 1 / n ) κ j \mathbb{E}E_j=(1-1/n)\kappa_j E E j = ( 1 − 1/ n ) κ j . If κ j = 0 \kappa_j=0 κ j = 0 , then E j = 0 E_j=0 E j = 0 almost surely; ratios below are interpreted as zero on those coordinates.
Lemma C.3 (Concentration of empirical energies). Under Assumptions 3.1 and 3.2,
max 1 ≤ j ≤ p ∣ E j − κ j ∣ κ j = O ≺ ( log n n ) . \max_{1\le j\le p}\frac{|E_j-\kappa_j|}{\kappa_j}=O_{\prec}\left(\sqrt{\frac{\log n}{n}}\right). 1 ≤ j ≤ p max κ j ∣ E j − κ j ∣ = O ≺ ( n log n ) .
Proof. Write m 0 = E s i 0 m_0=\mathbb{E}s_i^0 m 0 = E s i 0 and m = R r m 0 = E x i m=R_rm_0=\mathbb{E}x_i m = R r m 0 = E x i . Compactness in Assumption 3.2 gives ∥ s i 0 ∥ 2 ≤ R \|s_i^0\|_2\le R ∥ s i 0 ∥ 2 ≤ R and ∥ s i 0 − m 0 ∥ 2 ≤ 2 R \|s_i^0-m_0\|_2\le2R ∥ s i 0 − m 0 ∥ 2 ≤ 2 R for a constant R R R . The covariance eigenvalues λ 1 0 , … , λ r 0 \lambda_1^0,\ldots,\lambda_r^0 λ 1 0 , … , λ r 0 are positive constants, so Θ ≍ 1 \Theta\asymp1 Θ ≍ 1 .
Fix j ∈ { 1 , … , p } j\in\{1,\ldots,p\} j ∈ { 1 , … , p } . Recall from (3) that
Y i j : = ( x i − m ) T w j , Y ‾ j = 1 n ∑ i Y i j , Y_{ij}:=(x_i-m)^{\mathsf T}w_j,\qquad\overline{Y}_j=\frac{1}{n}\sum_iY_{ij}, Y ij := ( x i − m ) T w j , Y j = n 1 i ∑ Y ij ,
E j = E ~ j − Y ‾ j 2 , E ~ j = 1 n ∑ i Y i j 2 . E_j=\widetilde{E}_j-\overline{Y}_j^2,\qquad\widetilde{E}_j=\frac{1}{n}\sum_iY_{ij}^2. E j = E j − Y j 2 , E j = n 1 i ∑ Y ij 2 .
Write
Y i j = S i j + Z i j , S i j : = ( s i − m ) T w j , Z i j : = z i T w j . Y_{ij}=S_{ij}+Z_{ij},\qquad S_{ij}:=(s_i-m)^{\mathsf T}w_j,\qquad Z_{ij}:=z_i^{\mathsf T}w_j. Y ij = S ij + Z ij , S ij := ( s i − m ) T w j , Z ij := z i T w j .
By construction, $\mathbb{E}Y_{ij}=\mathbb{E}S_{ij}=0.
We first control the noise part. By Assumption 3.2 and the convention in Remark C.2 , z i z_i z i is a centered sub-Gaussian random vector with covariance matrix σ 2 I p \sigma^2 I_p σ 2 I p . Hence there exists a constant C > 0 C > 0 C > 0 independent of n n n and p p p such that, for every deterministic vector a ∈ R p \mathbf{a} \in\mathbb{R}^p a ∈ R p and every t ∈ R t \in\mathbb{R} t ∈ R ,
E exp ( t a T z i ) ≤ exp ( C σ 2 t 2 ∥ a ∥ 2 2 ) . \mathbb{E}\exp(t\mathbf{a}^{\mathsf{T}}\mathbf{z}_i) \le\exp(C\sigma^2t^2\|\mathbf{a}\|_2^2). E exp ( t a T z i ) ≤ exp ( C σ 2 t 2 ∥ a ∥ 2 2 ) .
Taking a = w j \mathbf{a}=\mathbf{w}_j a = w j and using ∥ w j ∥ 2 = 1 \|\mathbf{w}_j\|_2=1 ∥ w j ∥ 2 = 1 , we obtain
E exp ( t Z i j ) = E exp ( t w j T z i ) ≤ exp ( C σ 2 t 2 ) , t ∈ R . (39) \mathbb{E}\exp(tZ_{ij})=\mathbb{E}\exp(t\mathbf{w}_j^{\mathsf{T}}\mathbf{z}_i)\le\exp(C\sigma^2t^2), \qquad t\in\mathbb{R}. \tag*{(39)} E exp ( t Z ij ) = E exp ( t w j T z i ) ≤ exp ( C σ 2 t 2 ) , t ∈ R . (39)
We next control the signal part. By Assumption 3.1 and (12) , we have s i = ∑ k = 1 r s i k r k \mathbf{s}_i=\sum_{k=1}^r s_{ik}\mathbf{r}_k s i = ∑ k = 1 r s ik r k , and therefore
S i j = ( s i − m ) T w j = A j ⋅ ( s i 0 − m 0 ) . S_{ij}=(\mathbf{s}_i-\mathbf{m})^{\mathsf{T}}\mathbf{w}_j=A_{j\cdot}(\mathbf{s}_i^0-\mathbf{m}_0). S ij = ( s i − m ) T w j = A j ⋅ ( s i 0 − m 0 ) .
Using the bound ∥ s i 0 − m 0 ∥ 2 ≤ 2 R \|\mathbf{s}_i^0-\mathbf{m}_0\|_2\le2R ∥ s i 0 − m 0 ∥ 2 ≤ 2 R above, we obtain
∣ S i j ∣ = ∣ A j ⋅ ( s i 0 − m 0 ) ∣ ≤ ∥ A j ⋅ ∥ 2 ∥ s i 0 − m 0 ∥ 2 ≤ 2 R ρ j . (40) |S_{ij}|=|A_{j\cdot}(\mathbf{s}_i^0-\mathbf{m}_0)|\le\|A_{j\cdot}\|_2\|\mathbf{s}_i^0-\mathbf{m}_0\|_2\le2R\rho_j. \tag*{(40)} ∣ S ij ∣ = ∣ A j ⋅ ( s i 0 − m 0 ) ∣ ≤ ∥ A j ⋅ ∥ 2 ∥ s i 0 − m 0 ∥ 2 ≤ 2 R ρ j . (40)
Since S i j S_{ij} S ij is bounded, there exists a constant C 1 ≥ C > 0 C_1\ge C>0 C 1 ≥ C > 0 independent of n n n and p p p such that
E exp ( t ( S i j − E S i j ) ) ≤ exp ( C 1 ρ j 2 t 2 ) , t ∈ R . (41) \mathbb{E}\exp(t(S_{ij}-\mathbb{E}S_{ij}))\le\exp(C_1\rho_j^2t^2), \qquad t\in\mathbb{R}. \tag*{(41)} E exp ( t ( S ij − E S ij )) ≤ exp ( C 1 ρ j 2 t 2 ) , t ∈ R . (41)
Since s i \mathbf{s}_i s i and z i \mathbf{z}_i z i are independent, (C.7) and (C.9) yield
E exp ( t ( Y i j − E Y i j ) ) = E exp ( t ( S i j − E S i j ) ) E exp ( t Z i j ) ≤ exp ( C 1 ( ρ j 2 + σ 2 ) t 2 ) , t ∈ R . (42) \begin{aligned}
\mathbb{E}\exp(t(Y_{ij}-\mathbb{E}Y_{ij}))=\mathbb{E}\exp(t(S_{ij}-\mathbb{E}S_{ij}))\mathbb{E}\exp(tZ_{ij}) \\
&\le\exp(C_1(\rho_j^2+\sigma^2)t^2), \qquad t\in\mathbb{R}. \tag*{(42)}
\end{aligned} E exp ( t ( Y ij − E Y ij )) = E exp ( t ( S ij − E S ij )) E exp ( t Z ij ) ≤ exp ( C 1 ( ρ j 2 + σ 2 ) t 2 ) , t ∈ R . (42)
Thus Y i j − E Y i j Y_{ij}-\mathbb{E}Y_{ij} Y ij − E Y ij is a centered sub-Gaussian random variable with variance proxy of order ρ j 2 + σ 2 \rho_j^2+\sigma^2 ρ j 2 + σ 2 . Since the eigenvalues of Σ \Sigma Σ are fixed positive constants, there exist constants 0 < c Σ ≤ C Σ < ∞ 0<c_\Sigma\le C_\Sigma<\infty 0 < c Σ ≤ C Σ < ∞ such that
c Σ Θ ρ j 2 ≤ A j ⋅ Σ A j ⋅ T ≤ C Σ Θ ρ j 2 . c_\Sigma\Theta\rho_j^2\le A_{j\cdot}\Sigma A_{j\cdot}^{\mathsf{T}}\le C_\Sigma\Theta\rho_j^2. c Σ Θ ρ j 2 ≤ A j ⋅ Σ A j ⋅ T ≤ C Σ Θ ρ j 2 .
Therefore
κ j = σ 2 + A j ⋅ Σ A j ⋅ T ≍ σ 2 + Θ ρ j 2 . (43) \kappa_j=\sigma^2+A_{j\cdot}\Sigma A_{j\cdot}^{\mathsf{T}}\asymp\sigma^2+\Theta\rho_j^2. \tag*{(43)} κ j = σ 2 + A j ⋅ Σ A j ⋅ T ≍ σ 2 + Θ ρ j 2 . (43)
Since Θ \Theta Θ is fixed, (C.10) and (C.11) imply that Y i j − E Y i j Y_{ij}-\mathbb{E}Y_{ij} Y ij − E Y ij is sub-Gaussian with variance proxy of order κ j \kappa_j κ j . Hence, by the fact that the square of a sub-Gaussian random variable is sub-exponential,
Y i j 2 − κ j Y_{ij}^2-\kappa_j Y ij 2 − κ j
is sub-exponential with scale of order κ j \kappa_j κ j . By Bernstein’s inequality (Lemma E.1 ), we obtain that for any t > 0 t>0 t > 0 ,
P ( ∣ E ^ j − κ j ∣ κ j > t ) ≤ 2 exp ( − c n min ( t 2 , t ) ) . (44) \mathbb{P}\left(\frac{|\widehat{\mathcal{E}}_j-\kappa_j|}{\kappa_j}>t\right)\le2\exp\left(-cn\min(t^2,t)\right). \tag*{(44)} P ( κ j ∣ E j − κ j ∣ > t ) ≤ 2 exp ( − c n min ( t 2 , t ) ) . (44)
for some constant c > 0 c>0 c > 0 independent of n n n and p p p .
The mean Y ˉ j \bar{Y}_j Y ˉ j is sub-Gaussian with scale C κ j / n C\sqrt{\kappa_j/n} C κ j / n . Hence
P ( Y ˉ j 2 > κ j t ) ≤ 2 e − c n t . \mathbb{P}(\bar{Y}_j^2>\kappa_jt)\le2e^{-cnt}. P ( Y ˉ j 2 > κ j t ) ≤ 2 e − c n t .
For 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 , the identity E j = E ~ j − Y ˉ j 2 E_j=\widetilde{E}_j-\bar{Y}_j^2 E j = E j − Y ˉ j 2 and a union bound give
P ( ∣ E j − κ j ∣ > 2 κ j t ) ≤ 2 e − c n t 2 + 2 e − c n t . \mathbb{P}(|E_j-\kappa_j|>2\kappa_jt)\le2e^{-cnt^2}+2e^{-cnt}. P ( ∣ E j − κ j ∣ > 2 κ j t ) ≤ 2 e − c n t 2 + 2 e − c n t .
Thus the sample-centering correction is of smaller order and the same concentration conclusion follows.
Taking
t = n ε log n n t=n^\varepsilon\sqrt{\frac{\log n}{n}} t = n ε n log n
for any fixed 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 , and using that p ≍ n α p\asymp n^\alpha p ≍ n α , a union bound over j = 1 , … , p j=1,\ldots,p j = 1 , … , p yields
max 1 ≤ j ≤ p ∣ E j − κ j ∣ κ j = O P ( log n n ) . \max_{1\le j\le p}\frac{|E_j-\kappa_j|}{\kappa_j}
=O_{\mathbb{P}}\left(\sqrt{\frac{\log n}{n}}\right). 1 ≤ j ≤ p max κ j ∣ E j − κ j ∣ = O P ( n log n ) .
We now prove Proposition 3.4 .
Proof of Proposition 3.4. Let
d j : = A j ⋅ Σ A j T , κ j : = σ 2 + d j , d_j:=A_j\cdot\Sigma A_j^{\mathsf T},\qquad\kappa_j:=\sigma^2+d_j, d j := A j ⋅ Σ A j T , κ j := σ 2 + d j ,
and let
d ( 1 ) ≥ ⋯ ≥ d ( p ) , κ ( 1 ) ≥ ⋯ ≥ κ ( p ) d_{(1)}\ge\cdots\ge d_{(p)},\qquad\kappa_{(1)}\ge\cdots\ge\kappa_{(p)} d ( 1 ) ≥ ⋯ ≥ d ( p ) , κ ( 1 ) ≥ ⋯ ≥ κ ( p )
denote the corresponding decreasing rearrangements. Since the eigenvalues of Σ \Sigma Σ are fixed positive constants, there exist constants 0 < c Σ < C Σ < ∞ 0<c_\Sigma<C_\Sigma<\infty 0 < c Σ < C Σ < ∞ such that
c Σ Θ ρ j 2 ≤ A j ⋅ Σ A j T ≤ C Σ Θ ρ j 2 , j = 1 , … , p . (45) c_\Sigma\Theta\rho_j^2\le A_j\cdot\Sigma A_j^{\mathsf T}\le C_\Sigma\Theta\rho_j^2,\qquad j=1,\ldots,p. \tag*{(45)} c Σ Θ ρ j 2 ≤ A j ⋅ Σ A j T ≤ C Σ Θ ρ j 2 , j = 1 , … , p . (45)
By Lemma C.1 , there exist constants 0 < c − < c + < ∞ 0<c_-<c_+<\infty 0 < c − < c + < ∞ such that
c − m − 1 / q ≤ ρ ( m ) ≤ c + m − 1 / q , m = 1 , … , p . c_-m^{-1/q}\le\rho_{(m)}\le c_+m^{-1/q},\qquad m=1,\ldots,p. c − m − 1/ q ≤ ρ ( m ) ≤ c + m − 1/ q , m = 1 , … , p .
Combining this with (C.13), we obtain constants 0 < a 1 < a 2 < ∞ 0<a_1<a_2<\infty 0 < a 1 < a 2 < ∞ such that
a 1 Θ m − 2 / q ≤ d ( m ) ≤ a 2 Θ m − 2 / q , m = 1 , … , p . (46) a_1\Theta m^{-2/q}\le d_{(m)}\le a_2\Theta m^{-2/q},\qquad m=1,\ldots,p. \tag*{(46)} a 1 Θ m − 2/ q ≤ d ( m ) ≤ a 2 Θ m − 2/ q , m = 1 , … , p . (46)
Hence
κ ( m ) = σ 2 + d ( m ) ≍ σ 2 + Θ m − 2 / q , m = 1 , … , p . (47) \kappa_{(m)}=\sigma^2+d_{(m)}\asymp\sigma^2+\Theta m^{-2/q},\qquad m=1,\ldots,p. \tag*{(47)} κ ( m ) = σ 2 + d ( m ) ≍ σ 2 + Θ m − 2/ q , m = 1 , … , p . (47)
Define the ordered population tail average
κ ˉ t a i l : = 1 s ∑ ℓ = p + 1 − s p κ ( ℓ ) . \bar{\kappa}_{\mathrm{tail}} := \frac{1}{s}\sum_{\ell=p+1-s}^{p}\kappa_{(\ell)}. κ ˉ tail := s 1 ℓ = p + 1 − s ∑ p κ ( ℓ ) .
Write E ˉ t a i l = s − 1 ∑ ℓ = p + 1 − s p E ( ℓ ) = σ ^ 2 \bar{E}_{\mathrm{tail}}=s^{-1}\sum_{\ell=p+1-s}^{p}E_{(\ell)}=\hat{\sigma}^{2} E ˉ tail = s − 1 ∑ ℓ = p + 1 − s p E ( ℓ ) = σ ^ 2 . Since s s s is fixed, (C.14) implies
κ ˉ t a i l = σ 2 + 1 s ∑ ℓ = p + 1 − s p d ( ℓ ) ≤ σ 2 + Θ p − 2 / q . (48) \bar{\kappa}_{\mathrm{tail}}=\sigma^{2}+\frac{1}{s}\sum_{\ell=p+1-s}^{p}d_{(\ell)}\leq\sigma^{2}+\Theta p^{-2/q}. \tag*{(48)} κ ˉ tail = σ 2 + s 1 ℓ = p + 1 − s ∑ p d ( ℓ ) ≤ σ 2 + Θ p − 2/ q . (48)
By Lemma C.3 , we have
max 1 ≤ j ≤ p ∣ E j − κ j ∣ κ j = O ( 1 n ) . \max_{1\leq j\leq p}\frac{\lvert E_j-\kappa_j\rvert}{\kappa_j}=O\left(\frac{1}{\sqrt{n}}\right). 1 ≤ j ≤ p max κ j ∣ E j − κ j ∣ = O ( n 1 ) .
Hence, for any fixed δ > 0 \delta>0 δ > 0 , with high probability, for sufficiently large n n n ,
( 1 − δ ) κ j ≤ E j ≤ ( 1 + δ ) κ j , j = 1 , … , p . (1-\delta)\kappa_j\leq E_j\leq(1+\delta)\kappa_j,\qquad j=1,\ldots,p. ( 1 − δ ) κ j ≤ E j ≤ ( 1 + δ ) κ j , j = 1 , … , p .
Rearranging these inequalities yields
( 1 − δ ) κ ( m ) ≤ E ( m ) ≤ ( 1 + δ ) κ ( m ) , m = 1 , … , p , (1-\delta)\kappa_{(m)}\leq E_{(m)}\leq(1+\delta)\kappa_{(m)},\qquad m=1,\ldots,p, ( 1 − δ ) κ ( m ) ≤ E ( m ) ≤ ( 1 + δ ) κ ( m ) , m = 1 , … , p ,
and averaging over the last s s s ordered terms gives
( 1 − δ ) κ ˉ t a i l ≤ E ˉ t a i l ≤ ( 1 + δ ) κ ˉ t a i l . (49) (1-\delta)\bar{\kappa}_{\mathrm{tail}}\leq\bar{E}_{\mathrm{tail}}\leq(1+\delta)\bar{\kappa}_{\mathrm{tail}}. \tag*{(49)} ( 1 − δ ) κ ˉ tail ≤ E ˉ tail ≤ ( 1 + δ ) κ ˉ tail . (49)
Choose δ > 0 \delta>0 δ > 0 small enough so that
u 1 : = ( 1 + τ ) ( 1 + δ ) 1 − δ > 1 , u 2 : = ( 1 + τ ) ( 1 − δ ) 1 + δ > 1. u_1:=\frac{(1+\tau)(1+\delta)}{1-\delta}>1,\qquad u_2:=\frac{(1+\tau)(1-\delta)}{1+\delta}>1. u 1 := 1 − δ ( 1 + τ ) ( 1 + δ ) > 1 , u 2 := 1 + δ ( 1 + τ ) ( 1 − δ ) > 1.
Define
N 1 : = max { m : κ ( m ) ≥ u 1 κ ˉ t a i l } , N 2 : = max { m : κ ( m ) ≥ u 2 κ ˉ t a i l } . N_1:=\max\{m:\kappa_{(m)}\geq u_1\bar{\kappa}_{\mathrm{tail}}\},\qquad N_2:=\max\{m:\kappa_{(m)}\geq u_2\bar{\kappa}_{\mathrm{tail}}\}. N 1 := max { m : κ ( m ) ≥ u 1 κ ˉ tail } , N 2 := max { m : κ ( m ) ≥ u 2 κ ˉ tail } .
Use zero for the maximum of an empty index set. On the simultaneous coordinate-concentration event above, on which (C.17) also holds, if κ ( m ) ≥ u 1 κ ˉ t a i l \kappa_{(m)}\geq u_1\bar{\kappa}_{\mathrm{tail}} κ ( m ) ≥ u 1 κ ˉ tail , then
E ( m ) ≥ ( 1 − δ ) κ ( m ) ≥ ( 1 + τ ) ( 1 + δ ) κ ˉ t a i l ≥ ( 1 + τ ) E ˉ t a i l , E_{(m)}\geq(1-\delta)\kappa_{(m)}\geq(1+\tau)(1+\delta)\bar{\kappa}_{\mathrm{tail}}\geq(1+\tau)\bar{E}_{\mathrm{tail}}, E ( m ) ≥ ( 1 − δ ) κ ( m ) ≥ ( 1 + τ ) ( 1 + δ ) κ ˉ tail ≥ ( 1 + τ ) E ˉ tail ,
which implies m ≤ K m\leq K m ≤ K . Hence
N 1 ≤ K . (50) N_1\leq K. \tag*{(50)} N 1 ≤ K . (50)
Similarly, if κ ( m ) < u 2 κ ˉ t a i l \kappa_{(m)}<u_2\bar{\kappa}_{\mathrm{tail}} κ ( m ) < u 2 κ ˉ tail , then
E ( m ) ≤ ( 1 + δ ) κ ( m ) < ( 1 + τ ) ( 1 − δ ) κ ˉ t a i l ≤ ( 1 + τ ) E ˉ t a i l , E_{(m)}\leq(1+\delta)\kappa_{(m)}<(1+\tau)(1-\delta)\bar{\kappa}_{\mathrm{tail}}\leq(1+\tau)\bar{E}_{\mathrm{tail}}, E ( m ) ≤ ( 1 + δ ) κ ( m ) < ( 1 + τ ) ( 1 − δ ) κ ˉ tail ≤ ( 1 + τ ) E ˉ tail ,
so m > K m>K m > K . Therefore
K ≤ N 2 . (51) K\le N_2. \tag*{(51)} K ≤ N 2 . (51)
For each fixed u > 1 u>1 u > 1 , the inequality
κ ( m ) ≥ u κ ˉ t a i l \kappa_{(m)}\ge u\bar{\kappa}_{\mathrm{tail}} κ ( m ) ≥ u κ ˉ tail
holds if and only if
d ( m ) ≥ ( u − 1 ) σ 2 + u s ∑ ℓ = p + 1 − s p d ( ℓ ) . d_{(m)}\ge(u-1)\sigma^2+\frac{u}{s}\sum_{\ell=p+1-s}^{p}d_{(\ell)}. d ( m ) ≥ ( u − 1 ) σ 2 + s u ℓ = p + 1 − s ∑ p d ( ℓ ) .
By (C.14), the expression on the right is bounded above and below by constant multiples of B n : = σ 2 + Θ p − 2 / q B_n:=\sigma^2+\Theta p^{-2/q} B n := σ 2 + Θ p − 2/ q . Define L n : = ( Θ / B n ) q / 2 ≤ p L_n:=(\Theta/B_n)^{q/2}\le p L n := ( Θ/ B n ) q /2 ≤ p . We now apply this observation to the thresholds u 1 u_1 u 1 and u 2 u_2 u 2 . By the lower bound in (C.14), we can choose a fixed b 0 ∈ ( 0 , 1 ) b_0\in(0,1) b 0 ∈ ( 0 , 1 ) sufficiently small so that κ ( m ) ≥ u 1 κ ˉ t a i l \kappa_{(m)}\ge u_1\bar{\kappa}_{\mathrm{tail}} κ ( m ) ≥ u 1 κ ˉ tail whenever m ≤ b 0 L n m\le b_0L_n m ≤ b 0 L n . Similarly, the upper bound gives a fixed C > 0 C>0 C > 0 sufficiently large so that κ ( m ) < u 2 κ ˉ t a i l \kappa_{(m)}<u_2\bar{\kappa}_{\mathrm{tail}} κ ( m ) < u 2 κ ˉ tail whenever m > C L n m>CL_n m > C L n . It follows from the definitions of N 1 N_1 N 1 and N 2 N_2 N 2 that
⌈ b 0 L n ⌉ ≤ N 1 ≤ N 2 ≤ C L n . \lceil b_0L_n\rceil\le N_1\le N_2\le CL_n. ⌈ b 0 L n ⌉ ≤ N 1 ≤ N 2 ≤ C L n .
The condition σ 2 / Θ = o ( 1 ) \sigma^2/\Theta=o(1) σ 2 /Θ = o ( 1 ) in the proposition implies L n → ∞ L_n\to\infty L n → ∞ . Thus, for all sufficiently large n n n , we have L n ≥ 2 / b 0 L_n\ge2/b_0 L n ≥ 2/ b 0 and hence ⌈ b 0 L n ⌉ ≥ b 0 L n / 2 \lceil b_0L_n\rceil\ge b_0L_n/2 ⌈ b 0 L n ⌉ ≥ b 0 L n /2 . Taking b 1 = b 0 / 2 b_1=b_0/2 b 1 = b 0 /2 and b 2 > C b_2>C b 2 > C , we obtain
b 1 ( Θ σ 2 + Θ p − 2 / q ) q / 2 ≤ N 1 ≤ N 2 ≤ b 2 ( Θ σ 2 + Θ p − 2 / q ) q / 2 . (52) b_1\left(\frac{\Theta}{\sigma^2+\Theta p^{-2/q}}\right)^{q/2}\le N_1\le N_2\le b_2\left(\frac{\Theta}{\sigma^2+\Theta p^{-2/q}}\right)^{q/2}. \tag*{(52)} b 1 ( σ 2 + Θ p − 2/ q Θ ) q /2 ≤ N 1 ≤ N 2 ≤ b 2 ( σ 2 + Θ p − 2/ q Θ ) q /2 . (52)
Combining (C.18), (C.19), and (C.20), we obtain that, with probability tending to one,
K ≍ ( Θ σ 2 + Θ p − 2 / q ) q / 2 . (53) K\asymp\left(\frac{\Theta}{\sigma^2+\Theta p^{-2/q}}\right)^{q/2}. \tag*{(53)} K ≍ ( σ 2 + Θ p − 2/ q Θ ) q /2 . (53)
If S N R ≲ p 2 / q − 1 \mathrm{SNR}\lesssim p^{2/q-1} SNR ≲ p 2/ q − 1 , then Θ p − 2 / q ≲ σ 2 \Theta p^{-2/q}\lesssim\sigma^2 Θ p − 2/ q ≲ σ 2 , so
σ 2 + Θ p − 2 / q ≍ σ 2 . \sigma^2+\Theta p^{-2/q}\asymp\sigma^2. σ 2 + Θ p − 2/ q ≍ σ 2 .
Substituting this into (C.21) yields
K ≍ ( Θ / σ 2 ) q / 2 . K\asymp(\Theta/\sigma^2)^{q/2}. K ≍ ( Θ/ σ 2 ) q /2 .
If S N R ≳ p 2 / q − 1 \mathrm{SNR}\gtrsim p^{2/q-1} SNR ≳ p 2/ q − 1 , then σ 2 ≲ Θ p − 2 / q \sigma^2\lesssim\Theta p^{-2/q} σ 2 ≲ Θ p − 2/ q , so
σ 2 + Θ p − 2 / q ≍ Θ p − 2 / q . \sigma^2+\Theta p^{-2/q}\asymp\Theta p^{-2/q}. σ 2 + Θ p − 2/ q ≍ Θ p − 2/ q .
Substituting this into (C.21) yields
The same counting bound will also be used in the recovery proofs below. It only requires L n ≥ 2 / b 0 L_n \ge2/b_0 L n ≥ 2/ b 0 . Set c ∗ = ( b 0 / 2 ) q / 2 c_*=(b_0/2)^{q/2} c ∗ = ( b 0 /2 ) q /2 . For sufficiently large p p p , the condition σ 2 / Θ ≤ c ∗ \sigma^2/\Theta\le c_* σ 2 /Θ ≤ c ∗ gives L n ≥ ( 2 c ∗ ) − q / 2 = 2 / b 0 L_n \ge(2c_*)^{-q/2}=2/b_0 L n ≥ ( 2 c ∗ ) − q /2 = 2/ b 0 . Thus, on the same concentration event,
K = ( Θ σ 2 + Θ p − 2 / q ) q / 2 , σ 2 / Θ ≤ c ∗ . (54) \mathcal{K}=\left(\frac{\Theta}{\sigma^2+\Theta p^{-2/q}}\right)^{q/2}, \qquad\sigma^2/\Theta\le c_*. \tag*{(54)} K = ( σ 2 + Θ p − 2/ q Θ ) q /2 , σ 2 /Θ ≤ c ∗ . (54)
The comparison constants are uniform in this range. This completes the proof.
With Proposition 3.4 in hand, we next study how accurately the selected projection reconstructs the underlying signal subspace. This subspace reconstruction error will then be translated into a uniform bound for the projected clean pairwise distances. Define
U : = span { r 1 , … , r r } ⊂ R p , \mathcal{U}:=\operatorname{span}\{r_1,\ldots,r_r\}\subset\mathbb{R}^p, U := span { r 1 , … , r r } ⊂ R p ,
and let Π U \Pi_{\mathcal{U}} Π U denote the orthogonal projector onto U \mathcal{U} U . Recall that Π P = P P T \Pi_{\mathsf{P}}=\mathsf{P}\mathsf{P}^{\mathsf{T}} Π P = P P T projects onto the selected basis directions. The error in the following lemma is the largest norm of the discarded component ( I − Π P ) v (I-\Pi_{\mathsf{P}})v ( I − Π P ) v over unit vectors v ∈ U v\in\mathcal{U} v ∈ U .
Lemma C.4 (Signal-subspace reconstruction error). Let I K \mathcal{I}_{K} I K be the index set selected by Algorithm 1. Then
∥ ( I − Π P ) Π U ∥ o p ≤ ( ∑ j ∉ I K ρ j 2 ) 1 / 2 . \left\|(I-\Pi_{\mathsf{P}})\Pi_{\mathcal{U}}\right\|_{\mathrm{op}}
\le\left(\sum_{j\notin\mathcal{I}_{K}}\rho_j^2\right)^{1/2}. ∥ ( I − Π P ) Π U ∥ op ≤ j ∈ / I K ∑ ρ j 2 1/2 .
Proof. Let R r = ( r 1 , … , r r ) ∈ R p × r R_r=(r_1,\ldots,r_r)\in\mathbb{R}^{p\times r} R r = ( r 1 , … , r r ) ∈ R p × r , so that U = Col ( R r ) \mathcal{U}=\operatorname{Col}(R_r) U = Col ( R r ) and Π U = R r R r T \Pi_{\mathcal{U}}=R_rR_r^{\mathsf{T}} Π U = R r R r T . Since the columns of R r R_r R r are orthonormal, we have
∥ ( I − Π P ) Π U ∥ o p ≤ ∥ ( I − Π P ) Π U ∥ F = ∥ ( I − Π P ) R r R r T ∥ F ≤ ∥ ( I − Π P ) R r ∥ F . \left\|(I-\Pi_{\mathsf{P}})\Pi_{\mathcal{U}}\right\|_{\mathrm{op}}
\le\left\|(I-\Pi_{\mathsf{P}})\Pi_{\mathcal{U}}\right\|_{\mathrm{F}}
= \left\|(I-\Pi_{\mathsf{P}})R_rR_r^{\mathsf{T}}\right\|_{\mathrm{F}}
\le\left\|(I-\Pi_{\mathsf{P}})R_r\right\|_{\mathrm{F}}. ∥ ( I − Π P ) Π U ∥ op ≤ ∥ ( I − Π P ) Π U ∥ F = ( I − Π P ) R r R r T F ≤ ∥ ( I − Π P ) R r ∥ F .
By (C.1), we have R r = W A R_r=WA R r = W A . Since Π P \Pi_{\mathsf{P}} Π P is the orthogonal projector onto Col ( W I K ) \operatorname{Col}(W_{\mathcal{I}_{K}}) Col ( W I K ) ,
( I − Π P ) R r = ( I − Π P ) W A = W I K c A I K c , : . (I-\Pi_{\mathsf{P}})R_r=(I-\Pi_{\mathsf{P}})WA=W_{\mathcal{I}_{K}^{c}}A_{\mathcal{I}_{K}^{c},:}. ( I − Π P ) R r = ( I − Π P ) W A = W I K c A I K c , : .
Using the orthonormality of W W W , we obtain
∥ ( I − Π P ) R r ∥ F 2 = ∥ A I K c , : ∥ F 2 = ∑ j ∉ I K ∥ A j , : ∥ 2 2 = ∑ j ∉ I K ρ j 2 . \left\|(I-\Pi_{\mathsf{P}})R_r\right\|_{\mathrm{F}}^2
=\left\|A_{\mathcal{I}_{K}^{c},:}\right\|_{\mathrm{F}}^2
=\sum_{j\notin\mathcal{I}_{K}}\|A_{j,:}\|_2^2
=\sum_{j\notin\mathcal{I}_{K}}\rho_j^2. ∥ ( I − Π P ) R r ∥ F 2 = A I K c , : F 2 = j ∈ / I K ∑ ∥ A j , : ∥ 2 2 = j ∈ / I K ∑ ρ j 2 .
Taking square roots completes the proof.
Theorem C.5 (Convergence of signal-subspace reconstruction). Suppose Assumptions 3.1, 3.2, and 3.3 hold. Then
∥ ( I − Π P ) Π U ∥ o p 2 = { O ( ( Θ σ 2 ) q / 2 − 1 ) , if SNR ≲ p 2 / q − 1 , O ( p 1 − 2 / q ) , if SNR ≳ p 2 / q − 1 . \left\|(I-\Pi_{\mathsf{P}})\Pi_{\mathcal{U}}\right\|_{\mathrm{op}}^2
=
\begin{cases}
O\left(\left(\dfrac{\Theta}{\sigma^2}\right)^{q/2-1}\right), & \text{if SNR}\lesssim p^{2/q-1},\\
O\left(p^{1-2/q}\right), & \text{if SNR}\gtrsim p^{2/q-1}.
\end{cases} ∥ ( I − Π P ) Π U ∥ op 2 = ⎩ ⎨ ⎧ O ( ( σ 2 Θ ) q /2 − 1 ) , O ( p 1 − 2/ q ) , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 .
Proof. Let I K ⊂ [ p ] \mathcal{I}_{K} \subset[p] I K ⊂ [ p ] be the index set selected by Algorithm 1. By definition, ∣ I K ∣ = K |\mathcal{I}_{K}| = K ∣ I K ∣ = K . If K = p K=p K = p , the residual is zero and the claimed bound holds. We may therefore assume K < p K<p K < p . Let t n = σ 2 / Θ t_n=\sigma^2/\Theta t n = σ 2 /Θ , and recall c ⋆ c_\star c ⋆ from (C.22). If t n > c ⋆ t_n>c_\star t n > c ⋆ , then for all sufficiently large n n n , we are in the first SNR regime and have t n 1 − q / 2 ≥ c ⋆ 1 − q / 2 > 0 t_n^{1-q/2}\ge c_\star^{1-q/2}>0 t n 1 − q /2 ≥ c ⋆ 1 − q /2 > 0 . Since we also have ∥ ( I − Π P ) Π U ∥ o p ≤ 1 \lVert(\mathbf{I}-\boldsymbol{\Pi}_{P})\boldsymbol{\Pi}_{U}\rVert_{\mathrm{op}}\le1 ∥( I − Π P ) Π U ∥ op ≤ 1 , we obtain the desired bound in this case.
It remains to consider t n ≤ c ⋆ t_n\le c_\star t n ≤ c ⋆ . On the concentration event associated with (C.22), we have K ≥ 1 K\ge1 K ≥ 1 for all sufficiently large n n n . We work on this event below, so that 1 ≤ K < p 1\le K<p 1 ≤ K < p and the counting bound (C.22) applies. When defining the population top-K K K index set below, we break ties by index. With this convention, we define the population top-K K K index set by
I ⋆ : = { j ∈ [ p ] : ρ j is among the K largest of ( ρ 1 , … , ρ p ) } , \mathcal{I}^{\star}:=\{j\in[p]:\rho_j\text{ is among the }K\text{ largest of }(\rho_1,\ldots,\rho_p)\}, I ⋆ := { j ∈ [ p ] : ρ j is among the K largest of ( ρ 1 , … , ρ p )} ,
and recall that ρ ( 1 ) ≥ ρ ( 2 ) ≥ ⋯ ≥ ρ ( p ) \rho_{(1)}\ge\rho_{(2)}\ge\cdots\ge\rho_{(p)} ρ ( 1 ) ≥ ρ ( 2 ) ≥ ⋯ ≥ ρ ( p ) denotes the nonincreasing rearrangement of { ρ j } j = 1 p \{\rho_j\}_{j=1}^{p} { ρ j } j = 1 p .
By Lemma C.4, we bound the squared residual by the sum of squared row norms over the discarded directions. Splitting this sum according to I ⋆ \mathcal{I}^{\star} I ⋆ , we obtain
∥ ( I − Π P ) Π U ∥ o p 2 ≤ ∑ j ∉ I K ρ j 2 ≤ ∑ j ∉ I ⋆ ρ j 2 + ∑ j ∈ I ⋆ ∖ I K ρ j 2 . (55) \lVert(\mathbf{I}-\boldsymbol{\Pi}_{P})\boldsymbol{\Pi}_{U}\rVert_{\mathrm{op}}^{2}
\le\sum_{j\notin\mathcal{I}_{K}}\rho_j^2
\le\sum_{j\notin\mathcal{I}^{\star}}\rho_j^2+\sum_{j\in\mathcal{I}^{\star}\setminus\mathcal{I}_{K}}\rho_j^2. \tag*{(55)} ∥( I − Π P ) Π U ∥ op 2 ≤ j ∈ / I K ∑ ρ j 2 ≤ j ∈ / I ⋆ ∑ ρ j 2 + j ∈ I ⋆ ∖ I K ∑ ρ j 2 . (55)
We first control ∑ j ∉ I ⋆ ρ j 2 \sum_{j\notin\mathcal{I}^{\star}}\rho_j^2 ∑ j ∈ / I ⋆ ρ j 2 . By Lemma C.1 , ρ ( m ) ≤ C ′ m − 1 / q \rho_{(m)}\le C'm^{-1/q} ρ ( m ) ≤ C ′ m − 1/ q for some constant C ′ > 0 C'>0 C ′ > 0 . Hence
∑ j ∉ I ⋆ ρ j 2 = ∑ m = K + 1 p ρ ( m ) 2 ≤ ∑ m = K + 1 ∞ ( C ′ m − 1 / q ) 2 ≲ K 1 − 2 / q . (56) \sum_{j\notin\mathcal{I}^{\star}}\rho_j^2
=\sum_{m=K+1}^{p}\rho_{(m)}^2
\le\sum_{m=K+1}^{\infty}(C'm^{-1/q})^2
\lesssim K^{1-2/q}. \tag*{(56)} j ∈ / I ⋆ ∑ ρ j 2 = m = K + 1 ∑ p ρ ( m ) 2 ≤ m = K + 1 ∑ ∞ ( C ′ m − 1/ q ) 2 ≲ K 1 − 2/ q . (56)
To bound the second term in (C.23), we define
S m i s s : = I ⋆ ∖ I K , S a d d : = I K ∖ I ⋆ . S_{\mathrm{miss}}:=\mathcal{I}^{\star}\setminus\mathcal{I}_{K},\qquad
S_{\mathrm{add}}:=\mathcal{I}_{K}\setminus\mathcal{I}^{\star}. S miss := I ⋆ ∖ I K , S add := I K ∖ I ⋆ .
Then ∣ S m i s s ∣ = ∣ S a d d ∣ ≤ K |S_{\mathrm{miss}}|=|S_{\mathrm{add}}|\le K ∣ S miss ∣ = ∣ S add ∣ ≤ K . By Lemma C.3 , we have
max 1 ≤ j ≤ p ∣ E j − κ j ∣ κ j = O ( log n n ) . \max_{1\le j\le p}\frac{|E_j-\kappa_j|}{\kappa_j}
=O\left(\sqrt{\frac{\log n}{n}}\right). 1 ≤ j ≤ p max κ j ∣ E j − κ j ∣ = O ( n log n ) .
Fix 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 and set
δ n : = n ε log n n . \delta_n:=n^\varepsilon\sqrt{\frac{\log n}{n}}. δ n := n ε n log n .
For all sufficiently large n n n , we have δ n ≤ 1 / 3 \delta_n\le1/3 δ n ≤ 1/3 . The preceding concentration bound gives, with high probability,
max 1 ≤ j ≤ p ∣ E j − κ j ∣ κ j ≤ δ n . \max_{1\le j\le p}\frac{|E_j-\kappa_j|}{\kappa_j}\le\delta_n. 1 ≤ j ≤ p max κ j ∣ E j − κ j ∣ ≤ δ n .
For each j ∈ S m i s s j\in S_{\mathrm{miss}} j ∈ S miss , the equality ∣ S m i s s ∣ = ∣ S a d d ∣ |S_{\mathrm{miss}}|=|S_{\mathrm{add}}| ∣ S miss ∣ = ∣ S add ∣ allows us to choose l ∈ S a d d l\in S_{\mathrm{add}} l ∈ S add . Since l l l is selected and j j j is not, the empirical ordering gives E l ≥ E j E_l\ge E_j E l ≥ E j . We therefore have
κ l ( 1 + δ n ) ≥ E l ≥ E j ≥ κ j ( 1 − δ n ) , \kappa_l(1+\delta_n)\ge E_l\ge E_j\ge\kappa_j(1-\delta_n), κ l ( 1 + δ n ) ≥ E l ≥ E j ≥ κ j ( 1 − δ n ) ,
which implies
κ j ≤ κ l 1 + δ n 1 − δ n ≤ ( 1 + 3 δ n ) κ l . \kappa_j \le\kappa_l \frac{1+\delta_n}{1-\delta_n} \le(1+3\delta_n)\kappa_l. κ j ≤ κ l 1 − δ n 1 + δ n ≤ ( 1 + 3 δ n ) κ l .
Equivalently,
κ j − σ 2 ≤ ( κ l − σ 2 ) + 3 δ n κ l . (57) \kappa_j-\sigma^2 \le(\kappa_l-\sigma^2)+3\delta_n\kappa_l. \tag*{(57)} κ j − σ 2 ≤ ( κ l − σ 2 ) + 3 δ n κ l . (57)
Since κ j = σ 2 + A j ⋅ Σ A j T \kappa_j=\sigma^2+A_j\cdot\Sigma A_j^{\mathsf T} κ j = σ 2 + A j ⋅ Σ A j T and the eigenvalues of Σ \Sigma Σ are fixed positive constants, there exist constants 0 < c Σ < C Σ < ∞ 0<c_\Sigma<C_\Sigma<\infty 0 < c Σ < C Σ < ∞ such that
c Σ Θ ρ j 2 ≤ κ j − σ 2 ≤ C Σ Θ ρ j 2 , κ l ≤ σ 2 + C Σ Θ ρ l 2 . (58) c_\Sigma\Theta\rho_j^2\le\kappa_j-\sigma^2\le C_\Sigma\Theta\rho_j^2,\qquad\kappa_l\le\sigma^2+C_\Sigma\Theta\rho_l^2. \tag*{(58)} c Σ Θ ρ j 2 ≤ κ j − σ 2 ≤ C Σ Θ ρ j 2 , κ l ≤ σ 2 + C Σ Θ ρ l 2 . (58)
Combining (C.25) and (C.26) yields
c Σ Θ ρ j 2 ≤ C Σ Θ ρ l 2 + 3 δ n ( σ 2 + C Σ Θ ρ l 2 ) . c_\Sigma\Theta\rho_j^2\le C_\Sigma\Theta\rho_l^2+3\delta_n(\sigma^2+C_\Sigma\Theta\rho_l^2). c Σ Θ ρ j 2 ≤ C Σ Θ ρ l 2 + 3 δ n ( σ 2 + C Σ Θ ρ l 2 ) .
Hence, for some constant C > 0 C>0 C > 0 ,
ρ j 2 ≤ C ( 1 + δ n ) ρ l 2 + C δ n σ 2 Θ . \rho_j^2\le C(1+\delta_n)\rho_l^2+C\delta_n\frac{\sigma^2}{\Theta}. ρ j 2 ≤ C ( 1 + δ n ) ρ l 2 + C δ n Θ σ 2 .
Since l ∈ S a d d ⊆ ( I ⋆ ) c l\in S_{\mathrm{add}}\subseteq(I^\star)^c l ∈ S add ⊆ ( I ⋆ ) c , we have ρ l ≤ ρ ( K + 1 ) \rho_l\le\rho_{(K+1)} ρ l ≤ ρ ( K + 1 ) . Therefore,
ρ j 2 ≤ C ( 1 + δ n ) ρ ( K + 1 ) 2 + C δ n σ 2 Θ , j ∈ S m i s s . \rho_j^2\le C(1+\delta_n)\rho_{(K+1)}^2+C\delta_n\frac{\sigma^2}{\Theta},\qquad j\in S_{\mathrm{miss}}. ρ j 2 ≤ C ( 1 + δ n ) ρ ( K + 1 ) 2 + C δ n Θ σ 2 , j ∈ S miss .
Summing over j ∈ S m i s s j\in S_{\mathrm{miss}} j ∈ S miss gives
∑ j ∈ S m i s s ρ j 2 ≤ C K ( 1 + δ n ) ρ ( K + 1 ) 2 + C K δ n σ 2 Θ . \sum_{j\in S_{\mathrm{miss}}}\rho_j^2\le CK(1+\delta_n)\rho_{(K+1)}^2+CK\delta_n\frac{\sigma^2}{\Theta}. j ∈ S miss ∑ ρ j 2 ≤ C K ( 1 + δ n ) ρ ( K + 1 ) 2 + C K δ n Θ σ 2 .
Since ρ ( K + 1 ) 2 ≲ K − 2 / q \rho_{(K+1)}^2\lesssim K^{-2/q} ρ ( K + 1 ) 2 ≲ K − 2/ q by Lemma C.1 , we obtain
∑ j ∈ S m i s s ρ j 2 ≲ ( 1 + δ n ) K 1 − 2 / q + K δ n σ 2 Θ . (59) \sum_{j\in S_{\mathrm{miss}}}\rho_j^2\lesssim(1+\delta_n)K^{1-2/q}+K\delta_n\frac{\sigma^2}{\Theta}. \tag*{(59)} j ∈ S miss ∑ ρ j 2 ≲ ( 1 + δ n ) K 1 − 2/ q + K δ n Θ σ 2 . (59)
Combining the tail bound (C.24) and the missed-direction bound (C.27) with (C.23), and using δ n ≤ 1 / 3 \delta_n\le1/3 δ n ≤ 1/3 , we obtain
∥ ( I − Π P ) Π U ∥ o p 2 ≲ K 1 − 2 / q + K δ n σ 2 Θ . (60) \left\|(I-\Pi_P)\Pi_U\right\|_{\mathrm{op}}^2\lesssim K^{1-2/q}+K\delta_n\frac{\sigma^2}{\Theta}. \tag*{(60)} ∥ ( I − Π P ) Π U ∥ op 2 ≲ K 1 − 2/ q + K δ n Θ σ 2 . (60)
We now apply the counting bound (C.22) in the two SNR regimes. If S N R ≲ σ 2 / q − 1 \mathrm{SNR}\lesssim\sigma^{2/q-1} SNR ≲ σ 2/ q − 1 , we have K ≍ ( Θ / σ 2 ) q / 2 K\asymp(\Theta/\sigma^2)^{q/2} K ≍ ( Θ/ σ 2 ) q /2 . Substituting this order into the two terms in (C.28), we obtain
K 1 − 2 / q ≍ ( Θ σ 2 ) q / 2 − 1 , K σ 2 Θ δ n ≍ ( Θ σ 2 ) q / 2 − 1 δ n . K^{1-2/q}\asymp\left(\frac{\Theta}{\sigma^2}\right)^{q/2-1},\qquad K\frac{\sigma^2}{\Theta}\delta_n\asymp\left(\frac{\Theta}{\sigma^2}\right)^{q/2-1}\delta_n. K 1 − 2/ q ≍ ( σ 2 Θ ) q /2 − 1 , K Θ σ 2 δ n ≍ ( σ 2 Θ ) q /2 − 1 δ n .
Since δ n = o ( 1 ) \delta_n=o(1) δ n = o ( 1 ) , we obtain
∥ ( I − Π P ) Π U ∥ o p 2 = O ≲ ( ( Θ σ 2 ) q / 2 − 1 ) . \left\|(I-\Pi_P)\Pi_U\right\|_{\mathrm{op}}^2=O_{\lesssim}\left(\left(\frac{\Theta}{\sigma^2}\right)^{q/2-1}\right). ∥ ( I − Π P ) Π U ∥ op 2 = O ≲ ( ( σ 2 Θ ) q /2 − 1 ) .
If S N R ≳ p 2 / q − 1 \mathrm{SNR}\gtrsim p^{2/q-1} SNR ≳ p 2/ q − 1 , the same counting bound gives K ≍ p K\asymp p K ≍ p . In this regime, we also have σ 2 ≲ Θ p − 2 / q \sigma^2\lesssim\Theta p^{-2/q} σ 2 ≲ Θ p − 2/ q , and hence
K σ 2 Θ δ n ≲ p 1 − 2 / q δ n . K\frac{\sigma^2}{\Theta}\delta_n\lesssim p^{1-2/q}\delta_n. K Θ σ 2 δ n ≲ p 1 − 2/ q δ n .
Substituting these bounds into (C.28), we obtain
∥ ( I − Π P ) Π U ∥ o p 2 = O ≲ ( p 1 − 2 / q ) . \left\|(I-\Pi_P)\Pi_U\right\|_{\mathrm{op}}^2=O_{\lesssim}\left(p^{1-2/q}\right). ∥ ( I − Π P ) Π U ∥ op 2 = O ≲ ( p 1 − 2/ q ) .
This completes the proof.
Lemma C.6 (Clean pairwise-distance bound). Under Assumptions 3.1 , 3.2, and 3.3,
max 1 ≤ i < j ≤ n ∣ ∥ P T ( s i − s j ) ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ = { O ≲ ( ( Θ σ 2 ) q / 2 − 1 ) , if S N R ≲ p 2 / q − 1 , O ≲ ( p 1 − 2 / q ) , if S N R ≳ p 2 / q − 1 . \max_{1\leq i<j\leq n}\left|\left\|\mathrm{P}^{\mathsf T}(s_i-s_j)\right\|_2^2-\left\|s_i-s_j\right\|_2^2\right|=
\begin{cases}
O_{\lesssim}\left(\left(\frac{\Theta}{\sigma^2}\right)^{q/2-1}\right), & \text{if }\mathrm{SNR}\lesssim p^{2/q-1},\\
O_{\lesssim}\left(p^{1-2/q}\right), & \text{if }\mathrm{SNR}\gtrsim p^{2/q-1}.
\end{cases} 1 ≤ i < j ≤ n max P T ( s i − s j ) 2 2 − ∥ s i − s j ∥ 2 2 = { O ≲ ( ( σ 2 Θ ) q /2 − 1 ) , O ≲ ( p 1 − 2/ q ) , if SNR ≲ p 2/ q − 1 , if SNR ≳ p 2/ q − 1 . Proof. Let
Δ s i j : = s i − s j . \Delta s_{ij}:=s_i-s_j. Δ s ij := s i − s j . Since s i , s j ∈ U s_i,s_j\in\mathcal{U} s i , s j ∈ U , we have Δ s i j ∈ U \Delta s_{ij}\in\mathcal{U} Δ s ij ∈ U . Therefore,
∣ ∥ P T ( s i − s j ) ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ = ∣ ∥ Π P Δ s i j ∥ 2 2 − ∥ Δ s i j ∥ 2 2 ∣ = ∥ ( I − Π P ) Δ s i j ∥ 2 2 ≤ ∥ ( I − Π P ) Π U ∥ o p 2 ∥ Δ s i j ∥ 2 2 . (61) \left|\left\|\mathrm{P}^{\mathsf T}(s_i-s_j)\right\|_2^2-\left\|s_i-s_j\right\|_2^2\right|
=\left|\left\|\Pi_P\Delta s_{ij}\right\|_2^2-\left\|\Delta s_{ij}\right\|_2^2\right|
=\left\|(I-\Pi_P)\Delta s_{ij}\right\|_2^2
\leq\left\|(I-\Pi_P)\Pi_U\right\|_{\mathrm{op}}^2\left\|\Delta s_{ij}\right\|_2^2. \tag*{(61)} P T ( s i − s j ) 2 2 − ∥ s i − s j ∥ 2 2 = ∥ Π P Δ s ij ∥ 2 2 − ∥ Δ s ij ∥ 2 2 = ∥ ( I − Π P ) Δ s ij ∥ 2 2 ≤ ∥ ( I − Π P ) Π U ∥ op 2 ∥ Δ s ij ∥ 2 2 . (61) By Assumption 3.2, the latent vectors s i 0 s_i^0 s i 0 have compact support, so there exists a constant D > 0 D>0 D > 0 such that
∥ s i − s j ∥ 2 = ∥ s i 0 − s j 0 ∥ 2 ≤ D , 1 ≤ i , j ≤ n . \left\|s_i-s_j\right\|_2=\left\|s_i^0-s_j^0\right\|_2\leq D,\qquad1\leq i,j\leq n. ∥ s i − s j ∥ 2 = s i 0 − s j 0 2 ≤ D , 1 ≤ i , j ≤ n . Hence (C.29) yields
max 1 ≤ i < j ≤ n ∣ ∥ P T ( s i − s j ) ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ ≤ D 2 ∥ ( I − Π P ) Π U ∥ o p 2 . \max_{1\leq i<j\leq n}\left|\left\|\mathrm{P}^{\mathsf T}(s_i-s_j)\right\|_2^2-\left\|s_i-s_j\right\|_2^2\right|
\leq D^2\left\|(I-\Pi_P)\Pi_U\right\|_{\mathrm{op}}^2. 1 ≤ i < j ≤ n max P T ( s i − s j ) 2 2 − ∥ s i − s j ∥ 2 2 ≤ D 2 ∥ ( I − Π P ) Π U ∥ op 2 . By Theorem C.5 , this gives the desired result.
Lemma C.6 controls the signal-only projection bias. To complete the pairwise-distance analysis, it remains to bound the stochastic contribution from the projected noise and the signal–noise interaction term.
Lemma C.7 (Uniform control of projected noise terms). Under Assumptions 3.1, 3.2 and 3.3, we have
max 1 ≤ i < j ≤ n ∥ P T ( z i − z j ) ∥ 2 2 = O ≺ ( σ 2 K ) \max_{1\le i<j\le n}\left\|\mathrm{P}^{\mathsf{T}}(\mathbf{z}_i-\mathbf{z}_j)\right\|_2^2=O_{\prec}(\sigma^2 K) 1 ≤ i < j ≤ n max P T ( z i − z j ) 2 2 = O ≺ ( σ 2 K ) and
max 1 ≤ i < j ≤ n ∣ ( P T ( s i − s j ) ) T P T ( z i − z j ) ∣ = O ≺ ( σ K ( 1 − 1 / q ) + ) . \max_{1\le i<j\le n}\left|(\mathrm{P}^{\mathsf{T}}(\mathbf{s}_i-\mathbf{s}_j))^{\mathsf{T}}\mathrm{P}^{\mathsf{T}}(\mathbf{z}_i-\mathbf{z}_j)\right|=O_{\prec}\left(\sigma K^{(1-1/q)_+}\right). 1 ≤ i < j ≤ n max ( P T ( s i − s j ) ) T P T ( z i − z j ) = O ≺ ( σ K ( 1 − 1/ q ) + ) .
Proof. For 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n , write
Δ z i j : = z i − z j , Δ s i j : = s i − s j . \Delta\mathbf{z}_{ij}:=\mathbf{z}_i-\mathbf{z}_j,\qquad\Delta\mathbf{s}_{ij}:=\mathbf{s}_i-\mathbf{s}_j. Δ z ij := z i − z j , Δ s ij := s i − s j .
We first prove the bound for the pure noise term. By the definition of the selected index set I K \mathcal{I}_K I K and the projector Π P = P P T \Pi_{\mathrm{P}}=\mathrm{P}\mathrm{P}^{\mathsf{T}} Π P = P P T , we have
Π P = ∑ ℓ ∈ I K w ℓ w ℓ T . \Pi_{\mathrm{P}}=\sum_{\ell\in\mathcal{I}_K}\mathbf{w}_{\ell}\mathbf{w}_{\ell}^{\mathsf{T}}. Π P = ℓ ∈ I K ∑ w ℓ w ℓ T .
and therefore
∥ P T Δ z i j ∥ 2 2 = Δ z i j T Π P Δ z i j = ∑ ℓ ∈ I K ( w ℓ T Δ z i j ) 2 ≤ K max 1 ≤ ℓ ≤ p ( w ℓ T Δ z i j ) 2 . \left\|\mathrm{P}^{\mathsf{T}}\Delta\mathbf{z}_{ij}\right\|_2^2=\Delta\mathbf{z}_{ij}^{\mathsf{T}}\Pi_{\mathrm{P}}\Delta\mathbf{z}_{ij}=\sum_{\ell\in\mathcal{I}_K}\left(\mathbf{w}_{\ell}^{\mathsf{T}}\Delta\mathbf{z}_{ij}\right)^2\le K\max_{1\le\ell\le p}\left(\mathbf{w}_{\ell}^{\mathsf{T}}\Delta\mathbf{z}_{ij}\right)^2. P T Δ z ij 2 2 = Δ z ij T Π P Δ z ij = ℓ ∈ I K ∑ ( w ℓ T Δ z ij ) 2 ≤ K 1 ≤ ℓ ≤ p max ( w ℓ T Δ z ij ) 2 .
By Assumption 3.2, each Δ z i j \Delta\mathbf{z}_{ij} Δ z ij is a centered sub-Gaussian random vector with independent entries and covariance matrix 2 σ 2 I p 2\sigma^2\mathrm{I}_p 2 σ 2 I p . Hence, by the tail bound for linear forms of centered sub-Gaussian random vectors, there exists a constant c > 0 c>0 c > 0 independent of n n n and p p p such that for every nonzero deterministic vector a ∈ R p \mathbf{a}\in\mathbb{R}^p a ∈ R p ,
P ( ∣ a T Δ z i j ∣ > u ) ≤ 2 exp ( − c u 2 σ 2 ∥ a ∥ 2 2 ) , u > 0. \mathbb{P}\left(\left|\mathbf{a}^{\mathsf{T}}\Delta\mathbf{z}_{ij}\right|>u\right)\le2\exp\left(-\frac{cu^2}{\sigma^2\|\mathbf{a}\|_2^2}\right),\qquad u>0. P ( a T Δ z ij > u ) ≤ 2 exp ( − σ 2 ∥ a ∥ 2 2 c u 2 ) , u > 0.
Taking a = w ℓ \mathbf{a}=\mathbf{w}_{\ell} a = w ℓ and using ∥ w ℓ ∥ 2 = 1 \|\mathbf{w}_{\ell}\|_2=1 ∥ w ℓ ∥ 2 = 1 , we obtain
P ( ∣ w ℓ T Δ z i j ∣ > u ) ≤ 2 exp ( − c u 2 σ 2 ) , u > 0. \mathbb{P}\left(\left|\mathbf{w}_{\ell}^{\mathsf{T}}\Delta\mathbf{z}_{ij}\right|>u\right)\le2\exp\left(-\frac{cu^2}{\sigma^2}\right),\qquad u>0. P ( w ℓ T Δ z ij > u ) ≤ 2 exp ( − σ 2 c u 2 ) , u > 0.
Fix ε > 0 \varepsilon>0 ε > 0 and D > 0 D>0 D > 0 , and set
u : = M σ n ε , u:=M\sigma n^{\varepsilon}, u := M σ n ε ,
where M > 0 M>0 M > 0 will be chosen later. Since the number of pairs ( i , j ) (i,j) ( i , j ) is of order n 2 n^2 n 2 and p ≍ n α p\asymp n^\alpha p ≍ n α , a union bound over all ( i , j ) (i,j) ( i , j ) and ℓ ∈ [ p ] \ell\in[p] ℓ ∈ [ p ] gives
P ( max 1 ≤ i < j ≤ n max 1 ≤ ℓ ≤ p ∣ w ℓ T ( z i − z j ) ∣ > M σ n ε ) ≤ C n α + 2 exp ( − c M 2 n 2 ε ) . \mathbb{P}\left(\max_{1\le i<j\le n}\max_{1\le\ell\le p}\left|\mathbf{w}_{\ell}^{\mathsf{T}}(\mathbf{z}_i-\mathbf{z}_j)\right|>M\sigma n^\varepsilon\right)\le Cn^{\alpha+2}\exp(-cM^2n^{2\varepsilon}). P ( 1 ≤ i < j ≤ n max 1 ≤ ℓ ≤ p max w ℓ T ( z i − z j ) > M σ n ε ) ≤ C n α + 2 exp ( − c M 2 n 2 ε ) .
Choosing M > 0 M>0 M > 0 large enough yields
P ( max 1 ≤ i < j ≤ n max 1 ≤ ℓ ≤ p ∣ w ℓ T ( z i − z j ) ∣ > M σ n ε ) ≤ n − D \mathbb{P}\left(\max_{1\le i<j\le n}\max_{1\le\ell\le p}\left|\mathbf{w}_{\ell}^{\mathsf{T}}(\mathbf{z}_i-\mathbf{z}_j)\right|>M\sigma n^\varepsilon\right)\le n^{-D} P ( 1 ≤ i < j ≤ n max 1 ≤ ℓ ≤ p max w ℓ T ( z i − z j ) > M σ n ε ) ≤ n − D
for all sufficiently large n n n . Hence
max 1 ≤ i < j ≤ n max 1 ≤ ℓ ≤ p ∣ w ℓ ⊤ ( z i − z j ) ∣ = O ≺ ( σ ) . \max_{1\le i<j\le n}\max_{1\le\ell\le p}\left|w_\ell^\top(z_i-z_j)\right|=O_{\prec}(\sigma). 1 ≤ i < j ≤ n max 1 ≤ ℓ ≤ p max w ℓ ⊤ ( z i − z j ) = O ≺ ( σ ) .
Therefore,
max 1 ≤ i < j ≤ n ∥ P ⊤ ( z i − z j ) ∥ 2 2 = O ≺ ( σ 2 K ) . \max_{1\le i<j\le n}\left\|\mathbf{P}^{\top}(z_i-z_j)\right\|_2^2=O_{\prec}(\sigma^2\mathsf{K}). 1 ≤ i < j ≤ n max P ⊤ ( z i − z j ) 2 2 = O ≺ ( σ 2 K ) .
We next prove the bound for the interaction term. Write
∣ ( P ⊤ Δ s i j ) ⊤ P ⊤ Δ z i j ∣ = ∣ ∑ ℓ ∈ I K ( w ℓ ⊤ Δ s i j ) ( w ℓ ⊤ Δ z i j ) ∣ ≤ max 1 ≤ ℓ ≤ p ∣ w ℓ ⊤ Δ z i j ∣ ∑ ℓ ∈ I K ∣ w ℓ ⊤ Δ s i j ∣ . (62) \begin{aligned}
\left|\left(\mathbf{P}^{\top}\Delta s_{ij}\right)^{\top}\mathbf{P}^{\top}\Delta z_{ij}\right|
=\left|\sum_{\ell\in\mathcal{I}_{\mathsf{K}}}\left(w_\ell^{\top}\Delta s_{ij}\right)\left(w_\ell^{\top}\Delta z_{ij}\right)\right| \\
&\le\max_{1\le\ell\le p}\left|w_\ell^{\top}\Delta z_{ij}\right|\sum_{\ell\in\mathcal{I}_{\mathsf{K}}}\left|w_\ell^{\top}\Delta s_{ij}\right|. \tag*{(62)}
\end{aligned} ( P ⊤ Δ s ij ) ⊤ P ⊤ Δ z ij = ℓ ∈ I K ∑ ( w ℓ ⊤ Δ s ij ) ( w ℓ ⊤ Δ z ij ) ≤ 1 ≤ ℓ ≤ p max w ℓ ⊤ Δ z ij ℓ ∈ I K ∑ w ℓ ⊤ Δ s ij . (62)
By (12) , we have
w ℓ ⊤ Δ s i j = A ℓ ( s i 0 − s j 0 ) . w_\ell^{\top}\Delta s_{ij}=A_\ell(s_i^0-s_j^0). w ℓ ⊤ Δ s ij = A ℓ ( s i 0 − s j 0 ) .
Since { s i 0 } \{s_i^0\} { s i 0 } have compact support, there exists a constant D 0 > 0 D_0>0 D 0 > 0 such that
∥ s i 0 − s j 0 ∥ 2 ≤ D 0 , 1 ≤ i , j ≤ n . \left\|s_i^0-s_j^0\right\|_2\le D_0,\qquad1\le i,j\le n. s i 0 − s j 0 2 ≤ D 0 , 1 ≤ i , j ≤ n .
Hence
∣ w ℓ ⊤ Δ s i j ∣ ≤ ∥ A ℓ ∥ 2 ∥ s i 0 − s j 0 ∥ 2 ≤ D 0 ρ ℓ , \left|w_\ell^{\top}\Delta s_{ij}\right|\le\left\|A_\ell\right\|_2\left\|s_i^0-s_j^0\right\|_2\le D_0\rho_\ell, w ℓ ⊤ Δ s ij ≤ ∥ A ℓ ∥ 2 s i 0 − s j 0 2 ≤ D 0 ρ ℓ ,
where ρ ℓ = ∥ A ℓ ∥ 2 \rho_\ell=\left\|A_\ell\right\|_2 ρ ℓ = ∥ A ℓ ∥ 2 . Therefore,
∑ ℓ ∈ I K ∣ w ℓ ⊤ Δ s i j ∣ ≤ D 0 ∑ ℓ ∈ I K ρ ℓ ≤ D 0 ∑ m = 1 K ρ ( m ) . (63) \sum_{\ell\in\mathcal{I}_{\mathsf{K}}}\left|w_\ell^{\top}\Delta s_{ij}\right|
\le D_0\sum_{\ell\in\mathcal{I}_{\mathsf{K}}}\rho_\ell
\le D_0\sum_{m=1}^{\mathsf{K}}\rho_{(m)}. \tag*{(63)} ℓ ∈ I K ∑ w ℓ ⊤ Δ s ij ≤ D 0 ℓ ∈ I K ∑ ρ ℓ ≤ D 0 m = 1 ∑ K ρ ( m ) . (63)
By Lemma C.1 , ρ ( m ) ≲ m − 1 / q \rho_{(m)}\lesssim m^{-1/q} ρ ( m ) ≲ m − 1/ q , so
∑ m = 1 K ρ ( m ) ≲ { 1 , 0 < q < 1 , 1 + log K , q = 1 , K 1 − 1 / q , 1 < q < 2. (64) \sum_{m=1}^{\mathsf{K}}\rho_{(m)}
\lesssim
\begin{cases}
1, & 0<q<1,\\
1+\log\mathsf{K}, & q=1,\\
\mathsf{K}^{1-1/q}, & 1<q<2.
\end{cases} \tag*{(64)} m = 1 ∑ K ρ ( m ) ≲ ⎩ ⎨ ⎧ 1 , 1 + log K , K 1 − 1/ q , 0 < q < 1 , q = 1 , 1 < q < 2. (64)
Since K ≤ p \mathsf{K}\le p K ≤ p and p ≍ n α p\asymp n^\alpha p ≍ n α , the logarithmic factor in the case q = 1 q=1 q = 1 is absorbed by ≺ \prec ≺ -notation. Thus (C.32) implies
∑ m = 1 K ρ ( m ) = O ≺ ( K ( 1 − 1 / q ) + ) . \sum_{m=1}^{\mathsf{K}}\rho_{(m)}=O_{\prec}\left(\mathsf{K}^{(1-1/q)_+}\right). m = 1 ∑ K ρ ( m ) = O ≺ ( K ( 1 − 1/ q ) + ) .
Combining this with (C.30, (C.31), and the first part of the proof, we conclude that
max 1 ≤ i < j ≤ n ∣ ( P ( s i − s j ) ) ⊤ P ⊤ ( z i − z j ) ∣ = O ≺ ( σ K ( 1 − 1 / q ) + ) , \max_{1\le i<j\le n}\left|\left(\mathbf{P}(s_i-s_j)\right)^{\top}\mathbf{P}^{\top}(z_i-z_j)\right|
=O_{\prec}\left(\sigma\mathsf{K}^{(1-1/q)_+}\right), 1 ≤ i < j ≤ n max ( P ( s i − s j ) ) ⊤ P ⊤ ( z i − z j ) = O ≺ ( σ K ( 1 − 1/ q ) + ) ,
which completes the proof.
We are now ready to prove Theorem 3.6 . The argument combines the clean projection bias from Lemma C.6 with the projected-noise bounds in Lemma C.7 .
Proof of Theorem 3.6. Let t n = σ 2 / Θ t_n = \sigma^2/\Theta t n = σ 2 /Θ , and recall c ∗ c_\ast c ∗ from (C.22). Fix 0 < δ < τ / [ 2 ( 2 + τ ) ] 0 < \delta< \tau/[2(2+\tau)] 0 < δ < τ / [ 2 ( 2 + τ )] and work on the energy-concentration event in Lemma C.3 . Recall the signal variances d j = A j ⋅ Σ A j T d_j = A_j \cdot\Sigma A_j^{\mathsf{T}} d j = A j ⋅ Σ A j T from the proof of Proposition 3.4 . For each selected coordinate, we have E j ≥ ( 1 + τ ) σ ^ 2 E_j \ge(1+\tau)\hat{\sigma}^2 E j ≥ ( 1 + τ ) σ ^ 2 and E j ≤ ( 1 + δ ) ( σ 2 + d j ) E_j \le(1+\delta)(\sigma^2+d_j) E j ≤ ( 1 + δ ) ( σ 2 + d j ) . Since the population tail average is at least σ 2 \sigma^2 σ 2 , we also have σ ^ 2 ≥ ( 1 − δ ) σ 2 \hat{\sigma}^2 \ge(1-\delta)\sigma^2 σ ^ 2 ≥ ( 1 − δ ) σ 2 . Combining these inequalities, we obtain
d j ≥ a − σ 2 , a − = ( 1 + τ ) ( 1 − δ ) 1 + δ − 1 > 0. d_j \ge a_-\sigma^2,\qquad a_- = \frac{(1+\tau)(1-\delta)}{1+\delta}-1 > 0. d j ≥ a − σ 2 , a − = 1 + δ ( 1 + τ ) ( 1 − δ ) − 1 > 0.
By the upper bound d ( j ) ≤ C Θ j − 2 / q d_{(j)} \le C\Theta j^{-2/q} d ( j ) ≤ C Θ j − 2/ q in (C.14), we then have K ≲ t n − q / 2 K \lesssim t_n^{-q/2} K ≲ t n − q /2 whenever t n > 0 t_n > 0 t n > 0 . We first consider t n > c ∗ t_n > c_\ast t n > c ∗ . Set T = max { 1 , 2 / a − } T=\max\{1,2/a_-\} T = max { 1 , 2/ a − } . If c ∗ < t n < T c_\ast< t_n < T c ∗ < t n < T , the preceding bound gives K ≲ 1 K \lesssim1 K ≲ 1 , and we also have σ 2 < T Θ \sigma^2 < T\Theta σ 2 < T Θ . Using the bounded signal support and Lemma C.7 , we therefore obtain a pairwise-distance error of order O ≺ ( 1 ) O_{\prec}(1) O ≺ ( 1 ) .
If t n ≥ T t_n \ge T t n ≥ T , we have a − σ 2 ≥ 2 Θ a_-\sigma^2 \ge2\Theta a − σ 2 ≥ 2Θ , whereas d j ≤ ∑ ℓ d ℓ = Θ d_j \le\sum_\ell d_\ell= \Theta d j ≤ ∑ ℓ d ℓ = Θ . Thus, no coordinate can satisfy the selection inequality above, and K = 0 K=0 K = 0 on the concentration event. The projected distances are then zero and the clean distances are bounded, so we again obtain an error of order O ≺ ( 1 ) O_{\prec}(1) O ≺ ( 1 ) . In both cases, for all sufficiently large n n n , we are in the first SNR regime and have ψ n , b i a s = t n 1 − q / 2 ≥ c ∗ 1 − q / 2 > 0 \psi_{n,\mathrm{bias}}=t_n^{1-q/2}\ge c_\ast^{1-q/2}>0 ψ n , bias = t n 1 − q /2 ≥ c ∗ 1 − q /2 > 0 . We therefore obtain the claimed rate for t n > c ∗ t_n>c_\ast t n > c ∗ . By the standardized noise convention in Remark C.2 , the concentration event used here holds with high probability uniformly in σ \sigma σ . For any fixed D > 0 D>0 D > 0 , its failure probability is at most n − D n^{-D} n − D for all sufficiently large n n n .
It remains to consider t n ≤ c ∗ t_n\le c_\ast t n ≤ c ∗ . We work on the concentration event associated with (C.22) and use its counting bound for the selected dimension in the argument below.
For this remaining case, we write, for 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n ,
Δ x i j : = x i − x j , Δ s i j : = s i − s j , Δ z i j : = z i − z j . \Delta x_{ij}:=x_i-x_j,\qquad\Delta s_{ij}:=s_i-s_j,\qquad\Delta z_{ij}:=z_i-z_j. Δ x ij := x i − x j , Δ s ij := s i − s j , Δ z ij := z i − z j .
Since y i = P T ( x i − x ˉ ) y_i=P^{\mathsf{T}}(x_i-\bar{x}) y i = P T ( x i − x ˉ ) , the training mean cancels and we have
y i − y j = P T Δ x i j = P T Δ s i j + P T Δ z i j . y_i-y_j=P^{\mathsf{T}}\Delta x_{ij}=P^{\mathsf{T}}\Delta s_{ij}+P^{\mathsf{T}}\Delta z_{ij}. y i − y j = P T Δ x ij = P T Δ s ij + P T Δ z ij .
Therefore,
∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 = ( ∥ P T Δ s i j ∥ 2 2 − ∥ Δ s i j ∥ 2 2 ) + ∥ P T Δ z i j ∥ 2 2 + 2 ( P T Δ s i j ) T P T Δ z i j . (65) \lVert y_i-y_j\rVert_2^2-\lVert s_i-s_j\rVert_2^2
=\left(\lVert P^{\mathsf{T}}\Delta s_{ij}\rVert_2^2-\lVert\Delta s_{ij}\rVert_2^2\right)+\lVert P^{\mathsf{T}}\Delta z_{ij}\rVert_2^2+2(P^{\mathsf{T}}\Delta s_{ij})^{\mathsf{T}}P^{\mathsf{T}}\Delta z_{ij}. \tag*{(65)} ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 = ( ∥ P T Δ s ij ∥ 2 2 − ∥ Δ s ij ∥ 2 2 ) + ∥ P T Δ z ij ∥ 2 2 + 2 ( P T Δ s ij ) T P T Δ z ij . (65)
We bound the three terms on the right-hand side separately. The first term is the projection bias, while the latter two terms represent the stochastic projected-noise contribution. Taking absolute values and maxima over 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n , we obtain
max 1 ≤ i < j ≤ n ∣ ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ ≤ max 1 ≤ i < j ≤ n ∣ ∥ P T ( s i − s j ) ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ + max 1 ≤ i < j ≤ n ∥ P T ( z i − z j ) ∥ 2 2 + 2 max 1 ≤ i < j ≤ n ∣ ( P T ( s i − s j ) ) T P T ( z i − z j ) ∣ . (66) \begin{aligned}
\max_{1\le i<j\le n}\left|\lVert y_i-y_j\rVert_2^2-\lVert s_i-s_j\rVert_2^2\right|
\le
\max_{1\le i<j\le n}\left|\lVert P^{\mathsf{T}}(s_i-s_j)\rVert_2^2-\lVert s_i-s_j\rVert_2^2\right|
+\max_{1\le i<j\le n}\lVert P^{\mathsf{T}}(z_i-z_j)\rVert_2^2 \\
&+2\max_{1\leq i<j\leq n}\left|\left(\mathrm{P}^{\mathsf T}(s_i-s_j)\right)^{\mathsf T}\mathrm{P}^{\mathsf T}(z_i-z_j)\right|. \tag*{(66)}
\end{aligned} 1 ≤ i < j ≤ n max ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 ≤ 1 ≤ i < j ≤ n max ∥ P T ( s i − s j ) ∥ 2 2 − ∥ s i − s j ∥ 2 2 + 1 ≤ i < j ≤ n max ∥ P T ( z i − z j ) ∥ 2 2 + 2 1 ≤ i < j ≤ n max ( P T ( s i − s j ) ) T P T ( z i − z j ) . (66)
We first control the projection bias term. By Lemma C.6 ,
max 1 ≤ i < j ≤ n ∣ ∥ P T ( s i − s j ) ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ = O ≺ ( ψ n , b i a s ) . (67) \max_{1\leq i<j\leq n}\left|\left\|\mathrm{P}^{\mathsf T}(s_i-s_j)\right\|_2^2-\left\|s_i-s_j\right\|_2^2\right|=O_{\prec}(\psi_{n,\mathrm{bias}}). \tag*{(67)} 1 ≤ i < j ≤ n max P T ( s i − s j ) 2 2 − ∥ s i − s j ∥ 2 2 = O ≺ ( ψ n , bias ) . (67)
We next control the two projected-noise terms. By Lemma C.7 ,
max 1 ≤ i < j ≤ n ∥ P T ( z i − z j ) ∥ 2 2 = O ≺ ( σ 2 K ) , (68) \max_{1\leq i<j\leq n}\left\|\mathrm{P}^{\mathsf T}(z_i-z_j)\right\|_2^2=O_{\prec}(\sigma^2K), \tag*{(68)} 1 ≤ i < j ≤ n max P T ( z i − z j ) 2 2 = O ≺ ( σ 2 K ) , (68)
and
max 1 ≤ i < j ≤ n ∣ ( P T ( s i − s j ) ) T P T ( z i − z j ) ∣ = O ≺ ( σ K ( 1 − 1 / q ) + ) . (69) \max_{1\leq i<j\leq n}\left|\left(\mathrm{P}^{\mathsf T}(s_i-s_j)\right)^{\mathsf T}\mathrm{P}^{\mathsf T}(z_i-z_j)\right|=O_{\prec}\left(\sigma K^{(1-1/q)_+}\right). \tag*{(69)} 1 ≤ i < j ≤ n max ( P T ( s i − s j ) ) T P T ( z i − z j ) = O ≺ ( σ K ( 1 − 1/ q ) + ) . (69)
Hence
max 1 ≤ i < j ≤ n ∣ ∥ P T Δ z i j ∥ 2 2 + 2 ( P T Δ s i j ) T P T Δ z i j ∣ = O ≺ ( σ 2 K + σ K ( 1 − 1 / q ) + ) . (70) \max_{1\leq i<j\leq n}\left|\left\|\mathrm{P}^{\mathsf T}\Delta z_{ij}\right\|_2^2+2\left(\mathrm{P}^{\mathsf T}\Delta s_{ij}\right)^{\mathsf T}\mathrm{P}^{\mathsf T}\Delta z_{ij}\right|=O_{\prec}\left(\sigma^2K+\sigma K^{(1-1/q)_+}\right). \tag*{(70)} 1 ≤ i < j ≤ n max P T Δ z ij 2 2 + 2 ( P T Δ s ij ) T P T Δ z ij = O ≺ ( σ 2 K + σ K ( 1 − 1/ q ) + ) . (70)
By the counting bound (C.22), the selected projection dimension K K K admits the asymptotic characterization stated in (20) . Substituting that characterization into (C.38) yields the same order as the rate ψ n , n o i s e \psi_{n,\mathrm{noise}} ψ n , noise defined in (23) . Thus
max 1 ≤ i < j ≤ n ∣ ∥ P T Δ z i j ∥ 2 2 + 2 ( P T Δ s i j ) T P T Δ z i j ∣ = O ≺ ( ψ n , n o i s e ) . (71) \max_{1\leq i<j\leq n}\left|\left\|\mathrm{P}^{\mathsf T}\Delta z_{ij}\right\|_2^2+2\left(\mathrm{P}^{\mathsf T}\Delta s_{ij}\right)^{\mathsf T}\mathrm{P}^{\mathsf T}\Delta z_{ij}\right|=O_{\prec}(\psi_{n,\mathrm{noise}}). \tag*{(71)} 1 ≤ i < j ≤ n max P T Δ z ij 2 2 + 2 ( P T Δ s ij ) T P T Δ z ij = O ≺ ( ψ n , noise ) . (71)
Finally, combining (C.34) with the projection-bias bound (C.35) and the noise bound (C.39), we obtain
max 1 ≤ i < j ≤ n ∣ ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 ∣ = O ≺ ( ψ n , b i a s + ψ n , n o i s e ) = O ≺ ( ψ n ) , \max_{1\leq i<j\leq n}\left|\left\|y_i-y_j\right\|_2^2-\left\|s_i-s_j\right\|_2^2\right|=O_{\prec}(\psi_{n,\mathrm{bias}}+\psi_{n,\mathrm{noise}})=O_{\prec}(\psi_n), 1 ≤ i < j ≤ n max ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 = O ≺ ( ψ n , bias + ψ n , noise ) = O ≺ ( ψ n ) ,
which proves Theorem 3.6 . □
Proofs for Spectral Convergence
In this subsection, we bound the error of the empirical bandwidth h n h_n h n in (11) relative to the population bandwidth h h h in (27) , and then prove Theorem 3.8 .
We define the clean empirical distribution function
G n 0 ( t ) : = 2 n ( n − 1 ) ∑ 1 ≤ i < j ≤ n 1 { ∥ s i − s j ∥ 2 2 ≤ t } , t ≥ 0 , G_n^0(t):=\frac{2}{n(n-1)}\sum_{1\leq i<j\leq n}\mathbf{1}_{\{\left\|s_i-s_j\right\|_2^2\leq t\}},\qquad t\geq0, G n 0 ( t ) := n ( n − 1 ) 2 1 ≤ i < j ≤ n ∑ 1 { ∥ s i − s j ∥ 2 2 ≤ t } , t ≥ 0 ,
and let
h : = inf { t ≥ 0 : G n 0 ( t ) ≥ ω } . h:=\inf\{t\geq0:G_n^0(t)\geq\omega\}. h := inf { t ≥ 0 : G n 0 ( t ) ≥ ω } .
All three bandwidths are ω \omega ω -quantiles of squared distances, computed from the projected observations for h n h_n h n , the clean sample for h h h , and the clean population law for h h h . Recall (11) and (26) . The following proposition gives the bandwidth error bound.
Proposition C.8 (Bandwidth consistency). Suppose Assumptions 3.1, 3.2, and 3.3 hold. For any prespecified ω ∈ ( 0 , 1 ) \omega\in(0,1) ω ∈ ( 0 , 1 ) satisfying the local density condition in Theorem 3.8 ,
∣ h n h − 1 ∣ = O ( ψ n + 1 n ) . \left|\frac{h_n}{h}-1\right| = \mathrm{O}\left(\psi_n+\frac{1}{\sqrt{n}}\right). h h n − 1 = O ( ψ n + n 1 ) .
Remark C.9. Proposition C.8 separates the projection error ∣ h n − h ∣ = O ≺ ( ψ n ) \lvert h_n-h\rvert=\mathrm{O}_{\prec}(\psi_n) ∣ h n − h ∣ = O ≺ ( ψ n ) from the clean quantile error ∣ h − h ∣ = O ≺ ( n − 1 / 2 ) \lvert h-h\rvert=\mathrm{O}_{\prec}(n^{-1/2}) ∣ h − h ∣ = O ≺ ( n − 1/2 ) . Their sum gives the error relative to the population bandwidth, which is needed in the spectral comparison below.
Remark C.10. The local density condition in Theorem 3.8 is a standard sufficient condition for quantile stability; see, for example, [58 , 67 ] . It ensures that G G G crosses the level ω \omega ω at a rate bounded away from zero near h h h , as shown in (C.43) below. This local property is the regularity needed in the bandwidth proof. Algorithm S.1 provides a practical way to select this quantile parameter.
Proof. We first compare h n h_n h n with the clean empirical bandwidth h h h . Let
Δ n : = max 1 ≤ i < j ≤ n { ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 } . \Delta_n := \max_{1\leq i<j\leq n}\left\{\lVert y_i-y_j\rVert_2^2-\lVert s_i-s_j\rVert_2^2\right\}. Δ n := 1 ≤ i < j ≤ n max { ∥ y i − y j ∥ 2 2 − ∥ s i − s j ∥ 2 2 } .
By Theorem 3.6 ,
Δ n = O ≺ ( ψ n ) . (72) \Delta_n=\mathrm{O}_{\prec}(\psi_n). \tag*{(72)} Δ n = O ≺ ( ψ n ) . (72)
By definition of Δ n \Delta_n Δ n , for every t ≥ 0 t\geq0 t ≥ 0 ,
G n 0 ( t − Δ n ) ≤ G n ( t ) ≤ G n 0 ( t + Δ n ) , G_n^0(t-\Delta_n)\leq G_n(t)\leq G_n^0(t+\Delta_n), G n 0 ( t − Δ n ) ≤ G n ( t ) ≤ G n 0 ( t + Δ n ) ,
where we use the convention G n 0 ( s ) = 0 G_n^0(s)=0 G n 0 ( s ) = 0 for s < 0 s<0 s < 0 . Recall that
h = inf { t ≥ 0 : G n 0 ( t ) ≥ ω } , h n = inf { t ≥ 0 : G n ( t ) ≥ ω } . h=\inf\{t\geq0:G_n^0(t)\geq\omega\},\qquad h_n=\inf\{t\geq0:G_n(t)\geq\omega\}. h = inf { t ≥ 0 : G n 0 ( t ) ≥ ω } , h n = inf { t ≥ 0 : G n ( t ) ≥ ω } .
Hence
h − Δ n ≤ h n ≤ h + Δ n . h-\Delta_n\leq h_n\leq h+\Delta_n. h − Δ n ≤ h n ≤ h + Δ n .
Combining this with (C.40), we obtain
∣ h n − h ∣ ≤ Δ n = O ≺ ( ψ n ) . (73) \lvert h_n-h\rvert\leq\Delta_n=\mathrm{O}_{\prec}(\psi_n). \tag*{(73)} ∣ h n − h ∣ ≤ Δ n = O ≺ ( ψ n ) . (73)
We next compare h h h with the population bandwidth h h h . Recall 3.1. Since R R R is orthogonal, we have
∥ s i − s j ∥ 2 2 = ∥ s i 0 − s j 0 ∥ 2 2 . \lVert s_i-s_j\rVert_2^2=\lVert s_i^0-s_j^0\rVert_2^2. ∥ s i − s j ∥ 2 2 = ∥ s i 0 − s j 0 ∥ 2 2 .
Hence
G n 0 ( t ) = 2 n ( n − 1 ) ∑ 1 ≤ i < j ≤ n 1 { ∥ s i 0 − s j 0 ∥ 2 2 ≤ t } , G_n^0(t)=\frac{2}{n(n-1)}\sum_{1\leq i<j\leq n}\mathbf{1}_{\{\lVert s_i^0-s_j^0\rVert_2^2\leq t\}}, G n 0 ( t ) = n ( n − 1 ) 2 1 ≤ i < j ≤ n ∑ 1 {∥ s i 0 − s j 0 ∥ 2 2 ≤ t } ,
so G n 0 ( t ) G_n^0(t) G n 0 ( t ) is a function of the independent latent variables s 1 0 , … , s n 0 s_1^0,\ldots,s_n^0 s 1 0 , … , s n 0 . Moreover, since s 1 0 , s 2 0 ∼ i . i . d . μ s_1^0,s_2^0\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mu s 1 0 , s 2 0 ∼ i.i.d. μ ,
E G n 0 ( t ) = P ( ∥ s 1 0 − s 2 0 ∥ 2 2 ≤ t ) = G ( t ) . (74) \mathbb{E}G_n^0(t)=\mathbb{P}\left(\lVert s_1^0-s_2^0\rVert_2^2\leq t\right)=G(t). \tag*{(74)} E G n 0 ( t ) = P ( ∥ s 1 0 − s 2 0 ∥ 2 2 ≤ t ) = G ( t ) . (74)
Since μ ≪ V 0 \mu\ll V_0 μ ≪ V 0 and the Riemannian volume measure V 0 V_0 V 0 is nonatomic,
G ( 0 ) = P ( U = V ) = 0. G(0)=\mathbb{P}(U=V)=0. G ( 0 ) = P ( U = V ) = 0.
Moreover, since M 0 \mathcal{M}^0 M 0 is compact, there exists a constant C 0 > 0 C_0>0 C 0 > 0 such that D < C 0 D<C_0 D < C 0 . Thus G ( C 0 ) = 1 G(C_0)=1 G ( C 0 ) = 1 . Since ω ∈ ( 0 , 1 ) \omega\in(0,1) ω ∈ ( 0 , 1 ) and G G G is right-continuous at 0 0 0 , it follows from the definition of h h h that
By the density condition in Theorem 3.8 , G G G is continuous near h h h . The definition of its quantile gives G ( h ) ≥ ω G(h)\geq\omega G ( h ) ≥ ω . If the inequality were strict, continuity would give G ( h − s ) > ω G(h-s)>\omega G ( h − s ) > ω for some s > 0 s>0 s > 0 , contradicting the definition of h h h . Therefore G ( h ) = ω G(h)=\omega G ( h ) = ω . Since ν \nu ν is continuous at h h h and ν ( h ) > 0 \nu(h)>0 ν ( h ) > 0 , we can choose constants 0 < δ 0 < h / 2 0<\delta_0<h/2 0 < δ 0 < h /2 and c 0 > 0 c_0>0 c 0 > 0 such that G G G has density ν \nu ν on [ h − δ 0 , h + δ 0 ] [h-\delta_0,h+\delta_0] [ h − δ 0 , h + δ 0 ] and ν ( t ) ≥ c 0 \nu(t)\geq c_0 ν ( t ) ≥ c 0 throughout this interval. Integration then gives
G ( h + s ) − ω = ∫ h h + s ν ( t ) d t ≥ c 0 s , G(h+s)-\omega=\int_h^{h+s}\nu(t)\,\mathrm{d}t\geq c_0s, G ( h + s ) − ω = ∫ h h + s ν ( t ) d t ≥ c 0 s ,
ω − G ( h − s ) = ∫ h − s h ν ( t ) d t ≥ c 0 s . \omega-G(h-s)=\int_{h-s}^h\nu(t)\,\mathrm{d}t\geq c_0s. ω − G ( h − s ) = ∫ h − s h ν ( t ) d t ≥ c 0 s .
Thus
G ( h + s ) ≥ ω + c 0 s , G ( h − s ) ≤ ω − c 0 s , 0 < s ≤ δ 0 . (75) G(h+s)\geq\omega+c_0s,\qquad G(h-s)\leq\omega-c_0s,\qquad0<s\leq\delta_0. \tag*{(75)} G ( h + s ) ≥ ω + c 0 s , G ( h − s ) ≤ ω − c 0 s , 0 < s ≤ δ 0 . (75)
We next establish concentration for the clean empirical distribution function. Fix t ≥ 0 t\geq0 t ≥ 0 and define
f t ( s 1 0 , … , s n 0 ) : = G n 0 ( t ) = 2 n ( n − 1 ) ∑ 1 ≤ i < j ≤ n 1 { ∥ s i 0 − s j 0 ∥ 2 2 ≤ t } . f_t(s_1^0,\ldots,s_n^0):=G_n^0(t)=\frac{2}{n(n-1)}\sum_{1\leq i<j\leq n}\mathbf{1}\left\{\lVert s_i^0-s_j^0\rVert_2^2\leq t\right\}. f t ( s 1 0 , … , s n 0 ) := G n 0 ( t ) = n ( n − 1 ) 2 1 ≤ i < j ≤ n ∑ 1 { ∥ s i 0 − s j 0 ∥ 2 2 ≤ t } .
If we replace s i 0 s_i^0 s i 0 by another value s i 0 ′ s_i^{0\prime} s i 0′ , then at most ( n − 1 ) (n-1) ( n − 1 ) summands in the above sum can change, and each changes by at most 1 1 1 . Hence
sup s 1 0 , … , s n 0 , s i 0 ′ ∣ f t ( s 1 0 , … , s i 0 , … , s n 0 ) − f t ( s 1 0 , … , s i 0 ′ , … , s n 0 ) ∣ ≤ 2 n . \sup_{s_1^0,\ldots,s_n^0,s_i^{0\prime}}\left|f_t(s_1^0,\ldots,s_i^0,\ldots,s_n^0)-f_t(s_1^0,\ldots,s_i^{0\prime},\ldots,s_n^0)\right|\leq\frac{2}{n}. s 1 0 , … , s n 0 , s i 0′ sup f t ( s 1 0 , … , s i 0 , … , s n 0 ) − f t ( s 1 0 , … , s i 0′ , … , s n 0 ) ≤ n 2 .
By Lemma E.2 , for any u > 0 u>0 u > 0 ,
P ( ∣ G n 0 ( t ) − G ( t ) ∣ > u ) ≤ 2 exp ( − 2 u 2 n ( 2 / n ) 2 ) = 2 exp ( − n u 2 2 ) . (76) \mathbb{P}\left(\left|G_n^0(t)-G(t)\right|>u\right)\leq2\exp\left(-\frac{2u^2}{n(2/n)^2}\right)=2\exp\left(-\frac{nu^2}{2}\right). \tag*{(76)} P ( G n 0 ( t ) − G ( t ) > u ) ≤ 2 exp ( − n ( 2/ n ) 2 2 u 2 ) = 2 exp ( − 2 n u 2 ) . (76)
Let ε ∈ ( 0 , 1 / 2 ) \varepsilon\in(0,1/2) ε ∈ ( 0 , 1/2 ) and D > 0 D>0 D > 0 be arbitrary, and define
r n : = n ε n . r_n:=\frac{n^\varepsilon}{\sqrt{n}}. r n := n n ε .
Since r n = o ( 1 ) r_n=o(1) r n = o ( 1 ) , for sufficiently large n n n we have
r n ≤ min { δ 0 , h / 2 } . r_n\leq\min\{\delta_0,h/2\}. r n ≤ min { δ 0 , h /2 } .
Define
t n + : = h + r n , t n − : = h − r n . t_n^{+} := h + r_n,\qquad t_n^{-} := h - r_n. t n + := h + r n , t n − := h − r n .
Since t n + t_n^{+} t n + and t n − t_n^{-} t n − are deterministic for each fixed n n n , (C.44) and (C.43) give
P ( G n 0 ( t n + ) < ω ) ≤ P ( G n 0 ( t n + ) − G ( t n + ) < − c 0 r n ) ≤ 2 exp ( − n c 0 2 r n 2 2 ) . (77) \mathbb{P}\left(G_n^0(t_n^{+}) < \omega\right) \le\mathbb{P}\left(G_n^0(t_n^{+}) - G(t_n^{+}) < -c_0r_n\right) \le2\exp\left(-\frac{nc_0^2r_n^2}{2}\right). \tag*{(77)} P ( G n 0 ( t n + ) < ω ) ≤ P ( G n 0 ( t n + ) − G ( t n + ) < − c 0 r n ) ≤ 2 exp ( − 2 n c 0 2 r n 2 ) . (77)
P ( G n 0 ( t n − ) ≥ ω ) ≤ P ( G n 0 ( t n − ) − G ( t n − ) ≥ c 0 r n ) ≤ 2 exp ( − n c 0 2 r n 2 2 ) . (78) \mathbb{P}\left(G_n^0(t_n^{-}) \ge\omega\right) \le\mathbb{P}\left(G_n^0(t_n^{-}) - G(t_n^{-}) \ge c_0r_n\right) \le2\exp\left(-\frac{nc_0^2r_n^2}{2}\right). \tag*{(78)} P ( G n 0 ( t n − ) ≥ ω ) ≤ P ( G n 0 ( t n − ) − G ( t n − ) ≥ c 0 r n ) ≤ 2 exp ( − 2 n c 0 2 r n 2 ) . (78)
Since n r n 2 = n 2 ε nr_n^2 = n^{2\varepsilon} n r n 2 = n 2 ε , for sufficiently large n n n , we have that
2 exp ( − n c 0 2 r n 2 2 ) ≤ n − D 2\exp\left(-\frac{nc_0^2r_n^2}{2}\right) \le n^{-D} 2 exp ( − 2 n c 0 2 r n 2 ) ≤ n − D
Hence, by a union bound applied to (C.45) and (C.46),
P ( G n 0 ( t n + ) ≥ ω , G n 0 ( t n − ) < ω ) ≥ 1 − 2 n − D . \mathbb{P}\left(G_n^0(t_n^{+}) \ge\omega,\ G_n^0(t_n^{-}) < \omega\right) \ge1 - 2n^{-D}. P ( G n 0 ( t n + ) ≥ ω , G n 0 ( t n − ) < ω ) ≥ 1 − 2 n − D .
On this event, by the definition of h h h ,
h − r n ≤ h ≤ h + r n , h-r_n \le h \le h+r_n, h − r n ≤ h ≤ h + r n ,
and therefore
∣ h − h ∣ ≤ r n . |h-h| \le r_n. ∣ h − h ∣ ≤ r n .
Since ε > 0 \varepsilon> 0 ε > 0 and D > 0 D > 0 D > 0 were arbitrary, this proves
∣ h − h ∣ = O ≺ ( 1 n ) . (79) |h-h| = O_{\prec}\left(\frac{1}{\sqrt{n}}\right). \tag*{(79)} ∣ h − h ∣ = O ≺ ( n 1 ) . (79)
Combining (C.41) and (C.47), we obtain
∣ h n − h ∣ ≤ ∣ h n − h ∣ + ∣ h − h ∣ = O ≺ ( ψ n + 1 n ) . (80) |h_n-h| \le|h_n-h|+|h-h| = O_{\prec}\left(\psi_n+\frac{1}{\sqrt{n}}\right). \tag*{(80)} ∣ h n − h ∣ ≤ ∣ h n − h ∣ + ∣ h − h ∣ = O ≺ ( ψ n + n 1 ) . (80)
Since h h h is a positive constant, (C.48) yields
∣ h n h − 1 ∣ = O ≺ ( ψ n + 1 n ) , \left|\frac{h_n}{h}-1\right| = O_{\prec}\left(\psi_n+\frac{1}{\sqrt{n}}\right), h h n − 1 = O ≺ ( ψ n + n 1 ) ,
which completes the proof.
We now use Proposition C.8 to prove the spectral convergence result for a general kernel function f f f .
Assumption C.11 (Kernel regularity). The kernel function f : [ 0 , ∞ ) → R f : [0,\infty) \to\mathbb{R} f : [ 0 , ∞ ) → R is bounded, that is,
sup x ≥ 0 ∣ f ( x ) ∣ ≤ B f \sup_{x\geq0} |f(x)| \leq B_f x ≥ 0 sup ∣ f ( x ) ∣ ≤ B f for some constant B f > 0 B_f > 0 B f > 0 . Moreover, there exist two measurable functions ζ : [ 0 , ∞ ) → R \zeta: [0,\infty) \to\mathbb{R} ζ : [ 0 , ∞ ) → R , and τ : [ 0 , ∞ ) × [ 0 , ∞ ) → ( 0 , 1 ] \tau: [0,\infty) \times[0,\infty) \to(0,1] τ : [ 0 , ∞ ) × [ 0 , ∞ ) → ( 0 , 1 ] , such that for all s , t ≥ 0 s,t \geq0 s , t ≥ 0 ,
∣ f ( t ) − f ( s ) ∣ ≤ L f ( t ζ ( t ) + s ζ ( s ) ) ∣ t − s ∣ τ ( s , t ) , (81) |f(t)-f(s)| \leq L_f\left(t^{\zeta(t)}+s^{\zeta(s)}\right)|t-s|^{\tau(s,t)}, \tag*{(81)} ∣ f ( t ) − f ( s ) ∣ ≤ L f ( t ζ ( t ) + s ζ ( s ) ) ∣ t − s ∣ τ ( s , t ) , (81) where L f > 0 L_f > 0 L f > 0 is a constant, ζ ( x ) ≥ 0 \zeta(x) \geq0 ζ ( x ) ≥ 0 for 0 ≤ x ≤ 1 0 \leq x \leq1 0 ≤ x ≤ 1 , and ζ ( x ) ≤ 0 \zeta(x) \leq0 ζ ( x ) ≤ 0 for x > 1 x>1 x > 1 . Finally, for every h > 0 h>0 h > 0 and every dimension m ∈ N m\in\mathbb{N} m ∈ N , the kernel
Φ h ( u , v ) : = f ( ∥ u − v ∥ 2 h 1 / 2 ) , u , v ∈ R m , \Phi_h(u,v) := f\left(\frac{\lVert u-v\rVert_2}{h^{1/2}}\right), \qquad u,v\in\mathbb{R}^{m}, Φ h ( u , v ) := f ( h 1/2 ∥ u − v ∥ 2 ) , u , v ∈ R m , is positive semidefinite. Assume also that τ 0 = inf s , t ≥ 0 τ ( s , t ) > 0 \tau_0=\inf_{s,t\geq0}\tau(s,t)>0 τ 0 = inf s , t ≥ 0 τ ( s , t ) > 0 , and interpret 0 0 = 1 0^0=1 0 0 = 1 when needed in (C.49). All regularity constants are uniform in n n n .
Remark C.12. For f ( x ) = exp ( − x 2 ) f(x)=\exp(-x^2) f ( x ) = exp ( − x 2 ) used in (7) , one may take τ ( s , t ) = 1 \tau(s,t)=1 τ ( s , t ) = 1 , ζ ( x ) = 1 \zeta(x)=1 ζ ( x ) = 1 for 0 ≤ x ≤ 1 0\leq x\leq1 0 ≤ x ≤ 1 , ζ ( x ) = 0 \zeta(x)=0 ζ ( x ) = 0 for x > 1 x>1 x > 1 , and L f = 2 L_f=2 L f = 2 .
Under Assumption C.11, we define the corresponding kernel matrix, empirical eigenfunctions, and population integral operator. Recall (7) , (31) , and (28) . Using the same notation, define K n = ( K ( i , j ) ) \mathbf{K}_n=(K(i,j)) K n = ( K ( i , j )) by
K ( i , j ) = f ( ∥ y i − y j ∥ 2 h n 1 / 2 ) , 1 ≤ i , j ≤ n , K(i,j)=f\left(\frac{\lVert\mathbf{y}_i-\mathbf{y}_j\rVert_2}{h_n^{1/2}}\right), \qquad1\leq i,j\leq n, K ( i , j ) = f ( h n 1/2 ∥ y i − y j ∥ 2 ) , 1 ≤ i , j ≤ n ,
with eigenvalues λ 1 ≥ ⋯ ≥ λ n \lambda_1\geq\cdots\geq\lambda_n λ 1 ≥ ⋯ ≥ λ n and eigenvectors u 1 , … , u n \mathbf{u}_1,\ldots,\mathbf{u}_n u 1 , … , u n of the normalized matrix n − 1 K n n^{-1}\mathbf{K}_n n − 1 K n . Denote the empirical eigenfunctions for λ i > 0 \lambda_i>0 λ i > 0 by
ϕ ^ i ( n ) ( x ) : = 1 λ i n ∑ j = 1 n f ( ∥ P T ( x − x j ) ∥ 2 h n 1 / 2 ) u i j , x ∈ R p , \widehat{\phi}^{(n)}_i(\mathbf{x}) := \frac{1}{\lambda_i\sqrt{n}}\sum_{j=1}^{n}f\left(\frac{\lVert\mathbf{P}^{\mathsf T}(\mathbf{x}-\mathbf{x}_j)\rVert_2}{h_n^{1/2}}\right)u_{ij}, \qquad\mathbf{x}\in\mathbb{R}^{p}, ϕ i ( n ) ( x ) := λ i n 1 j = 1 ∑ n f ( h n 1/2 ∥ P T ( x − x j ) ∥ 2 ) u ij , x ∈ R p ,
and the population integral operator K ~ : L 2 ( R p , μ s ) → L 2 ( R p , μ s ) \widetilde{\mathcal{K}}:L^2(\mathbb{R}^{p},\mu_s)\to L^2(\mathbb{R}^{p},\mu_s) K : L 2 ( R p , μ s ) → L 2 ( R p , μ s ) by
( K ~ g ) ( x ) : = ∫ f ( ∥ x − y ∥ 2 h 1 / 2 ) g ( y ) μ s ( d y ) , x ∈ S , (\widetilde{\mathcal{K}}g)(\mathbf{x}) := \int f\left(\frac{\lVert\mathbf{x}-\mathbf{y}\rVert_2}{h^{1/2}}\right)g(\mathbf{y})\mu_s(\mathrm{d}y), \qquad\mathbf{x}\in\mathcal{S}, ( K g ) ( x ) := ∫ f ( h 1/2 ∥ x − y ∥ 2 ) g ( y ) μ s ( d y ) , x ∈ S ,
with eigenvalue-eigenfunction pairs { ( γ ~ i , ϕ ~ i ) } i ≥ 1 \{(\widetilde{\gamma}_i,\widetilde{\phi}_i)\}_{i\geq1} {( γ i , ϕ i ) } i ≥ 1 . Zero-bandwidth kernels and zero-eigenvalue weighted coordinates are defined to be zero.
Define ζ 0 : = inf 0 ≤ x ≤ 1 ζ ( x ) \zeta_0:=\inf_{0\leq x\leq1}\zeta(x) ζ 0 := inf 0 ≤ x ≤ 1 ζ ( x ) , τ 0 : = inf s , t ≥ 0 τ ( s , t ) \tau_0:=\inf_{s,t\geq0}\tau(s,t) τ 0 := inf s , t ≥ 0 τ ( s , t ) , and
ξ : = { τ 0 , if ζ 0 ≥ τ 0 , ( τ 0 + ζ 0 ) / 2 , if 0 ≤ ζ 0 < τ 0 . \xi:=
\begin{cases}
\tau_0, & \text{if }\zeta_0\geq\tau_0,\\
(\tau_0+\zeta_0)/2, & \text{if }0\leq\zeta_0<\tau_0.
\end{cases} ξ := { τ 0 , ( τ 0 + ζ 0 ) /2 , if ζ 0 ≥ τ 0 , if 0 ≤ ζ 0 < τ 0 .
Recall G G G in (26) and ψ n \psi_n ψ n in (24) . We have the following spectral convergence results.
Theorem C.13 (Spectral convergence with general f f f ). Suppose Assumptions 3.1 , 3.2, 3.3 and C.11 hold. For w w w satisfying the density condition in Theorem 3.8 , we have
max i ∈ [ n ] ∣ λ i − γ i ∣ = O ( ψ n ξ + n − τ 0 / 2 ) . \max_{i\in[n]}|\lambda_i-\gamma_i|=O\left(\psi_n^\xi+n^{-\tau_0/2}\right). i ∈ [ n ] max ∣ λ i − γ i ∣ = O ( ψ n ξ + n − τ 0 /2 ) . Moreover, for any fixed δ > 0 \delta>0 δ > 0 and any 1 ≤ i ≤ M ( δ ) 1\le i\le M(\delta) 1 ≤ i ≤ M ( δ ) with g i > 0 g_i>0 g i > 0 as in (30) , there exists a sign s i ∈ { − 1 , 1 } s_i\in\{-1,1\} s i ∈ { − 1 , 1 } such that, for any x ∈ S \boldsymbol{x}\in\mathcal{S} x ∈ S , we have
∣ λ i ϕ ^ i ( n ) ( x ) − s i γ i ϕ ~ i ( x ) ∣ = O ( ψ n ξ + n − τ 0 / 2 + 1 g i ( ψ n ξ / 2 + n − τ 0 / 2 ) ) . \left|\sqrt{\lambda_i}\widehat{\phi}_i^{(n)}(\boldsymbol{x})-s_i\sqrt{\gamma_i}\widetilde{\phi}_i(\boldsymbol{x})\right|
=O\left(\psi_n^\xi+n^{-\tau_0/2}+\frac{1}{g_i}\left(\psi_n^{\xi/2}+n^{-\tau_0/2}\right)\right). λ i ϕ i ( n ) ( x ) − s i γ i ϕ i ( x ) = O ( ψ n ξ + n − τ 0 /2 + g i 1 ( ψ n ξ /2 + n − τ 0 /2 ) ) .
Remark C.14. For the Gaussian kernel, ξ = τ 0 = 1 \xi=\tau_0=1 ξ = τ 0 = 1 , so the stated rates reduce to Theorem 3.8 .
Proof. Recall Φ h \Phi_h Φ h from Assumption C.11 . We define the normalized kernel matrices
K x = 1 n K n , K y ( i , j ) = 1 n Φ h ( s i , s j ) , K 0 ( i , j ) = 1 n Φ h ( s i , s j ) , 1 ≤ i , j ≤ n . \mathbf{K}_{x}=\frac{1}{n}\mathbf{K}_n,\qquad
\mathbf{K}_{y}(i,j)=\frac{1}{n}\Phi_h(\boldsymbol{s}_i,\boldsymbol{s}_j),\qquad
\mathbf{K}_{0}(i,j)=\frac{1}{n}\Phi_h(\boldsymbol{s}_i,\boldsymbol{s}_j),\qquad
1\le i,j\le n. K x = n 1 K n , K y ( i , j ) = n 1 Φ h ( s i , s j ) , K 0 ( i , j ) = n 1 Φ h ( s i , s j ) , 1 ≤ i , j ≤ n .
Denote the diameter of S \mathcal{S} S by D D D . By (C.47), for sufficiently large n n n , we have ∣ h − h ∣ ≤ h / 4 |h-h| \le h/4 ∣ h − h ∣ ≤ h /4 with high probability.
For a clean squared distance a ≤ D 2 a\le D^2 a ≤ D 2 and its projected counterpart b b b , we have ∣ b / h n − a / h ∣ ≤ C ( ∣ b − a ∣ + ∣ h n − h ∣ ) |b/h_n-a/h|\le C(|b-a|+|h_n-h|) ∣ b / h n − a / h ∣ ≤ C ( ∣ b − a ∣ + ∣ h n − h ∣ ) if h n ≥ h / 2 h_n\ge h/2 h n ≥ h /2 . In the entrywise comparison leading to Eqs. (109)–(111) of [20 ] , the kernel regularity bound gives ∣ f ( t ) − f ( s ) ∣ ≤ C ∣ t 2 − s 2 ∣ ξ |f(t)-f(s)|\le C|t^2-s^2|^\xi ∣ f ( t ) − f ( s ) ∣ ≤ C ∣ t 2 − s 2 ∣ ξ . Applying this step with t = b / h n t=\sqrt{b/h_n} t = b / h n and s = a / h s=\sqrt{a/h} s = a / h , we obtain
∣ f ( b / h n ) − f ( a / h ) ∣ ≤ C ( ∣ b − a ∣ + ∣ h n − h ∣ ) ξ . (82) \left|f\left(\sqrt{b/h_n}\right)-f\left(\sqrt{a/h}\right)\right|
\le C(|b-a|+|h_n-h|)^\xi. \tag*{(82)} f ( b / h n ) − f ( a / h ) ≤ C ( ∣ b − a ∣ + ∣ h n − h ∣ ) ξ . (82)
For h n < h / 2 h_n<h/2 h n < h /2 this follows from boundedness and ∣ h n − h ∣ ≥ h / 4 |h_n-h|\ge h/4 ∣ h n − h ∣ ≥ h /4 . To compare the two clean kernels, take s = a / h s=\sqrt{a/h} s = a / h and t = a / h t=\sqrt{a/h} t = a / h . Then ∣ s − t ∣ ≤ C ∣ h − h ∣ ≤ 1 |s-t|\le C|h-h| \le1 ∣ s − t ∣ ≤ C ∣ h − h ∣ ≤ 1 with high probability by (C.47). Since s ξ ( s ) s^\xi(s) s ξ ( s ) and t ξ ( t ) t^\xi(t) t ξ ( t ) in (C.49) are each at most one and τ ( s , t ) ≥ τ 0 \tau(s,t)\ge\tau_0 τ ( s , t ) ≥ τ 0 , we have
sup 0 ≤ a ≤ D 2 ∣ f ( a / h ) − f ( a / h ) ∣ ≤ C ∣ h − h ∣ τ 0 = O ( n − τ 0 / 2 ) . (83) \sup_{0\le a\le D^2}\left|f\left(\sqrt{a/h}\right)-f\left(\sqrt{a/h}\right)\right|
\le C|h-h|^{\tau_0}=O\left(n^{-\tau_0/2}\right). \tag*{(83)} 0 ≤ a ≤ D 2 sup f ( a / h ) − f ( a / h ) ≤ C ∣ h − h ∣ τ 0 = O ( n − τ 0 /2 ) . (83)
To evaluate the eigenfunctions, we fix x ∈ S \boldsymbol{x}\in\mathcal{S} x ∈ S and define three vectors in R n \mathbb{R}^n R n by their entries
( k x ) j = Φ h n ( P T x , P T x j ) , ( k y ) j = Φ h ( x , s j ) , ( k 0 ) j = Φ h ( x , s j ) , j = 1 , … , n . (k_x)_j=\Phi_{h_n}(\mathbf{P}^{\mathsf{T}}\boldsymbol{x},\mathbf{P}^{\mathsf{T}}\boldsymbol{x}_j),\qquad
(k_y)_j=\Phi_h(\boldsymbol{x},\boldsymbol{s}_j),\qquad
(k_0)_j=\Phi_h(\boldsymbol{x},\boldsymbol{s}_j),\qquad
j=1,\ldots,n. ( k x ) j = Φ h n ( P T x , P T x j ) , ( k y ) j = Φ h ( x , s j ) , ( k 0 ) j = Φ h ( x , s j ) , j = 1 , … , n .
Thus λ i ϕ ^ i ( n ) ( x ) = k x T u i / n λ i \sqrt{\lambda_i}\widehat{\phi}_i^{(n)}(\boldsymbol{x})=k_x^{\mathsf{T}}\boldsymbol{u}_i/\sqrt{n\lambda_i} λ i ϕ i ( n ) ( x ) = k x T u i / n λ i for λ i > 0 \lambda_i>0 λ i > 0 . Write M n = max j , ℓ ∣ w ℓ T z j ∣ M_n=\max_{j,\ell}|\boldsymbol{w}_{\ell}^{\mathsf{T}}\boldsymbol{z}_j| M n = max j , ℓ ∣ w ℓ T z j ∣ . The sub-Gaussian bound (C.7) gives P ( ∣ w ℓ T z j ∣ > t ) ≤ 2 exp ( − c t 2 ) \mathbb{P}(|\boldsymbol{w}_{\ell}^{\mathsf{T}}\boldsymbol{z}_j|>t)\le2\exp(-ct^2) P ( ∣ w ℓ T z j ∣ > t ) ≤ 2 exp ( − c t 2 ) for t > 0 t>0 t > 0 . A union bound gives P ( M n > σ t ) ≤ 2 n p exp ( − c t 2 ) \mathbb{P}(M_n>\sigma t)\le2np\exp(-ct^2) P ( M n > σ t ) ≤ 2 n p exp ( − c t 2 ) , hence M n = O P ( σ ) M_n=O_{\mathbb{P}}(\sigma) M n = O P ( σ ) since p ≃ n α p\simeq n^\alpha p ≃ n α .
Recall from (12) that U = span { r 1 , … , r r } \mathcal{U}=\operatorname{span}\{\boldsymbol{r}_1,\ldots,\boldsymbol{r}_r\} U = span { r 1 , … , r r } is the signal subspace, so d j = x − s j ∈ U \boldsymbol{d}_j=\boldsymbol{x}-\boldsymbol{s}_j\in\mathcal{U} d j = x − s j ∈ U . By compactness in Assumption 3.2 and Lemma C.1 , we have ∥ d j ∥ 2 ≤ D \|\boldsymbol{d}_j\|_2\le D ∥ d j ∥ 2 ≤ D and ∣ w ℓ T d j ∣ ≤ D ρ ℓ |\boldsymbol{w}_{\ell}^{\mathsf{T}}\boldsymbol{d}_j|\le D\rho_\ell ∣ w ℓ T d j ∣ ≤ D ρ ℓ . Expanding the squared distance, we have
Q j : = ∥ P T ( x − x j ) ∥ 2 2 − ∥ d j ∥ 2 2 = − ∥ ( I − Π P ) d j ∥ 2 2 + ∥ P T z j ∥ 2 2 − 2 d j T Π P z j . Q_j:=\|\mathbf{P}^{\mathsf{T}}(\boldsymbol{x}-\boldsymbol{x}_j)\|_2^2-\|\boldsymbol{d}_j\|_2^2
=-\|(\mathbf{I}-\mathbf{\Pi}_{\mathbf{P}})\boldsymbol{d}_j\|_2^2+\|\mathbf{P}^{\mathsf{T}}\boldsymbol{z}_j\|_2^2-2\boldsymbol{d}_j^{\mathsf{T}}\mathbf{\Pi}_{\mathbf{P}}\boldsymbol{z}_j. Q j := ∥ P T ( x − x j ) ∥ 2 2 − ∥ d j ∥ 2 2 = − ∥ ( I − Π P ) d j ∥ 2 2 + ∥ P T z j ∥ 2 2 − 2 d j T Π P z j .
Bounding the last two terms over the K K K selected directions, we obtain
max j ∣ Q j ∣ ≤ D 2 ∥ ( I − Π P ) Π U ∥ o p 2 + K M n 2 + 2 D M n ∑ m ≤ K ρ ( m ) = O < ( ψ n ) , (84) \max_j |Q_j| \le D^2\|(\mathbf{I}-\Pi_P)\Pi_U\|_{\mathrm{op}}^2 + KM_n^2 + 2DM_n\sum_{m\le K}\rho(m) = O_{<}(\psi_n), \tag*{(84)} j max ∣ Q j ∣ ≤ D 2 ∥ ( I − Π P ) Π U ∥ op 2 + K M n 2 + 2 D M n m ≤ K ∑ ρ ( m ) = O < ( ψ n ) , (84)
where in the last step we used Theorem C.5 for the bias and (C.32) for the interaction. For the noise terms in (C.38), recall the cutoff c ∗ c_{\ast} c ∗ in (C.22). We use (C.22) when σ 2 / Θ ≤ c ∗ \sigma^2/\Theta\le c_{\ast} σ 2 /Θ ≤ c ∗ and the bound K ≲ ( Θ / σ 2 ) q / 2 K \lesssim(\Theta/\sigma^2)^{q/2} K ≲ ( Θ/ σ 2 ) q /2 from the proof of Theorem 3.6 when σ 2 / Θ > c ∗ \sigma^2/\Theta> c_{\ast} σ 2 /Θ > c ∗ .
By (C.50),
n − 1 / 2 ∥ k x − k y ∥ 2 ≤ max j ∣ ( k x ) j − ( k y ) j ∣ ≤ C ( max j ∣ Q j ∣ + ∣ h n − h ∣ ) ξ = O < ( ψ n ξ ) , (85) n^{-1/2}\|k_x-k_y\|_2 \le\max_j |(k_x)_j-(k_y)_j| \le C\left(\max_j |Q_j|+|h_n-h|\right)^\xi= O_{<}(\psi_n^\xi), \tag*{(85)} n − 1/2 ∥ k x − k y ∥ 2 ≤ j max ∣ ( k x ) j − ( k y ) j ∣ ≤ C ( j max ∣ Q j ∣ + ∣ h n − h ∣ ) ξ = O < ( ψ n ξ ) , (85)
where in the last step we used (C.52) and the bandwidth bound ∣ h n − h ∣ ≤ Δ n = O < ( ψ n ) |h_n-h|\le\Delta_n=O_{<}(\psi_n) ∣ h n − h ∣ ≤ Δ n = O < ( ψ n ) in (C.41). Moreover, we also have ∣ b − a ∣ ≤ Δ n |b-a|\le\Delta_n ∣ b − a ∣ ≤ Δ n . By (C.50)–(C.51) and ∥ A / n ∥ o p ≤ max j , k ∣ A j k ∣ \|A/n\|_{\mathrm{op}}\le\max_{j,k}|A_{jk}| ∥ A / n ∥ op ≤ max j , k ∣ A j k ∣ , we obtain
ϵ p : = ∥ K x − K y ∥ o p = O < ( ψ n ξ ) , \epsilon_{\mathrm{p}}:=\|K_x-K_y\|_{\mathrm{op}}=O_{<}(\psi_n^\xi), ϵ p := ∥ K x − K y ∥ op = O < ( ψ n ξ ) ,
ϵ h : = ∥ K y − K 0 ∥ o p = O < ( n − τ 0 / 2 ) , \epsilon_{\mathrm{h}}:=\|K_y-K_0\|_{\mathrm{op}}=O_{<}(n^{-\tau_0/2}), ϵ h := ∥ K y − K 0 ∥ op = O < ( n − τ 0 /2 ) ,
n − 1 / 2 ∥ k y − k 0 ∥ 2 = O < ( n − τ 0 / 2 ) . (86) n^{-1/2}\|k_y-k_0\|_2=O_{<}(n^{-\tau_0/2}). \tag*{(86)} n − 1/2 ∥ k y − k 0 ∥ 2 = O < ( n − τ 0 /2 ) . (86)
In the reproducing kernel Hilbert space H \mathcal{H} H of Φ h \Phi_h Φ h , we write k s = Φ h ( ⋅ , s ) k_s=\Phi_h(\mathord{\cdot},s) k s = Φ h ( ⋅ , s ) . For g ∈ H g\in\mathcal{H} g ∈ H , define the empirical and population operators by
C n g = 1 n ∑ j = 1 n g ( s j ) k s j , C g = ∫ S g ( s ) k s μ s ( d s ) . C_ng=\frac{1}{n}\sum_{j=1}^{n}g(s_j)k_{s_j},\qquad Cg=\int_S g(s)k_s\,\mu_s(\mathrm{d}s). C n g = n 1 j = 1 ∑ n g ( s j ) k s j , C g = ∫ S g ( s ) k s μ s ( d s ) .
Their nonzero eigenvalues are those of K 0 \mathbf{K}_0 K 0 and K ~ \widetilde{\mathbf{K}} K , respectively. Since the clean samples are i.i.d. and the kernel is bounded, [20 Lemma 5] gives η n : = ∥ C n − C ∥ o p = O < ( n − 1 / 2 ) \eta_n:=\|C_n-C\|_{\mathrm{op}}=O_{<}(n^{-1/2}) η n := ∥ C n − C ∥ op = O < ( n − 1/2 ) . By Weyl’s inequality and (C.54), using n − 1 / 2 ≤ n − τ 0 / 2 n^{-1/2}\le n^{-\tau_0/2} n − 1/2 ≤ n − τ 0 /2 for 0 < τ 0 ≤ 1 0<\tau_0\le1 0 < τ 0 ≤ 1 , we have
max i ≤ n ∣ λ i − γ i ∣ ≤ ϵ p + ϵ h + η n = O < ( ψ n ξ + n − τ 0 / 2 ) . (87) \max_{i\le n}|\lambda_i-\gamma_i|\le\epsilon_{\mathrm{p}}+\epsilon_{\mathrm{h}}+\eta_n=O_{<}(\psi_n^\xi+n^{-\tau_0/2}). \tag*{(87)} i ≤ n max ∣ λ i − γ i ∣ ≤ ϵ p + ϵ h + η n = O < ( ψ n ξ + n − τ 0 /2 ) . (87)
Write ε = ϵ p + ϵ h + η n \varepsilon=\epsilon_{\mathrm{p}}+\epsilon_{\mathrm{h}}+\eta_n ε = ϵ p + ϵ h + η n . Fix i ≤ M ( δ ) i\le M(\delta) i ≤ M ( δ ) with g i > 0 g_i>0 g i > 0 and suppose first that ε < min ( g i , δ ) / 16 \varepsilon<\min(g_i,\delta)/16 ε < min ( g i , δ ) /16 . Let ( β j , v j ) (\beta_j,\mathbf{v}_j) ( β j , v j ) and ( β j 0 , v j 0 ) (\beta_j^0,\mathbf{v}_j^0) ( β j 0 , v j 0 ) be the j j j th eigenpairs of K y \mathbf{K}_y K y and K 0 \mathbf{K}_0 K 0 , respectively. The Weyl bounds used in (C.55) give
max { ∣ λ j − γ j ∣ , ∣ β j − γ j ∣ , ∣ β j 0 − γ j ∣ } ≤ ε , j ∈ [ n ] . \max\{|\lambda_j-\gamma_j|,|\beta_j-\gamma_j|,|\beta_j^0-\gamma_j|\}\le\varepsilon,\qquad j\in[n]. max { ∣ λ j − γ j ∣ , ∣ β j − γ j ∣ , ∣ β j 0 − γ j ∣ } ≤ ε , j ∈ [ n ] .
Since γ i ≥ δ \gamma_i\ge\delta γ i ≥ δ by (29) , all three i i i th eigenvalues exceed δ / 2 \delta/2 δ /2 . Recall from (30) that g i g_i g i is the distance from γ i \gamma_i γ i to its nearest neighbor in the population spectrum. Each end of an adjacent gap moves by at most ε \varepsilon ε , so the gap at the i i i th eigenvalue of each matrix is at least g i − 2 ε > 7 g i / 8 g_i-2\varepsilon>7g_i/8 g i − 2 ε > 7 g i /8 . We now define the clean weighted coordinates at x x x by
F i , y = k y T v i n β i , F i , 0 = k 0 T v i 0 n β i 0 . F_{i,y}=\frac{k_y^{\mathsf{T}}\mathbf{v}_i}{\sqrt{n\beta_i}},\qquad F_{i,0}=\frac{k_0^{\mathsf{T}}\mathbf{v}_i^0}{\sqrt{n\beta_i^0}}. F i , y = n β i k y T v i , F i , 0 = n β i 0 k 0 T v i 0 .
To compare with F i , y F_{i,y} F i , y , we first change the eigenvalue factor and then the kernel vector. Since n − 1 / 2 ∥ k x ∥ 2 ≤ B f n^{-1/2}\lVert k_x\rVert_2 \le B_f n − 1/2 ∥ k x ∥ 2 ≤ B f and ∥ u i ∥ 2 = 1 \lVert u_i\rVert_2=1 ∥ u i ∥ 2 = 1 , we have
∣ 1 λ i − 1 β i ∣ ∣ k x T u i ∣ n ≤ C δ , B f ∣ λ i − β i ∣ ≤ C δ , B f ϵ p = O ≺ ( ψ n ξ ) , \left|\frac{1}{\sqrt{\lambda_i}}-\frac{1}{\sqrt{\beta_i}}\right|\frac{|k_x^{\mathsf T}u_i|}{\sqrt{n}}\le C_{\delta,B_f}|\lambda_i-\beta_i|\le C_{\delta,B_f}\epsilon_p=O_{\prec}(\psi_n^\xi), λ i 1 − β i 1 n ∣ k x T u i ∣ ≤ C δ , B f ∣ λ i − β i ∣ ≤ C δ , B f ϵ p = O ≺ ( ψ n ξ ) ,
∣ ( k x − k y ) T u i ∣ n β i ≤ C δ n − 1 / 2 ∥ k x − k y ∥ 2 = O ≺ ( ψ n ξ ) , \frac{|(k_x-k_y)^{\mathsf T}u_i|}{\sqrt{n\beta_i}}\le C_\delta n^{-1/2}\lVert k_x-k_y\rVert_2=O_{\prec}(\psi_n^\xi), n β i ∣ ( k x − k y ) T u i ∣ ≤ C δ n − 1/2 ∥ k x − k y ∥ 2 = O ≺ ( ψ n ξ ) ,
where we used (C.54) and (C.53), respectively. For the remaining term, by Cauchy–Schwarz we have that, for either sign s 1 s_1 s 1 ,
∣ k y T ( u i − s 1 v i ) ∣ n β i ≤ ∥ k y ∥ 2 n β i ∥ u i − s 1 v i ∥ 2 ≤ C δ , B f ∥ u i − s 1 v i ∥ 2 . \frac{|k_y^{\mathsf T}(u_i-s_1v_i)|}{\sqrt{n\beta_i}}\le\frac{\lVert k_y\rVert_2}{\sqrt{n\beta_i}}\lVert u_i-s_1v_i\rVert_2\le C_{\delta,B_f}\lVert u_i-s_1v_i\rVert_2. n β i ∣ k y T ( u i − s 1 v i ) ∣ ≤ n β i ∥ k y ∥ 2 ∥ u i − s 1 v i ∥ 2 ≤ C δ , B f ∥ u i − s 1 v i ∥ 2 .
Moreover, by the squared alignment estimate in [20 Eqs. (113)–(116)] , we can choose s 1 s_1 s 1 such that
∥ u i − s 1 v i ∥ 2 2 = O ≺ ( ψ n ξ g i 2 ) . \lVert u_i-s_1v_i\rVert_2^2=O_{\prec}\left(\frac{\psi_n^\xi}{g_i^2}\right). ∥ u i − s 1 v i ∥ 2 2 = O ≺ ( g i 2 ψ n ξ ) .
Combining the three terms as in [20 Eqs. (117)–(119)] , we obtain
∣ λ i ϕ ^ i ( n ) ( x ) − s 1 F i , y ∣ 2 = O ≺ ( ψ n 2 ξ + ψ n ξ g i 2 ) . (88) \left|\sqrt{\lambda_i}\widehat{\phi}_i^{(n)}(x)-s_1F_{i,y}\right|^2=O_{\prec}\left(\psi_n^{2\xi}+\frac{\psi_n^\xi}{g_i^2}\right). \tag*{(88)} λ i ϕ i ( n ) ( x ) − s 1 F i , y 2 = O ≺ ( ψ n 2 ξ + g i 2 ψ n ξ ) . (88)
Next, by Weyl’s inequality applied to the clean kernel matrices K y \mathbf{K}_y K y and K 0 \mathbf{K}_0 K 0 , we have ∣ β i − β i 0 ∣ ≤ ∥ K y − K 0 ∥ o p = e h |\beta_i-\beta_i^0|\le\lVert\mathbf{K}_y-\mathbf{K}_0\rVert_{\mathrm{op}}=e_h ∣ β i − β i 0 ∣ ≤ ∥ K y − K 0 ∥ op = e h . Since the gap at β i 0 \beta_i^0 β i 0 exceeds 7 g i / 8 7g_i/8 7 g i /8 , the eigenvector perturbation bound in [20 Lemma 14] gives ∥ v i − s 2 v i 0 ∥ 2 ≤ C e h / g i \lVert v_i-s_2v_i^0\rVert_2\le C e_h/g_i ∥ v i − s 2 v i 0 ∥ 2 ≤ C e h / g i for a sign s 2 s_2 s 2 . Substituting these bounds and (C.54) into the same decomposition, we have
∣ F i , y − s 2 F i , 0 ∣ ≤ C δ , B f ( e h + n − 1 / 2 ∥ k y − k 0 ∥ 2 + e h / g i ) = O ≺ ( n − τ 0 / 2 ( 1 + g i − 1 ) ) . (89) |F_{i,y}-s_2F_{i,0}|\le C_{\delta,B_f}\left(e_h+n^{-1/2}\lVert k_y-k_0\rVert_2+e_h/g_i\right)=O_{\prec}\left(n^{-\tau_0/2}(1+g_i^{-1})\right). \tag*{(89)} ∣ F i , y − s 2 F i , 0 ∣ ≤ C δ , B f ( e h + n − 1/2 ∥ k y − k 0 ∥ 2 + e h / g i ) = O ≺ ( n − τ 0 /2 ( 1 + g i − 1 ) ) . (89)
Finally, F i , 0 F_{i,0} F i , 0 and γ ~ i ϕ ~ i ( x ) \sqrt{\widetilde{\gamma}_i}\widetilde{\phi}_i(x) γ i ϕ i ( x ) are values of unit eigenfunctions of C n C_n C n and C C C at x x x . The same perturbation bound gives an H \mathcal{H} H -norm error of at most C η n / g i C\eta_n/g_i C η n / g i after alignment by a sign s 3 s_3 s 3 . Since ∣ v ( x ) ∣ ≤ f ( 0 ) ∥ v ∥ H |v(x)|\le\sqrt{f(0)}\lVert v\rVert_{\mathcal{H}} ∣ v ( x ) ∣ ≤ f ( 0 ) ∥ v ∥ H , we get
∣ F i , 0 − s 3 γ ~ i ϕ ~ i ( x ) ∣ = O ≺ ( n − 1 / 2 / g i ) . (90) |F_{i,0}-s_3\sqrt{\widetilde{\gamma}_i}\widetilde{\phi}_i(x)|=O_{\prec}(n^{-1/2}/g_i). \tag*{(90)} ∣ F i , 0 − s 3 γ i ϕ i ( x ) ∣ = O ≺ ( n − 1/2 / g i ) . (90)
It remains to consider ϵ ≥ min ( g i , δ ) / 16 \epsilon\ge\min(g_i,\delta)/16 ϵ ≥ min ( g i , δ ) /16 . This case can occur at high noise. As shown in the proof of Theorem 3.6 , for sufficiently large σ 2 / Θ \sigma^2/\Theta σ 2 /Θ we have K = 0 \mathbf{K}=0 K = 0 with high probability. Then h n = 0 h_n=0 h n = 0 and λ i = 0 \lambda_i=0 λ i = 0 by the zero-bandwidth convention, so (C.55) gives ϵ ≥ γ i ≥ δ \epsilon\ge\gamma_i\ge\delta ϵ ≥ γ i ≥ δ . To bound the coordinates throughout this case, let G x G_x G x be the Gram matrix of Φ h n \Phi_{h_n} Φ h n on P T x 1 , … , P T x n , P T x \mathsf{P}^{\mathsf T}x_1,\ldots,\mathsf{P}^{\mathsf T}x_n,\mathsf{P}^{\mathsf T}x P T x 1 , … , P T x n , P T x , in that order. Let a i = ( u i T , 0 ) T a_i=(u_i^{\mathsf T},0)^{\mathsf T} a i = ( u i T , 0 ) T and e n + 1 = ( 0 , … , 0 , 1 ) T e_{n+1}=(0,\ldots,0,1)^{\mathsf T} e n + 1 = ( 0 , … , 0 , 1 ) T in R n + 1 \mathbb{R}^{n+1} R n + 1 . The first n n n entries of G x e n + 1 G_xe_{n+1} G x e n + 1 form k x k_x k x . For 1 ≤ j , k ≤ n 1\le j,k\le n 1 ≤ j , k ≤ n , recall from (6) that y j − y k = P T ( x j − x k ) y_j-y_k=\mathsf{P}^{\mathsf T}(x_j-x_k) y j − y k = P T ( x j − x k ) , so
G x ( j , k ) = Φ h n ( P T x j , P T x k ) = Φ h n ( y j , y k ) = K n ( j , k ) . G_x(j,k)=\Phi_{h_n}(\mathsf{P}^{\mathsf T}x_j,\mathsf{P}^{\mathsf T}x_k)=\Phi_{h_n}(y_j,y_k)=K_n(j,k). G x ( j , k ) = Φ h n ( P T x j , P T x k ) = Φ h n ( y j , y k ) = K n ( j , k ) .
Since the last entry of a i a_i a i is zero, a i T G x a i = u i T K n u i a_i^\mathsf{T}G_xa_i=u_i^\mathsf{T}K_nu_i a i T G x a i = u i T K n u i . Applying Cauchy–Schwarz for the positive semidefinite matrix G x G_x G x to a i a_i a i and e n + 1 e_{n+1} e n + 1 , we obtain
∣ k x T u i ∣ 2 ≤ ( u i T K n u i ) ( e n + 1 T G x e n + 1 ) ≤ ( u i T K n u i ) f ( 0 ) = n λ i f ( 0 ) . \left|k_x^\mathsf{T}u_i\right|^2 \le\left(u_i^\mathsf{T}K_nu_i\right)\left(e_{n+1}^\mathsf{T}G_xe_{n+1}\right) \le\left(u_i^\mathsf{T}K_nu_i\right)f(0)=n\lambda_i f(0). k x T u i 2 ≤ ( u i T K n u i ) ( e n + 1 T G x e n + 1 ) ≤ ( u i T K n u i ) f ( 0 ) = n λ i f ( 0 ) .
where in the last inequality we used e n + 1 T G x e n + 1 ≤ f ( 0 ) e_{n+1}^\mathsf{T}G_xe_{n+1}\le f(0) e n + 1 T G x e n + 1 ≤ f ( 0 ) , and in the last equality we used n − 1 K n u i = λ i u i n^{-1}K_nu_i=\lambda_i u_i n − 1 K n u i = λ i u i and ∥ u i ∥ 2 = 1 \lVert u_i\rVert_2=1 ∥ u i ∥ 2 = 1 . Thus the empirical weighted coordinate is bounded by B f \sqrt{B_f} B f , as is the population coordinate by the reproducing property. Since e p ≤ 2 B f e_p\le2B_f e p ≤ 2 B f and g i ≤ γ i ≤ B f g_i\le\gamma_i\le B_f g i ≤ γ i ≤ B f , the condition on e p + e h + η n e_p+e_h+\eta_n e p + e h + η n in this case gives, for either sign s i s_i s i ,
∣ λ i ϕ ^ i ( n ) ( x ) − s i γ i ϕ ~ i ( x ) ∣ ≤ 2 B f ≤ C δ , B f e p + e h + η n g i . \left|\sqrt{\lambda_i}\widehat{\phi}_i^{(n)}(x)-s_i\sqrt{\gamma_i}\widetilde{\phi}_i(x)\right|\le2\sqrt{B_f}\le C_{\delta,B_f}\frac{\sqrt{e_p}+e_h+\eta_n}{g_i}. λ i ϕ i ( n ) ( x ) − s i γ i ϕ i ( x ) ≤ 2 B f ≤ C δ , B f g i e p + e h + η n .
In the first case we choose s i = s 1 s 2 s 3 s_i=s_1s_2s_3 s i = s 1 s 2 s 3 and add the square root of (C.56) to the bounds in (C.57) and (C.58). In both cases we obtain
∣ λ i ϕ ^ i ( n ) ( x ) − s i γ i ϕ ~ i ( x ) ∣ = O ( ψ n ξ + n − τ 0 / 2 + ψ n ξ / 2 + n − τ 0 / 2 g i ) . (91) \left|\sqrt{\lambda_i}\widehat{\phi}_i^{(n)}(x)-s_i\sqrt{\gamma_i}\widetilde{\phi}_i(x)\right|=O\left(\psi_n^\xi+n^{-\tau_0/2}+\frac{\psi_n^{\xi/2}+n^{-\tau_0/2}}{g_i}\right). \tag*{(91)} λ i ϕ i ( n ) ( x ) − s i γ i ϕ i ( x ) = O ( ψ n ξ + n − τ 0 /2 + g i ψ n ξ /2 + n − τ 0 /2 ) . (91)
For the Gaussian kernel, ξ = τ 0 = 1 \xi=\tau_0=1 ξ = τ 0 = 1 , so (C.55) and (C.59) give the eigenvalue and eigenfunction rates in Theorem 3.8 , respectively. This completes the proof.
Supplementary Algorithms
Selection of ω \omega ω
We now specify how to choose ω \omega ω in (11) . We first generate m m m candidate quantile levels from the trimmed interval ( ε , 1 − ε ) (\varepsilon,1-\varepsilon) ( ε , 1 − ε ) , and for each candidate we identify the corresponding location in the ordered pairwise squared distances. We then compare the local spacing of neighboring ordered distances within a window of size s s s around each candidate and select the one with the smallest such spacing. Throughout the paper, we use the default values ε = 0.05 \varepsilon=0.05 ε = 0.05 , s = 5 s=5 s = 5 , and m = 100 m=100 m = 100 . This procedure is summarized in Algorithm S.1.
Selection of the Number of Embeddings Used
We specify how to choose the number of embeddings used in (9) . We select d d d by an eigenvalue-ratio rule in the spirit of [22 ] : among the empirical eigenvalues of n − 1 K n n^{-1}K_n n − 1 K n , we identify the last index at which the ratio of two successive eigenvalues exceeds a prescribed fixed threshold. We use the default threshold α = 1.05 \alpha=1.05 α = 1.05 . The resulting procedure is summarized in Algorithm S.2.
Algorithm S.1 Selection of the quantile level ω \omega ω
Inputs: Ordered pairwise squared distances { d ( j ) } j = 1 M \{d_{(j)}\}_{j=1}^{M} { d ( j ) } j = 1 M with M = ( n 2 ) M=\binom{n}{2} M = ( 2 n ) , a trimming constant ε ∈ ( 0 , 1 / 2 ) \varepsilon\in(0,1/2) ε ∈ ( 0 , 1/2 ) , a small fixed integer s s s with 1 ≤ s ≤ M ε 1 \le s \le M\varepsilon 1 ≤ s ≤ M ε , and a positive integer m m m .
Step one: Generate m m m candidate values
ω ( 1 ) , … , ω ( m ) ∼ i i d Unif ( ε , 1 − ε ) . \omega^{(1)},\ldots,\omega^{(m)} \mathrel{\overset{\mathrm{iid}}{\sim}} \operatorname{Unif}(\varepsilon,1-\varepsilon). ω ( 1 ) , … , ω ( m ) ∼ iid Unif ( ε , 1 − ε ) .
Step two: For each ℓ = 1 , … , m \ell=1,\ldots,m ℓ = 1 , … , m , compute
j ℓ = ⌈ M ω ( ℓ ) ⌉ . j_{\ell}=\left\lceil M\omega^{(\ell)}\right\rceil. j ℓ = ⌈ M ω ( ℓ ) ⌉ .
Define
I s : = { ℓ ∈ [ m ] : s + 1 ≤ j ℓ ≤ M − s } . \mathcal{I}_{s}:=\{\ell\in[m]:s+1\le j_{\ell}\le M-s\}. I s := { ℓ ∈ [ m ] : s + 1 ≤ j ℓ ≤ M − s } .
Step three: Let
ℓ ∗ ∈ arg min ℓ ∈ I s { d ( j ℓ + s ) − d ( j ℓ − s ) } , \ell^{\ast}\in\operatorname*{arg\,min}_{\ell\in\mathcal{I}_{s}}\{d_{(j_{\ell}+s)}-d_{(j_{\ell}-s)}\}, ℓ ∗ ∈ ℓ ∈ I s arg min { d ( j ℓ + s ) − d ( j ℓ − s ) } ,
where ties are broken by choosing the smallest ℓ \ell ℓ . Set
ω = ω ( ℓ ∗ ) . \omega=\omega^{(\ell^{\ast})}. ω = ω ( ℓ ∗ ) .
Output: The selected quantile level ω \omega ω .
Algorithm S.2 Selection of number of embeddings
Inputs: Sorted eigenvalues { λ ^ i } i = 1 n \{\hat{\lambda}_{i}\}_{i=1}^{n} { λ ^ i } i = 1 n of n − 1 K n n^{-1}\mathbf{K}_{n} n − 1 K n with λ ^ 1 ≥ ⋯ ≥ λ ^ n \hat{\lambda}_{1}\ge\cdots\ge\hat{\lambda}_{n} λ ^ 1 ≥ ⋯ ≥ λ ^ n , and threshold α > 1 \alpha>1 α > 1 .
Action: Set
d = max ( { 1 ≤ i ≤ n − 1 : λ ^ i > α λ ^ i + 1 } ∪ { 1 } ) . d=\max\left(\{1\le i\le n-1:\hat{\lambda}_{i}>\alpha\hat{\lambda}_{i+1}\}\cup\{1\}\right). d = max ( { 1 ≤ i ≤ n − 1 : λ ^ i > α λ ^ i + 1 } ∪ { 1 } ) .
Output: d d d , the number of embeddings used.
Concentration Inequalities
In this section, we introduce the following standard concentration inequalities used in the proofs.
Lemma E.1 (Bernstein’s Inequality for Sub-Exponential Variables). Let X 1 , … , X N X_1,\ldots,X_N X 1 , … , X N be independent mean-zero sub-exponential random variables. Then for every t ≥ 0 t \ge0 t ≥ 0 ,
P ( ∣ ∑ i = 1 N X i ∣ ≥ t ) ≤ 2 exp ( − c min ( t 2 ∑ i = 1 N ∥ X i ∥ ψ 1 2 , t max i ∥ X i ∥ ψ 1 ) ) . \mathbb{P}\left(\left|\sum_{i=1}^{N}X_i\right|\ge t\right)\le2\exp\left(-c\min\left(\frac{t^2}{\sum_{i=1}^{N}\lVert X_i\rVert_{\psi_1}^2},\frac{t}{\max_i\lVert X_i\rVert_{\psi_1}}\right)\right). P ( i = 1 ∑ N X i ≥ t ) ≤ 2 exp ( − c min ( ∑ i = 1 N ∥ X i ∥ ψ 1 2 t 2 , max i ∥ X i ∥ ψ 1 t ) ) . where c > 0 c>0 c > 0 is some universal constant and ∥ ⋅ ∥ ψ 1 \lVert\cdot\rVert_{\psi_1} ∥ ⋅ ∥ ψ 1 denotes the sub-exponential norm.
Proof. See Theorem 2.8.1 in [68 ] .
Lemma E.2 (Bounded differences inequality). Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be independent random vectors with X i ∈ X X_i\in\mathcal{X} X i ∈ X for i = 1 , … , n i=1,\ldots,n i = 1 , … , n and let f : X × ⋯ × X → R f:\mathcal{X}\times\cdots\times\mathcal{X}\to\mathbb{R} f : X × ⋯ × X → R be measurable. Assume that there exist constants c 1 , … , c n ≥ 0 c_1,\ldots,c_n\ge0 c 1 , … , c n ≥ 0 such that, for every i = 1 , … , n i=1,\ldots,n i = 1 , … , n ,
sup x j ∈ X ( 1 ≤ j ≤ n ) x i ′ ∈ X ∣ f ( x 1 , … , x n ) − f ( x 1 , … , x i − 1 , x i ′ , x i + 1 , … , x n ) ∣ ≤ c i . \sup_{\substack{x_j\in\mathcal{X}\ (1\le j\le n)\\ x_i'\in\mathcal{X}}}\left|f(x_1,\ldots,x_n)-f(x_1,\ldots,x_{i-1},x_i',x_{i+1},\ldots,x_n)\right|\le c_i. x j ∈ X ( 1 ≤ j ≤ n ) x i ′ ∈ X sup ∣ f ( x 1 , … , x n ) − f ( x 1 , … , x i − 1 , x i ′ , x i + 1 , … , x n ) ∣ ≤ c i . Define
Z = f ( X 1 , … , X n ) , v = 1 4 ∑ i = 1 n c i 2 . Z=f(X_1,\ldots,X_n),\qquad v=\frac{1}{4}\sum_{i=1}^{n}c_i^2. Z = f ( X 1 , … , X n ) , v = 4 1 i = 1 ∑ n c i 2 . Then for every t > 0 t>0 t > 0 ,
P ( ∣ Z − E Z ∣ > t ) ≤ 2 exp ( − 2 t 2 ∑ i = 1 n c i 2 ) . \mathbb{P}(|Z-\mathbb{E}Z|>t)\le2\exp\left(-\frac{2t^2}{\sum_{i=1}^{n}c_i^2}\right). P ( ∣ Z − E Z ∣ > t ) ≤ 2 exp ( − ∑ i = 1 n c i 2 2 t 2 ) . Proof. See Theorem 6.2 in [11 ] .