Second-order statistics of nonlinear dynamical systems can be obtained from experiments or numerical simulations. These statistics are relevant in understanding the fundamental physics, e.g., of fluid flows, and are useful for developing low-complexity models. Such models can be used for the purpose of control design and analysis. In many applications, only certain second-order statistics of a limited number of states are available. Thus, it is of interest to complete partially specified covariance matrices in a way that is consistent with the linearized dynamics. The dynamics impose structural constraints on admissible forcing correlations and state statistics. Solutions to such completion problems can be used to obtain stochastically driven linearized models. Herein, we address the covariance completion problem. We introduce an optimization criterion that combines the nuclear norm together with an entropy functional. The two, together, provide a numerically stable and scalable computational approach which is aimed at low complexity structures for stochastic forcing that can account for the observed statistics. We develop customized algorithms based on alternating direction methods that are well-suited for large scale problems.