  Covariance matrix estimation techniques require high acquisition costs that
challenge the sampling systems' storing and transmission capabilities. For this
reason, various acquisition approaches have been developed to simultaneously
sense and compress the relevant information of the signal using random
projections. However, estimating the covariance matrix from the random
projections is an ill-posed problem that requires further information about the
data, such as sparsity, low rank, or stationary behavior. Furthermore, this
approach fails using high compression ratios. Therefore, this paper proposes an
algorithm based on the projected gradient method to recover a low-rank or
Toeplitz approximation of the covariance matrix. The proposed algorithm divides
the data into subsets projected onto different subspaces, assuming that each
subset contains an approximation of the signal statistics, improving the
inverse problem's condition. The error induced by this assumption is
analytically derived along with the convergence guarantees of the proposed
method. Extensive simulations show that the proposed algorithm can effectively
recover the covariance matrix of hyperspectral images with high compression
ratios (8-15% approx) in noisy scenarios. Additionally, simulations and
theoretical results show that filtering the gradient reduces the estimator's
error recovering up to twice the number of eigenvectors.
