  In this article, the optimal sample complexity of learning the underlying
interactions or dependencies of a Linear Dynamical System (LDS) over a Directed
Acyclic Graph (DAG) is studied. We call such a DAG underlying an LDS as
dynamical DAG (DDAG). In particular, we consider a DDAG where the nodal
dynamics are driven by unobserved exogenous noise sources that are wide-sense
stationary (WSS) in time but are mutually uncorrelated, and have the same
{power spectral density (PSD)}. Inspired by the static DAG setting, a metric
and an algorithm based on the PSD matrix of the observed time series are
proposed to reconstruct the DDAG. It is shown that the optimal sample
complexity (or length of state trajectory) needed to learn the DDAG is
$n=\Theta(q\log(p/q))$, where $p$ is the number of nodes and $q$ is the maximum
number of parents per node. To prove the sample complexity upper bound, a
concentration bound for the PSD estimation is derived, under two different
sampling strategies. A matching min-max lower bound using generalized Fano's
inequality also is provided, thus showing the order optimality of the proposed
algorithm.
