Tile-Aligned Sparse PCA: Making Interpretable Projections Fast on GPUs

Sparse principal component analysis (sparse PCA) forces each output axis to depend on only a few input features. A component built from 40 genes, rather than a blend of all 20,000, is something a scientist can read. The usual pitch also says that a projection with mostly zero weights should be cheap to compute. On GPUs that second promise tends to fail. Once a projection has many components, each with its own scattered set of features, the weight matrix is only moderately sparse (roughly 80–97% zeros). That is exactly the range where the model-compression literature finds scattered zeros running no faster than, and often slower than, just doing the dense multiplication. The cost of irregular memory reads and index bookkeeping outweighs the arithmetic saved.

This proposal rests on one observation. Interpretability does not care about the order of the features, but the hardware does. We can therefore permute features before fitting so that correlated features sit next to each other, and then require each component's nonzeros to fall in a few dense rectangular tiles of the permuted weight matrix, sized to match GPU matrix-multiply blocks. Each nonzero tile is still readable as "this small group of correlated features drives these components." The projection then runs as a handful of dense tile multiplies instead of a scattered sparse product. The question is what this alignment costs in explained variance and what it buys in wall-clock time, compared against the best way of accelerating ordinary unstructured sparse PCA after the fact.

Core Claim

Relabeling features is free for interpretability. Sparse PCA can therefore adopt the tile-wise structure that made pruned networks fast, without the problem that makes that structure costly for neural weights, where index positions are fixed. We claim two things. First, on high-dimensional data with many components, tile-constrained sparse PCA reaches explained variance within a few percent of unstructured sparse PCA at matched cardinality. Second, its projections run substantially faster than dense projection, faster than cuSPARSE on the unstructured solution, and faster than a Tensor-Core kernel given the unstructured solution after its own reordering. The second comparison is the one that matters.

The prior work motivates this from both sides.

What motivates it. Tile-wise sparsity (Guo et al.) prunes whole rows or columns inside GEMM tiles. It reports a 1.95× speedup on Tensor Cores and 11.6× at 99% sparsity on a V100, but only for network weights whose index positions are fixed. The SMaT kernel (Okanovic et al.) takes a different route: it reorders rows by Jaccard similarity into blocked storage and runs them on Tensor Cores. It beats dense cuBLAS at sparsity as low as 78%, but it can only pack whatever block structure a matrix already happens to have.

What supplies the method. Efficient Sparse PCA via Block-Diagonalization shows that after thresholding and permuting the covariance into blocks, the optimal first sparse component lies inside a single block. It reports a 100.5× CPU speedup over branch-and-bound with 0.61% average error. That result is evidence that restricting supports to correlated groups costs little. It covers only one component and only CPU runtime; we use its permutation idea to lay out tiles for many components on a GPU.

What constrains it. Two lines of work set limits:

  • N:M sparsity (exactly N nonzeros in every M consecutive weights, e.g. 2:4), learned in Zhou et al., is hardware-native. At best it yields 50–75% zeros spread evenly across every window, which is useless for interpretability. The structure we need is block-shaped, not window-shaped.
  • Rigid block patterns hurt accuracy unless patched, as ARMOR does with factorized wrappers and TEW does with 1.5% rescue weights. We test whether the permutation step removes most of that penalty in the PCA setting.

Research Program

Formulation. Let $X \in \mathbb{R}^{n \times d}$ be the data and $\Sigma$ its covariance. Let $P$ be a feature permutation, and let $V \in \mathbb{R}^{d \times r}$ hold the $r$ loading vectors in permuted order. We partition $V$ into tiles of $b$ features by $c$ components, with $b, c \in \{16, 32\}$ to match Tensor-Core fragment and GEMM tile shapes. We then solve

$$\max_{V} \ \mathrm{tr}(V^\top P^\top \Sigma P V) \quad \text{s.t.} \quad V^\top V = I, \quad \#\{\text{nonzero tiles of } V\} \le T,$$

where $T$ is the tile budget. Within an active tile we optionally apply an element-level cardinality cap. The kernel stores such a tile dense, so the reported feature-level support stays small while execution stays regular.

Choosing the permutation. $P$ comes from thresholded-covariance clustering in the style of the block-diagonalization paper. We relax it by packing clusters into tiles of size $b$ and splitting oversized clusters by spectral bisection.

Solver. The solver is a projected block power iteration. Each step multiplies by $\Sigma$, keeps the $T$ tiles with the largest Frobenius norm, and re-orthonormalizes.

What the tile constraint buys and costs. Components that share no tiles are exactly orthogonal, which partly addresses the rank-$r$ deflation problem noted for exact sparse PCA solvers. We do not claim that as a general solution. The main open analysis is the gap between the tile-constrained optimum and the unstructured optimum as a function of how clustered $\Sigma$ is. The block-diagonalization paper already warns that dense, interconnected covariance structure pushes block sizes toward $d$. We will measure the gap directly and relate it to the fraction of covariance mass captured by the tiled layout.

What gets built. We build a fused kernel for $Y = XPV$. It gathers the permuted input columns once, then runs one dense tile multiply per active tile, with asynchronous copies and double buffering following the SMaT recipe. We also build a solver whose inner products use the same kernel, so fitting at large $d$ gets faster as well.

Where this matters. The target regime is where projections are applied repeatedly:

  • very large $n$, as in Sentiment140 (1.6M tweets, about 37k-word vocabulary) and Kosarak (about 900k transactions, about 41k items), used in Sparse Dimensionality Reduction Revisited;
  • per-token reduction of LLM hidden states for monitoring, following the activation-probe setting of Beyond Linear Probes, where every forward pass pays the projection cost.

