The class of complex random vectors whose covariance matrix is linearly parameterized by a basis of Hermitian Toeplitz (HT) matrices is considered, and the maximum compression ratios that preserve all second-order information are derived - the statistics of the uncompressed vector must be recoverable from a set of linearly compressed observations. This kind of vectors typically arises when sampling wide-sense stationary random processes and features a number of applications in signal and array processing. Explicit guidelines to design optimal and nearly optimal schemes operating both in a periodic and non-periodic fashion are provided by considering two of the most common linear compression schemes: non-uniform sampling and random sampling.