State covariances of linear systems satisfy certain constraints imposed by the underlying dynamics. These constraints dictate a particular structure of state covariances. However, sample covariances almost always fail to have the required structure. The renewed interest in using state covariances for estimating the power spectra of inputs gives rise to the approximation problem. In this note, the structured covariance least-squares problem is formulated and the Lyapunov-type matricial linear constraint is converted into an equivalent set of trace constraints. Efficient unconstrained maximization methods capable of solving the corresponding dual problem are developed.