Baselines

Dense PCA with cuBLAS. This is the do-nothing reference. We take the top $r$ dense components and project with cuBLAS on the same A100, in the same precision, on the same batch shapes. It is the speed bar any sparse method must clear. It is also the interpretability floor, since every feature enters every component. We beat it on speed if our projection has lower latency at tile densities of 10% or below.

Unstructured sparse PCA. We fit a per-component sparse PCA with a greedy solver in the spirit of Moghaddam et al. or the approximate greedy path of d'Aspremont et al., with cardinality matched to ours. For single components, where exact search is feasible, we use block-diagonalized branch-and-bound. That method reports a 100.5× average speedup over plain branch-and-bound at 0.61% average approximation error, and 6.0× over Chan's algorithm. We execute the unstructured solutions two ways.

  • With cuSPARSE, the naive sparse path.
  • With SMaT after Jaccard reordering. This is the strongest runtime competitor. It reports being on average 2.6× faster than DASP, up to 125× faster than cuSPARSE, and faster than cuBLAS from 78% sparsity. Its reordering cost is excluded from timing, because the loadings are static.

Explained variance is compared at equal feature cardinality and equal number of components. Runtime is compared on identical inputs.

Globally sparse PCA with a shared feature set. This variant forces all components onto one shared feature set, as in globally sparse probabilistic PCA (Mattei). It is structurally the easiest to accelerate: gather the chosen columns, then multiply densely.

Downstream clustering. For clustering and feature selection, the strongest reported competitor is SPCA-Net (Tuning-Free Structured Sparse PCA), which reports 59.17% clustering accuracy on Isolet. We run it with its released stage count of 3–5. We beat it if we match its ACC and NMI within noise while projecting faster.

Ablations. Two ablations isolate the key ingredient:

  • Random permutation. Tile-constrained sparse PCA with a random rather than covariance-derived permutation. This tests whether the permutation, not the tile constraint alone, preserves variance.
  • No permutation, no tiling. Our kernel applied to unstructured loadings, which separates the kernel's engineering from the structural constraint.

Why not just…?

Why not just fit ordinary sparse PCA and let SMaT reorder it afterwards? This is the most serious threat, and the proposal is designed to settle it. Reordering can only pack blocks that already exist. Unstructured sparse PCA picks features for variance, not for co-location, so its supports across many components may overlap little. That would leave SMaT tiles mostly padding. We will measure the fill fraction of blocked tiles and the resulting throughput for reordered unstructured solutions. If SMaT on those solutions gets within about 20% of our throughput while keeping more variance, the honest conclusion is that constraining during fitting is unnecessary, and we will report it that way.

Why not just use one shared feature set for all components, gather those columns, and multiply densely? When the shared set is small this is essentially free on hardware and hard to beat. The cost falls on the statistics: every component is forced onto the same features. That loses variance and component-specific meaning whenever different components describe different mechanisms, such as different gene programs. Our method contains this baseline as a single-tile-column special case. The explained-variance-versus-latency frontier will show whether per-component tile freedom is worth anything. If it is not, on a given dataset, we say so.

Why not just threshold dense PCA loadings, or use hardware-native 2:4 sparsity? Thresholding keeps scattered supports, so it inherits the full irregular-memory cost. Classical sparse PCA results summarized in d'Aspremont et al. show it also captures variance poorly. The 2:4 pattern is fast only on Ampere and later GPUs, and caps sparsity at 50%, far too dense for anyone to read. We include thresholding as a baseline, but on structural grounds do not expect it to compete on either axis.

Proposed Experiments

Datasets. We use the 11 covariance benchmarks from the block-diagonalization paper (CovColon, both Lymphoma matrices, LeukemiaCov, ProstateCov, GLI85Cov, GLABRA180Cov, Reddit1500, Reddit2000, ArceneCov, DorotheaCov up to 100,000 features). We add Sentiment140 and Kosarak as large-$n$ projection workloads. We add hidden-state activations of a mid-size open LLM collected on WildGuardMix prompts, a regime where covariance may be densely interconnected and our method should suffer most.

Measurements. For each dataset, number of components $r \in \{8, 64, 256\}$, and cardinality budget, we record:

  • explained variance, adjusted for any non-orthogonality;
  • distinct features used;
  • stability of the support across bootstrap resamples;
  • projection throughput on an A100, plus a V100 run to test portability beyond sparse Tensor Cores;
  • end-to-end fitting time.

Downstream checks. Clustering ACC and NMI on COIL20, Isolet, UMIST and MSTAR compare us with SPCA-Net. On the LLM activations, linear-probe F1 on the reduced coordinates compares with a probe on full activations. We found no reported absolute F1 on Lacuna for the TPC probe baseline, only "up to a 10% accuracy boost over standard linear probes," so we rerun those probes ourselves. On Colon Cancer we check that interpretable signals previously highlighted, such as Myosin and Actin, still appear within active tiles.

Decisive checks. Three results would decide the proposal:

  • On most benchmarks, at matched latency, tile-aligned loadings keep at least 95% of the variance of unstructured sparse PCA while running faster than SMaT on the reordered unstructured solution.
  • The random-permutation ablation loses clearly more variance, which shows the correlation-aware layout is doing the work.
  • On the LLM activations, the variance gap grows as covariance clustering weakens, which maps where the method stops paying off.

If the first check fails against SMaT, the contribution becomes a measured negative result: post-hoc reordering suffices for interpretable projections. That is still a useful thing to know.