Basis-Free Support Recovery for Streaming Sparse Principal Subspaces

When the number of features is comparable to or larger than the number of samples, ordinary principal component analysis (PCA) fails. The top eigenvectors of the sample covariance become nearly orthogonal to the true ones, because noise spreads the spectrum and swamps the signal. Sparsity is the standard fix: assume the true components use only a few features, find those features, and run PCA on them. For a single component in a data stream, this is essentially solved. Kumar and Sarkar show that Oja's algorithm, a one-pass stochastic power iteration that updates a vector with each incoming sample, makes signal coordinates grow faster than noise coordinates. Thresholding its output therefore recovers the support in linear memory at the minimax rate (Oja's Algorithm for Streaming Sparse PCA). For $k>1$ components, every known route breaks. Deflation, which peels off one component at a time, can leave a dense residual matrix that destroys the sparse structure needed for the next component (Combinatorial Sparse PCA Beyond the Spiked Identity Model, Lemma 9). Convex relaxations recover the whole subspace at once but need an eigendecomposition of a $p\times p$ matrix at every iteration. Streaming block Oja handles $k$ components but has no sparsity mechanism, so it stays inconsistent in high dimensions.

This note proposes a simple way out. Instead of thresholding the $k$ estimated columns one by one, threshold a quantity that does not depend on how the columns are chosen: the diagonal of the projection onto the span of the block Oja iterate. These are the "leverage scores," one number per feature measuring how much of that feature lies in the estimated subspace. Because leverage scores are unchanged by any re-mixing of the columns, the coupling between components that blocks entrywise analysis for $k>1$ drops out of the statistic. We can then reuse the rank-one entrywise growth argument column by column. The target is a one-pass, $O(dk)$-memory estimator that recovers the union support of a top-$k$ sparse subspace and then estimates the subspace on it, under both shared and disjoint supports, with no deflation and no convex warm start.

Core Claim

Let $A_t$ be the incoming rank-one or low-rank update and $\eta$ the step size. Write $B_t=\prod_{s\le t}(I+\eta A_s)$ for the product matrix of unnormalized Oja, and let $Z\in\mathbb{R}^{d\times k'}$ be a Gaussian random initialization with $k'\ge k$ columns. Let $P_t$ be the orthogonal projection onto the column span of $B_tZ$. The statistic is

$$\ell_i \;=\; e_i^\top P_t e_i \;=\; (B_tZ)_{i\cdot}\,\big(Z^\top B_t^\top B_t Z\big)^{-1}(B_tZ)_{i\cdot}^\top ,$$

where $e_i$ is the $i$-th standard basis vector and $(B_tZ)_{i\cdot}$ is the $i$-th row. Because $P_t$ depends only on the span, $\ell_i$ is identical whether block Oja is run with QR re-orthonormalization at every step, as it must be for numerical stability, or left unnormalized.

In the unnormalized form, each column $B_tz_j$ is an independent run of rank-one unnormalized Oja from its own random start. The numerator is therefore governed exactly by the entrywise growth results of Kumar and Sarkar. The interaction between components is confined to a $k'\times k'$ Gram matrix, whose conditioning can be controlled with the Schatten-norm recursions developed for block Oja in Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates.

The claim is that thresholding $\ell_i$ at the top $r$ coordinates recovers the union support of the leading $k$-dimensional sparse subspace. Two properties follow from the construction. First, the requirement is only a gap between $\lambda_k$ and $\lambda_{k+1}$, because $P_t$ ignores rotations inside the top-$k$ block. Clustered eigenvalues within the block are therefore harmless. Second, the statistic treats shared, disjoint, and partially overlapping supports alike, because it scores features rather than components. A second pass then runs block Oja restricted to the $r$ selected coordinates, or exact PCA on an $r\times r$ sketch. If needed, a final varimax-style rotation on that small matrix recovers component-specific supports.

Research Program

The theoretical part has three pieces.

The first piece is a numerator bound. For $i$ inside the union support $S$, a sum over $j$ of the squared rank-one iterate entries $(e_i^\top B_t z_j)^2$ must dominate the same sum for $i\notin S$. We will adapt the Kumar–Sarkar entrywise argument from a single random start to $k'$ independent starts sharing one $B_t$.

The second piece is a denominator bound. The Gram matrix $Z^\top B_t^\top B_tZ$ has its top $k$ directions aligned with the signal and its remaining $k'-k$ directions at noise scale. Oversampling ($k'>k$) keeps its smallest relevant singular value away from zero. This is where the eigengap $\lambda_k-\lambda_{k+1}$ enters, and only there.

The third piece combines the two into a support-recovery guarantee and a final subspace error. The natural target is a squared sine error of order $k\,s_U\log d/n$, where $s_U$ is the union support size. This form comes from applying the rank-$k$ dense rate to a problem restricted to $s_U$ coordinates, with a $\log d$ price for selection. We will state explicitly which covariance conditions it requires. We expect a counterpart of Kumar and Sarkar's condition that noise off the support not be amplified faster than signal, and we will test whether the structured-noise counterexamples of Kumar et al. violate it.

