Estimating high-dimensional directed acyclic graphs with the PC-algorithm

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We consider the PC-algorithm Spirtes et. al. (2000) for estimating the skeleton of a very high-dimensional acyclic directed graph (DAG) with corresponding Gaussian distribution. The PC-algorithm is computationally feasible for sparse problems with many nodes, i.e. variables, and it has the attractive property to automatically achieve high computational efficiency as a function of sparseness of the true underlying DAG. We prove consistency of the algorithm for very high-dimensional, sparse DAGs where the number of nodes is allowed to quickly grow with sample size n, as fast as O(n^a) for any 0<a<infinity. The sparseness assumption is rather minimal requiring only that the neighborhoods in the DAG are of lower order than sample size n. We empirically demonstrate the PC-algorithm for simulated data and argue that the algorithm is rather insensitive to the choice of its single tuning parameter.

Keywords

Statistics Theory, 62H20, 62H12 (Primary), 68Q32 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/130909

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0510436
 http://arxiv.org/abs/math/0510436

Collections

arXiv