Useful Facts

A.1 Relation of Inverse Covariance Matrix and Partial Correlation For a covariance matrix of joint distribution for variables X,Y, the covariance matrix is The derivation comes from the following: Lemma A.1 (Conditional independence (Adapted from [34])). Notice for arbitrary function f, E[f(X)|Y] = EL[f(X)|φy(Y)] with one-hot encoding of discrete variable Y. Therefore for any feature map we can also get that conditional independence ensures: This thus finishes the proof for Lemma D.4. A.3 Technical Facts for Matrix Concentration We include this covariance concentration result that is adapted from Claim A.2 in [18]: Claim A.2 (covariance concentration for gaussian variables). Let X = [x1,x2, xn]> Rn d where each xi N(0,ΣX). Then for any given matrix B Rd m that is of rank kand is independent of X, with probability at least 1 δ10 over X we have 0.9B>ΣXB 1 n B>X>XB 1.1B>ΣXB. Let X = [x1,x2, xn]> Rn d where each xi is ρ2-sub-gaussian. Then for any given matrix B Rd m that is of rank kand is independent of X, with probability at least 1 δ10 over X we have 0.9B>ΣXB 1 n B>X>XB 1.1B>ΣXB. Let Z Rn k be a matrix with row vectors sampled from i.i.d Gaussian distribution N(0,ΣZ). Let P Rn n be a fixed projection onto a space of dimension d.