The empirical part implements the estimator, its ablations, and the baselines below in one codebase with a shared data loader, so that each streaming method sees the same sample order.

Baselines

The naive reference is diagonal thresholding followed by ordinary top-$k$ PCA on the selected features. This is what practitioners do. It is strong in the spiked-identity model and cheap. It will be given the same $r$ and the same total number of samples. Beating it only on the spiked-identity benchmark would mean little. The proposal must win on the structured-noise and multi-spike covariances where Combinatorial Sparse PCA Beyond the Spiked Identity Model shows it selects no correct coordinates.

The strongest existing statistical method for rank-$k$ sparse subspaces is Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time. It runs an early-stopped convex relaxation and then a truncated orthogonal power iteration, and is minimax-optimal under general sub-Gaussian covariance. On its synthetic small-eigengap setting it reports a subspace error of 0.32 versus 1.15 for the truncated power method. We will reproduce that setting exactly. Its batch memory makes it feasible only at moderate $d$, so we compare there. Beating it means matching its error within statistical noise while using $O(dk')$ rather than $O(d^2)$ memory and a single pass. We do not claim to beat its error. Matching it in one pass is the claim, and worse-but-close is an honest possible outcome.

The convex joint-support baseline is Fantope Projection and Selection. It solves an entrywise-penalized problem over the convex hull of rank-$k$ projections. We run it on its own $n=100$, $p=200$, $k=5$ shared- and disjoint-support designs, tuning its penalty by the same held-out-variance criterion we use to pick $r$. The file gives no numeric values for these designs (no reported result found on Lacuna for FPS numbers), so we regenerate them. Beating FPS means lower projection Frobenius error on disjoint supports, where its penalty is known to be biased, and parity on shared supports.

The deflation baselines are Generalized and Schur-complement deflation from Deflation Methods for Sparse PCA. Each is paired with thresholded Oja or the restarted truncated power method (RTPM) as the rank-one engine, giving the same total pass budget. On Pit Props, Generalized Deflation reports about 79% explained variance versus about 73.4% for Hotelling. On the gene expression data it reaches 79.6% versus 75.1% by the eighth component. Matching these at equal cardinality is the bar on those small datasets.

The key ablation replaces leverage scores with per-column thresholding of the QR-normalized block Oja iterate, the obvious extension of Kumar and Sarkar. It isolates whether basis-free scoring matters. A second ablation sets $k'=k$ to isolate oversampling.

Why not just…?

Why not just threshold each column of block Oja separately? This is the most likely objection and a real threat, since in easy regimes it may work as well. The argument against it is that QR re-orthonormalization mixes columns arbitrarily from step to step when eigenvalues inside the top-$k$ block are close. An individual column's coordinates then need not be sparse even when the span is. The per-column ablation on clustered-eigenvalue designs settles this. If it matches leverage scores there too, the contribution shrinks to the theory, and we will say so.

Why not just find components one at a time with deflation? Lemma 9 of Combinatorial Sparse PCA Beyond the Spiked Identity Model shows that projecting out a sparse component can leave a dense residual. Mackey's analysis shows that errors in early components also corrupt later ones. Deflation also needs $k$ passes in a stream. The experiment that would show deflation is fine is parity on the multi-spike and disjoint-support designs at equal passes. We run exactly that comparison.

Why not just run diagonal thresholding, or plain block Oja with no sparsity? The first is refuted on structured noise by explicit constructions. The second converges toward noise directions when $p/n$ is bounded away from zero, as the phase-transition results in Information-theoretically optimal sparse PCA imply. We include both anyway, since the size of the gap on real data is itself informative.

Proposed Experiments

The synthetic suite has five parts. It uses the FPS shared/disjoint designs, then scales $p$ to $10^4$ and $10^5$ at fixed $n$. It includes Kumar–Sarkar multi-spike covariances and the structured-noise counterexamples of Kumar et al. It adds a new family with $\lambda_1\approx\dots\approx\lambda_k$ to test the claim that eigenvalue gaps inside the block do not matter. It also includes partially overlapping supports. The metrics are union-support precision and recall, projection Frobenius and squared-sine error against $n$, peak memory, and wall-clock time.

The decisive checks are three. First, error should scale linearly in $s_U\log d/n$ on log-log plots. Second, leverage scores should beat per-column thresholding when the within-block gap is near zero. Third, on disjoint supports, error should match or beat FPS.

The real-data suite has four parts. The NYTimes bag-of-words corpus ($d=20{,}000$) is scored by topic coherence (normalized pointwise mutual information) and explained variance. The Arcene and Dorothea covariances from Efficient Sparse PCA via Block-Diagonalization, with up to $10^5$ features, test scale where convex methods cannot run. The Leukemia expression data (3,051 genes, $k=30$) is compared to Globally Sparse Probabilistic PCA on variance retained per selected gene. Pit Props and the cell-nuclei gene data serve as sanity checks against the deflation numbers above.

The proposal fails if leverage-score thresholding loses to diagonal thresholding on the structured-noise designs. It also fails if it cannot come within statistical noise of Tighten after Relax at the dimensions where both run.