Metadata only
Date
2005Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
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.
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(na) for any 0 < a < 1. 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. Show more
Publication status
publishedJournal / series
Research reportVolume
Publisher
Seminar für Statistik, Eidgenössische Technische Hochschule (ETH)Organisational unit
03502 - Bühlmann, Peter L. / Bühlmann, Peter L.
More
Show all metadata
ETH Bibliography
yes
Altmetrics