Variable selection in high-dimensional linear models: partially faithful distributions and the pc-simple algorithm

摘要

We consider variable selection in high-dimensional linear models where the number of covari-nates greatly exceeds the sample size. We introduce the new concept of partial faithfulness andnuse it to infer associations between the covariates and the response. Under partial faithfulness,nwe develop a simplified version of the PC algorithm (Spirtes et al., 2000), which is computation-nally feasible even with thousands of covariates and provides consistent variable selection undernconditions on the random design matrix that are of a different nature than coherence condi-ntions for penalty-based approaches like the lasso. Simulations and application to real data shownthat our method is competitive compared to penalty-based approaches. We provide an efficientnimplementation of the algorithm in the R-package pcalg.