Testing Causality for High Dimensional Data

Determining causal relationship between high dimensional observations are among the most important tasks in scientific discoveries. In this paper, we revisited the linear trace method, a technique proposed in~citepjanzing2009telling,zscheischler2011testing to infer the causal direction between two random variables of high dimensions. We strengthen the existing results significantly by providing an improved tail analysis in addition to extending the results to nonlinear trace functionals with sharper confidence bounds under certain distributional assumptions. We obtain our results by interpreting the trace estimator in the causal regime as a function over random orthogonal matrices, where the concentration of Lipschitz functions over such space could be applied. We additionally propose a novel ridge-regularized variant of the estimator in citezscheischler2011testing, and give provable bounds relating the ridge-estimated terms to their ground-truth counterparts. We support our theoretical results with encouraging experiments on synthetic datasets, more prominently, under high-dimension low sample size regime.