Support Recovery in Sparse PCA with Incomplete Data
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.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Relaxed Sparsest-Permutation Formulation for Causal Discovery at Scale
Despite the growing availability of large datasets, causal structure learning remains computationally prohibitive at scale. We revisit sparsest-permutation learning for linear structural equation models and show that exa…
Support Recovery in Sparse PCA with Non-Random Missing Data
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 pro…
Dictionary and Image Recovery from Incomplete and Random Measurements
This paper tackles algorithmic and theoretical aspects of dictionary learning from incomplete and random block-wise image measurements and the performance of the adaptive dictionary for sparse image recovery. This proble…
compressed sensingDictionary LearningDiversityNormalized Iterative Hard Thresholding for Tensor Recovery
Low-rank recovery builds upon ideas from the theory of compressive sensing, which predicts that sparse signals can be accurately reconstructed from incomplete measurements. Iterative thresholding-type algorithms-particul…
Compressive SensingIterative Regularization with k-support Norm: An Important Complement to Sparse Recovery
Sparse recovery is ubiquitous in machine learning and signal processing. Due to the NP-hard nature of sparse recovery, existing methods are known to suffer either from restrictive (or even unknown) applicability conditio…