Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming

Abstract

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.

accepted to IEEE Transactions on Information Theory, 2015

References in corpus (3)

• High Dimensional Statistical Inference and Random Matrices
• Sketching Sparse Matrices
• Hanson-Wright inequality and sub-gaussian concentration

Cited by in corpus (7)

• Compressive Phase Retrieval via Generalized Approximate Message Passing
• The local convexity of solving systems of quadratic equations
• Channel Vector Subspace Estimation from Low-Dimensional Projections
• Regularization-free estimation in trace regression with symmetric positive semidefinite matrices
• Effective Data-aware Covariance Estimator from Compressed Data
• Proximal linearized iteratively reweighted least squares for a class of nonconvex and nonsmooth problems
• Sequential Sensing with Model Mismatch