Sparse Covariance Estimation from Quadratic Measurements: A Precise Analysis

We study the problem of estimating a high-dimensional sparse covariance matrix, Σ_0, from a finite number of quadratic measurements, i.e., measurements a^T_iΣ_0_ai which are quadratic forms in the measurement vectors a i resulting from the covariance matrix, Σ_0. Such a problem arises in applications where we can only make energy measurements of the underlying random variables. We study a simple LASSO-like convex recovery algorithm which involves a squared 2-norm (to match the covariance estimate to the measurements), plus a regularization term (that penalizes the ℓ_1−norm of the non-diagonal entries of Σ_0 to enforce sparsity). When the measurement vectors are i.i.d. Gaussian, we obtain the precise error performance of the algorithm (accurately determining the estimation error in any metric, e.g., 2-norm, operator norm, etc.) as a function of the number of measurements and the underlying distribution of Σ_0. In particular, in the noiseless case we determine the necessary and sufficient number of measurements required to perfectly recover Σ_0 as a function of its sparsity. Our results rely on a novel comparison lemma which relates a convex optimization problem with "quadratic Gaussian" measurements to one which has i.i.d. Gaussian measurements.