{"id":"arxiv/2603.02607","url":"https://arxiv.org/abs/2603.02607","tags":["stat.ML","cs.DS","cs.LG","math.OC"],"score":0,"title":"Combinatorial Sparse PCA Beyond the Spiked Identity Model","domain":"stat.ML","source":"arxiv","authors":["Syamantak Kumar","Purnamrita Sarkar","Kevin Tian","Peiyuan Zhang"],"reviews":0,"subject":"stat.ML","summary":"Sparse PCA is one of the most well-studied problems in high-dimensional statistics. In this problem, we are given samples from a distribution with covariance $Σ$, whose top eigenvector $v \\in R^d$ is $s$-sparse. Existing sparse PCA algorithms can be broadly categorized into (1) combinatorial algorithms (e.g., diagonal or elementwise covariance thresholding) and (2) SDP-based algorithms. While combinatorial algorithms are much simpler, they are typically only analyzed under the spiked identity model (where $Σ= I_d + γvv^\\top$ for some $γ> 0$), whereas SDP-based algorithms require no…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-03-03","reactions":{}}