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

Abstract

We consider variable selection in high-dimensional linear models where the\nnumber of covariates greatly exceeds the sample size. We introduce the new\nconcept of partial faithfulness and use it to infer associations between the\ncovariates and the response. Under partial faithfulness, we develop a\nsimplified version of the PC algorithm (Spirtes et al., 2000), the PC-simple\nalgorithm, which is computationally feasible even with thousands of covariates\nand provides consistent variable selection under conditions on the random\ndesign matrix that are of a different nature than coherence conditions for\npenalty-based approaches like the Lasso. Simulations and application to real\ndata show that our method is competitive compared to penalty-based approaches.\nWe provide an efficient implementation of the algorithm in the R-package pcalg.\n