Search for: All records

We study learning the directed acyclic graph (DAG) for linear structural equation models (SEMs) when the causal structure is a polytree. Under Gaussian polytree models, we derive sufficient sample-size conditions under which the Chow–Liu algorithm exactly recovers both the skeleton and the equivalence class (CPDAG). Matching information-theoretic lower bounds provide necessary conditions, yielding sharp characterizations of problem difficulty. We further analyze inverse correlation matrix estimation with error bounds depending on dimension and the number of v-structures, and extend to group linear polytrees. Comprehensive simulations and benchmark experiments demonstrate robustness when true graphs are only approximately polytrees. 

Techniques of matrix completion aim to impute a large portion of missing entries in a data matrix through a small portion of observed ones. In practice, prior information and special structures are usually employed in order to improve the accuracy of matrix completion. In this paper, we propose a unified nonconvex optimization framework for matrix completion with linearly parameterized factors. In particular, by introducing a condition referred to as Correlated Parametric Factorization, we conduct a unified geometric analysis for the nonconvex objective by establishing uniform upper bounds for low-rank estimation resulting from any local minimizer. Perhaps surprisingly, the condition of Correlated Parametric Factorization holds for important examples including subspace-constrained matrix completion and skew-symmetric matrix completion. The effectiveness of our unified nonconvex optimization method is also empirically illustrated by extensive numerical simulations.