Search Dimension in Unlabeled Projection Pursuit: A Scaling Law for Subspace Restriction

Rares Dimitrie Grozavescu; Mark Girolami

cs.LGSep 29, 2026

Search Dimension in Unlabeled Projection Pursuit: A Scaling Law for Subspace Restriction

Authors: Rares Dimitrie Grozavescu, Mark Girolami

Organizations: University of Cambridge

Abstract

Projection pursuit searches for a direction along which the data look least Gaussian. When the observation space contains a large Gaussian complement, the empirical objective can be minimized by a direction that carries no signal, with empirical kurtosis as low as at the truth. Sample splitting exposes rather than repairs this failure. Appending coordinates independent of the latent regime degrades the search while leaving Bayes recoverability unchanged. Restricting the search to the column space of a known forward operator removes the failure exactly on the negative-kurtosis branch. Estimating a principal subspace from the data is the alternative. In a controlled two-component model, the leading sufficient scalings differ in the gain with which the operator transmits the discriminant: $ς^{-4}$ for covariance-spike estimation and $ς^{-8}$ for fourth-moment search. At fixed search dimension, the measured threshold ratio collapses onto $n/p^2$ with exponent $0.156$ , close to the predicted $1/8$ . This is an empirically supported scaling motivated by sufficient bounds, not a proved asymptotically tight law. When the search dimension is varied, the measured exponent is $0.325$ , substantially larger than $1/8$ , and the tested range does not identify its functional form. The crossing location also depends on calibration and model configuration. Under a downstream excess-error criterion, the scaling largely disappears.

Figures & tables

Collapse on $n/p^{2}$ at fixed $d_{\mathrm{search}}$
	exponent	95% CI	$R^{2}$
fixed $15^{\circ}$ criterion	$0.150$	$[0.110,0.166]$	$0.964$
calibrated criterion	$0.156$	$[0.118,0.174]$	$0.965$
Rank dependence, $d_{\mathrm{search}}\in\{2,\ldots,32\}$
$\varsigma_{\mathrm{KPP}}$	$0.325$	$[0.259,0.399]$
$\varsigma_{\mathrm{PCA}}$	$-0.031$

Table 1: Measured threshold scalings. The fixed-rank collapse is fitted over

11

configurations and the rank comparison over

28

. The calibrated criterion is

15.4^{\circ}

–

20.5^{\circ}

on the collapse grid. The tested rank range does not distinguish the candidate functional forms.

$p$	$n$	$n/p^{2}$	$\varsigma_{\mathrm{PCA}}$	$\varsigma_{\mathrm{KPP}}$	ratio
1024	4096	0.004	2.200	0.924	0.42
512	4096	0.016	1.687	0.868	0.51
256	4096	0.062	1.240	0.911	0.73
128	4096	0.250	1.022	1.098	1.07
128	16384	1.000	0.659	0.819	1.24
32	4096	4.000	0.676	0.908	1.34

Table 2: Threshold discriminant gains and their ratio. The ratio crosses one at

n\approx 0.60\,p^{2}

under the 15 ∘ criterion at which it was measured; Section 5.1 shows why that number is not transportable. The same thresholds computed on cells with no optimizer gap, and re-searched at a 512-fold larger restart budget, are in Appendix A and agree to within the bootstrap interval of the crossing.

Figure 1: Ratio of the exact-subspace KPP threshold to the PCA-subspace threshold against

n/p^{2}

at fixed

r

. The fitted fixed-rank power law is shown for reference. The ratio crossing depends on the success criterion and model configuration; the marked value is for the baseline

15^{\circ}

criterion and is not interpreted as a universal constant.

Condition	Crossing	Exponent
	( $n/p^{2}$ )
$10^{\circ}$ criterion	$1.20$	$0.142$
$15^{\circ}$ criterion (baseline)	$0.60$	$0.150$
$20^{\circ}$ criterion	$0.30$	$0.145$
Strongest-spike discriminant	$0.006$	—
Anisotropic $\mathbf{\Sigma}$	not determined	—

Table 3: Sensitivity of the threshold comparison. The crossing changes with the angular criterion and with the covariance-spike configuration. For the anisotropic row, the prefactor shift is not constant across the rank grid, so no single crossing is reported.

Figure 2: Sample splitting exposes but does not remove the unrestricted-search failure. (a) Out-of-sample

\hat{\kappa}

for the split search follows the unrestricted full-sample arm and remains near zero, while the restricted arm approaches

\kappa_{\star}

. (b) With

n_{B}=800

, validation noise can make a spurious candidate look better than

u_{\star}

; with

n_{B}=12800

, validation correctly ranks

u_{\star}

