  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.
