  We study a practical algorithm for sparse principal component analysis (PCA)
of incomplete and noisy data. Our algorithm is based on the semidefinite
program (SDP) relaxation of the non-convex $l_1$-regularized PCA problem. We
provide theoretical and experimental evidence that SDP enables us to exactly
recover the true support of the sparse leading eigenvector of the unknown true
matrix, despite only observing an incomplete (missing uniformly at random) and
noisy version of it. We derive sufficient conditions for exact recovery, which
involve matrix incoherence, the spectral gap between the largest and
second-largest eigenvalues, the observation probability and the noise variance.
We validate our theoretical results with incomplete synthetic data, and show
encouraging and meaningful results on a gene expression dataset.

Machine Learning;Machine Learning