above the selected candidate, but the search never proposed

u_{\star}

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

$p$	$n$	$n/p^{2}$	$\varsigma_{\mathrm{KPP}}$	gap-clean	budget
1024	4096	0.004	0.924	0.905	0.875
512	4096	0.016	0.868	0.868	0.868
256	4096	0.062	0.911	0.911	0.911
128	4096	0.250	1.098	1.098	1.098
128	16384	1.000	0.819	0.786	0.773
32	4096	4.000	0.908	0.908	0.906

Appendix

Table 4: The kurtosis threshold measured via the standard restart budget, on cells with an optimizer gap within the null tolerance, and re-searched at a 512-fold larger budget. The implied crossings are within the bootstrap interval of one another.

Figure 3: Direct evaluation of Theorem 1 . (a) Uniform deviation

\eta=\sup_{u\in U}|\hat{\kappa}_{T}(u)-\kappa(u)|

against

n

for the unrestricted search at several

p

(solid) and the operator-subspace restricted search at

r=4

(dashed). (b) The same data against

p

at fixed

n

; the shaded band spans the

d_{\mathrm{search}}^{1/2}

d_{\mathrm{search}}^{1}

dependence allowed by Eq. ( 6 ).

method	$\mathbf{H},\mathbf{\Phi},\sigma,\mathbf{K}$	$M$	$\mathcal{R}$	$(\pi,\mu,\mathbf{\Sigma})$	labels
	fwd. model	regimes	subspace	true
oracle (control)	yes	yes	yes	yes	no
latent-space $k$ -means	yes	yes	not used	no	no
kurtosis, full space	yes	yes	not used	no	no
kurtosis, operator-subspace	yes	yes	used	no	no
kurtosis, PCA-restricted	yes	yes	estimated	no	no

Appendix

Table 5: Train-time information available to each method.

Explore similar work

SuperPCA: subspace analysis and an efficient algorithm for high-dimensional PCA
Sep 22, 2026Irina-Beatrice Haas, Maike Meier, Yuji Nakatsukasa +1Principal Component Analysis Dimensionality Reduction
Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK · Bernoulli Institute for Mathematics, Computer Science and Artificial Intelligence, University of Groningen, 9700 AB, Groningen, The Netherlands · Institute of Mathematics, EPFL, 1015 Lausanne, Switzerland
Bidirectional Random Projections
Jun 9, 2026Chao Lan, Luyuan YangRandomized Sketching Linear Regression
a School of Computer Science, University of Oklahoma, U.S.
Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails
Sep 3, 2026Shi Fu, Huibo Xu, Qixin Zhang +1Sparse Recovery Heavy-Tailed Noise
Generative AI Lab, College of Computing and Data Science, Nanyang Technological University, Singapore

Sep 22, 2026, stat.MLJ/K move · Enter open · S save

SuperPCA: subspace analysis and an efficient algorithm for high-dimensional PCA

Irina-Beatrice Haas, Maike Meier, Yuji Nakatsukasa, Taejun Park

Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK · Bernoulli Institute for Mathematics, Computer Science and Artificial Intelligence, University of Groningen, 9700 AB, Groningen, The Netherlands · Institute of Mathematics, EPFL, 1015 Lausanne, Switzerland

Principal Component Analysis Dimensionality Reduction

Open paper AskPDF arXiv

Principal component analysis (PCA) is a fundamental tool to reduce the dimensionality of the data in many applications. PCA finds a few signal directions that contain most of the variability of the data by computing the eigenvectors of the sample covariance matrix. In this work, we focus on the spiked covariance model, in which the data vectors are defined by a few orthogonal signals plus an isotropic Gaussian noise, and our goal is to estimate one or more of the leading signals. Our main theoretical finding is that the subspace spanned by several leading eigenvectors of the sample covariance matrix contains significant information about the desired signals long before the individual eigenvectors converge to the population principal components. To prove this, we derive a posteriori bounds for the angle between the subspace spanned by the desired population signals and the subspace obtained from the sample using perturbation theory for singular vectors. This leads to a new algorithm, SuperPCA (SUbsPace subsamplER PCA), which capitalizes on an approximate eigenspace of the sample covariance matrix to find the leading signals far more efficiently and accurately than classical PCA in the high-dimensional, multi-signal setting. SuperPCA exploits only a small number of subsampled coordinates of the data, which can lead to tremendous savings in data acquisition cost, especially when the signals are approximately sparse. For the same number of measurements, SuperPCA can offer a factor

10

improvement in accuracy compared to the classical PCA method.

Abstract

Explore similar work

SuperPCA: subspace analysis and an efficient algorithm for high-dimensional PCA

Bidirectional Random Projections

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails