Support Recovery in Sparse PCA with Non-Random Missing Data
This addresses the challenge of sparse PCA with missing data for applications like data analysis and signal processing, but it is incremental as it builds on existing semidefinite relaxation methods with new theoretical conditions.
The paper tackles the problem of recovering the support of the sparse leading eigenvector in sparse PCA with incomplete and noisy data under non-random sampling, showing that under certain conditions, the algorithm achieves high-probability support recovery and outperforms other methods when observed entries have good structural properties.
We analyze a practical algorithm for sparse PCA on incomplete and noisy data under a general non-random sampling scheme. The algorithm is based on a semidefinite relaxation of the $\ell_1$-regularized PCA problem. We provide theoretical justification that under certain conditions, we can recover the support of the sparse leading eigenvector with high probability by obtaining a unique solution. The conditions involve the spectral gap between the largest and second-largest eigenvalues of the true data matrix, the magnitude of the noise, and the structural properties of the observed entries. The concepts of algebraic connectivity and irregularity are used to describe the structural properties of the observed entries. We empirically justify our theorem with synthetic and real data analysis. We also show that our algorithm outperforms several other sparse PCA approaches especially when the observed entries have good structural properties. As a by-product of our analysis, we provide two theorems to handle a deterministic sampling scheme, which can be applied to other matrix-related problems.