Timezone: »
Poster
Support Recovery in Sparse PCA with Incomplete Data
Hanbyul Lee · Qifan Song · Jean Honorio
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.
Author Information
Hanbyul Lee (Purdue University)
Qifan Song (Purdue University )
Jean Honorio (Purdue University)
More from the Same Authors
-
2021 Spotlight: Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem »
Adarsh Barik · Jean Honorio -
2022 Poster: Why Do Artificially Generated Data Help Adversarial Robustness »
Yue Xing · Qifan Song · Guang Cheng -
2022 Poster: Phase Transition from Clean Training to Adversarial Training »
Yue Xing · Qifan Song · Guang Cheng -
2021 Poster: Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees »
Gregory Dexter · Kevin Bello · Jean Honorio -
2021 Poster: Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem »
Adarsh Barik · Jean Honorio -
2021 Poster: On the Algorithmic Stability of Adversarial Training »
Yue Xing · Qifan Song · Guang Cheng -
2020 Poster: Efficient Variational Inference for Sparse Deep Learning with Theoretical Guarantee »
Jincheng Bai · Qifan Song · Guang Cheng -
2020 Poster: Fairness constraints can help exact inference in structured prediction »
Kevin Bello · Jean Honorio -
2019 Poster: Learning Bayesian Networks with Low Rank Conditional Probability Tables »
Adarsh Barik · Jean Honorio -
2019 Poster: On the Correctness and Sample Complexity of Inverse Reinforcement Learning »
Abi Komanduru · Jean Honorio -
2019 Poster: Exact inference in structured prediction »
Kevin Bello · Jean Honorio -
2018 Poster: Learning latent variable structured prediction models with Gaussian perturbations »
Kevin Bello · Jean Honorio -
2018 Poster: Information-theoretic Limits for Community Detection in Network Models »
Chuyang Ke · Jean Honorio -
2018 Poster: Computationally and statistically efficient learning of causal Bayes nets using path queries »
Kevin Bello · Jean Honorio -
2017 Poster: Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity »
Asish Ghoshal · Jean Honorio