Research map / Learning theory and algorithms / Matrix and tensor methods

Efficient Sparse PCA via Block-Diagonalization

ICLR 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Sparse and robust PCA · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Approximates a general covariance matrix by a re-sorted block-diagonal matrix via entrywise thresholding, then solves Sparse PCA per block with any off-the-shelf algorithm and maps the best block solution back, giving speedups with an additive error linear in the approximation.

Problem

Sparse PCA is NP-hard and exact methods (e.g., Branch-and-Bound) require exponential runtime, while polynomial approximations trade off solution quality and efficiency on large covariance matrices.

Approach

Threshold the input covariance matrix at epsilon, group indices connected by nonzero entries into blocks (via DFS), solve Sparse PCA per block with any existing algorithm, and reconstruct the best block solution in the original coordinates; the paper proves the optimal sparse solution of a block-diagonal matrix lies within a single block, and gives a binary-search rule for choosing epsilon.

Key results

• Integrated with Branch-and-Bound, the framework achieves an average speedup of 100.50 with an average approximation error of 0.61% across datasets (k=2,5,10,15).
• Integrated with Chan's algorithm on larger datasets (k=200-2000), the average speedup is 6.00 with an average error of -0.91%, i.e., it often finds better solutions than the standalone algorithm.
• In a synthetic example (10 blocks of size 100, k=4), runtime drops from over 3600 s to 17 s (speedup ~211) with 0.09% approximation error.

Measured effects reported in the paper

Surprising findings

• On the Chan's algorithm experiments, the framework often finds better objective values than the standalone algorithm (average error -0.91%).
• Speedups are heavily dataset-dependent; LymphomaCov2 shows a 4.82% average error with a 6.95x speedup.

Limitations

• Approximation error is linear in the thresholding error, so accuracy can degrade when the threshold is large or the matrix is not nearly block-diagonal (e.g., LymphomaCov2 at 4.82% error).
• Theoretical guarantees for the statistical model require sub-Gaussian noise and block-size assumptions; the practical binary-search method is only a heuristic in terms of approximation quality.
• Only addresses the single-component Sparse PCA problem; multiple principal components are left to future work.

Experimental setup

Datasets: CovColon LymphomaCov1 Reddit1500 Reddit2000 LeukemiaCov LymphomaCov2 ProstateCov ArceneCov DorotheaCov GLI85Cov GLABRA180Cov

Benchmarks: CovColon LymphomaCov1 Reddit1500 Reddit2000 LeukemiaCov LymphomaCov2 ProstateCov ArceneCov GLI85Cov GLABRA180Cov DorotheaCov

Metrics: speedup factor approximation error (%)

Baselines: Branch-and-Bound Chan's algorithm

Builds on: Branch-and-Bound Chan's algorithm

Closest papers by meaning

• Upper bounds for Model-Free Row-Sparse Principal Component Analysis (ICML 2020 · similarity 0.92)
• A Kernel Random Matrix-Based Approach for Sparse PCA (ICLR 2019 · similarity 0.91)
• Support Recovery in Sparse PCA with Incomplete Data (NeurIPS 2022 · similarity 0.91)
• The Complexity of Sparse Tensor PCA (NeurIPS 2021 · similarity 0.91)
• Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.91)
• Oja's Algorithm for Streaming Sparse PCA (NeurIPS 2024 · similarity 0.90)