Statistical inference and information processing of high-dimensional data often require efficient estimation of their second-order statistics. With rapidly changing data, limited processing power and storage at the data acquisition devices, it is desirable to extract the covariance structure from minimal storage. In this paper, we explore a quadratic measurement model which imposes a minimal memory requirement and low computational complexity during the sampling process, and is shown to be optimal in preserving low-dimensional covariance structures. We show that a covariance matrix under  appropriate structural assumptions can be perfectly recovered from a near-optimal number of sub-Gaussian quadratic measurements, via efficient convex relaxation algorithms for respective structure.