Exact and Stable Covariance Estimation from Quadratic Sampling via
  Convex Programming
  Statistical inference and information processing of high-dimensional data
often require efficient and accurate estimation of their second-order
statistics. With rapidly changing data, limited processing power and storage at
the acquisition devices, it is desirable to extract the covariance structure
from a single pass over the data and a small number of stored measurements. In
this paper, we explore a quadratic (or rank-one) measurement model which
imposes minimal memory requirements and low computational complexity during the
sampling process, and is shown to be optimal in preserving various
low-dimensional covariance structures. Specifically, four popular structural
assumptions of covariance matrices, namely low rank, Toeplitz low rank,
sparsity, jointly rank-one and sparse structure, are investigated, while
recovery is achieved via convex relaxation paradigms for the respective
structure.
  The proposed quadratic sampling framework has a variety of potential
applications including streaming data processing, high-frequency wireless
communication, phase space tomography and phase retrieval in optics, and
non-coherent subspace detection. Our method admits universally accurate
covariance estimation in the absence of noise, as soon as the number of
measurements exceeds the information theoretic limits. We also demonstrate the
robustness of this approach against noise and imperfect structural assumptions.
Our analysis is established upon a novel notion called the mixed-norm
restricted isometry property (RIP-$\ell_{2}/\ell_{1}$), as well as the
conventional RIP-$\ell_{2}/\ell_{2}$ for near-isotropic and bounded
measurements. In addition, our results improve upon the best-known phase
retrieval (including both dense and sparse signals) guarantees using PhaseLift
with a significantly simpler approach.
