Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming

Yuxin Chen, Yuejie Chi, Andrea J. Goldsmith

Research output: Contribution to journalArticlepeer-review

136 Scopus citations


Statistical inference and information processing of high-dimensional data often require an 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 noncoherent 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- ℓ21, as well as the conventional RIP- ℓ22 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.

Original languageEnglish (US)
Article number7101247
Pages (from-to)4034-4059
Number of pages26
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 1 2015

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Covariance sketching
  • Energy measurements
  • Low rank
  • Phase retrieval
  • Phase tomography, RIP-'2='1
  • Quadratic measurements
  • Rank-one measurements
  • Sparsity
  • Toeplitz


Dive into the research topics of 'Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming'. Together they form a unique fingerprint.

Cite this