Novel schemes are developed for linear dimensionality reduction of data vectors whose covariance matrix exhibits sparsity. Two types of sparsity are considered: i) sparsity in the eigenspace of the covariance matrix; or, ii) sparsity in the factors that the covariance matrix is decomposed. Different from existing alternatives, the novel dimensionality-reducing and reconstruction matrices are designed to fully exploit covariance-domain sparsity. They are obtained by solving properly formulated optimization problems using simple coordinate descent iterations. Numerical tests corroborate that the novel algorithms achieve improved reconstruction quality relative to related approaches that do not fully exploit covariance-domain sparsity.