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

Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity

ICML 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Sparse and robust PCA

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.

Proposes a column-thresholding polynomial-time estimator for single-spiked sparse PCA needing only Ω(k log p) samples when signal strength λ=Ω(||v||_inf^-1), and a two-stage method combining it with truncated power iteration that attains minimax statistical error.

Problem

Sparse PCA in the single-spiked covariance model: polynomial-time methods need Ω(k^2) samples to recover a k-sparse unit spike, while information-theoretically Ω(k log p) suffices.

Approach

Instead of diagonal thresholding, select the support as the top-k entries of the column of the sample covariance indexed by the largest diagonal entry, which yields a larger statistical gap and hence lower sample complexity under a signal-strength condition λ=Ω(||v||_inf^-1); then refine with truncated power iteration.

Key results

• Thresholding algorithm requires n >= C k log p samples to achieve dist(v, v0) <= gamma with probability 1-5p^-1 when lambda >= C1 ||v||_inf^-1.
• Two-stage algorithm achieves statistical error O(sqrt(k log p / n)), the minimax optimal rate, with linear optimization error decay.
• In the three-peak experiment (p=2000, n=1000, lambda=8), the proposed method attains error 0.1907 and F-score 0.8325 versus 0.6283/0.4804 for DT and 0.2248/0.8038 for Soft-CT.

Measured effects reported in the paper

Surprising findings

• Diagonal thresholding cannot exploit the constant-order ||v||_inf condition and remains fundamentally limited under the same assumption.

Limitations

• Requires signal strength condition lambda = Omega(||v||_inf^-1), so the Omega(k log p) rate is not unconditional; planted-clique reductions suggest no poly-time method without such assumptions.
• Support recovery consistency not established.
• Optimality of the signal strength condition is unknown.

Experimental setup

Datasets: synthetic single-spiked covariance data three-peak synthetic data (Johnstone & Lu, 2009)

Benchmarks: synthetic single-spiked covariance experiments three-peak experiment

Metrics: estimation error dist(v, v_hat) F-score computational time iterations

Baselines: Diagonal thresholding (DT) Soft covariance thresholding (Soft-CT) Hard covariance thresholding (Hard-CT)

Builds on: diagonal thresholding truncated power method covariance thresholding

Closest papers by meaning

• The Complexity of Sparse Tensor PCA (NeurIPS 2021 · similarity 0.92)
• A Kernel Random Matrix-Based Approach for Sparse PCA (ICLR 2019 · similarity 0.92)
• Combinatorial Sparse PCA Beyond the Spiked Identity Model (ICML 2026 · similarity 0.92)
• Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.91)
• Support Recovery in Sparse PCA with Incomplete Data (NeurIPS 2022 · similarity 0.91)
• Oja's Algorithm for Streaming Sparse PCA (NeurIPS 2024 · similarity 0.89)