Robust and universal covariance estimation from quadratic measurements via convex programming

Yuxin Chen, Yuejie Chi, Andrea J. Goldsmith

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

This paper considers the problem of recovering the covariance matrix of a stream of high-dimensional data instances from a minimal number of stored measurements. We develop a quadratic random sampling method based on rank-one measurements of the covariance matrix, which serves as an efficient covariance sketching scheme for processing data streams. This also allows modeling of phaseless measurements that arise in high-frequency wireless communication and signal processing applications. We propose to recover the covariance matrix from the above quadratic measurements via convex relaxation with respect to the presumed parsimonious covariance structure. We show that in the absence of noise, exact and universal recovery of low-rank or Toeplitz low-rank covariance matrices can be achieved as soon as the number of stored measurements exceeds the fundamental sampling limit. The convex programs are also robust to noise and imperfect structural assumptions. Our analysis is established upon a novel notion called the mixed-norm restricted isometry property (RIP- ℓ2/ℓ1), as well as the conventional RIP-ℓ2/ℓ2 for near-isotropic and bounded measurements. Our results improve upon best-known phase retrieval performance guarantees with a significantly simpler approach. Numerical results are provided to demonstrate the practical applicability of our technique.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2017-2021
Number of pages5
ISBN (Print)9781479951864
DOIs
StatePublished - 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI
Period6/29/147/4/14

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Applied Mathematics
  • Modeling and Simulation

Keywords

  • convex programming
  • covariance estimation
  • phaseless measurements
  • quadratic measurements
  • sketching

Fingerprint

Dive into the research topics of 'Robust and universal covariance estimation from quadratic measurements via convex programming'. Together they form a unique fingerprint.

Cite this