A number of problems in statistical signal processing model the data as a Wide-Sense Stationary (WSS) time series, whose power spectrum (or equivalently, the covariance matrix) acts as a sufficient statistic for inferring parameters of interest. The covariance matrix of such data exhibit Toeplitz structure, which can be leveraged to design highly efficient compressive samplers to reduce the dimension of the WSS data, without requiring it to have a sparse representation. Unlike existing results in Compressed Sensing, the goal here is to recover the high dimensional covariance matrix (or infer parameters of interest from it), instead of reconstructing the data itself. Inspired by our past work on nested sensor arrays, I will describe a new sampling techniques, known as the ``Generalized Nested Sample'' (GNS), to acquire compressive measurements in such a way that it becomes possible to perfectly reconstruct the original high dimensional covariance matrix from these compressed sketches. I will focus on lowrank Toeplitz covariance matrices and develop an efficient GNS-based sampler which allows the recovery of a rank-r Toeplitz covariance matrix from a compressed sketch of size $O(√r) x O(√r)$, where the size of the sketch has no dependence on the ambient large dimension N. Our reconstruction technique will use a regularizer-free framework, combined with the ability to extrapolate additional “unobserved” entries of the NxN covariance matrix. The algorithm has significantly lower computational complexity (that does not scale with N) compared to recent nuclear-norm based compressive covariance estimators, and is provably robust against bounded errors. Finally, I will consider the special case of rank-1 and sparse covariance matrices that arise in the important problem of “phase retrieval” in optical imaging. The role of 2nd order difference sets in complex phase retrieval will be demonstrated, inspiring the design of a new class of non-uniform Fourier sampler, that can provably recover a complex signal (upto a global phase ambiguity) from its amplitude measurements with near-minimal number of samples. An interesting connection with the so-called 4N-4 conjecture will also be established, which hypothesizes 4N-4 to be the minimum number of measurements necessary to ensure injectivity in N dimensions for complex phase retrieval. Joint work with Heng Qiao, graduate student, University of California, San Diego.