# Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming

arXiv: https://arxiv.org/abs/1310.0807 · HTML: https://mlsanity.com/paper/1310.0807/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2013.

## Built on by (most cited first, 20 of 20)

- [Flat minima generalize for low-rank matrix recovery](https://mlsanity.com/paper/2203.03756/) (2022)
- [Sensing Theorems for Unsupervised Learning in Linear Inverse Problems](https://mlsanity.com/paper/2203.12513/) (2022)
- [Unsupervised Learning From Incomplete Measurements for Inverse Problems](https://mlsanity.com/paper/2201.12151/) (2022)
- [Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent](https://mlsanity.com/paper/2105.03678/) (2021)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning](https://mlsanity.com/paper/2309.04626/) (2023)
- [Optimal sparse phase retrieval via a quasi-Bayesian approach](https://mlsanity.com/paper/2504.09509/) (2025)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [ROP inception: signal estimation with quadratic random sketching](https://mlsanity.com/paper/2205.08225/) (2022)
- [Learning the Structure of Large Networked Systems Obeying Conservation Laws](https://mlsanity.com/paper/2206.07083/) (2022)
- [Compressive Recovery of Sparse Precision Matrices](https://mlsanity.com/paper/2311.04673/) (2023)
- [Acceleration and Implicit Regularization in Gaussian Phase Retrieval](https://mlsanity.com/paper/2311.12888/) (2023)
- [A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval](https://mlsanity.com/paper/2409.04733/) (2024)
- [Convex Latent Effect Logit Model via Sparse and Low-rank Decomposition](https://mlsanity.com/paper/2108.09859/) (2021)
- [Dictionary Learning: The Complexity of Learning Sparse Superposed Features with Feedback](https://mlsanity.com/paper/2502.05407/) (2025)
- [AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimization](https://mlsanity.com/paper/2504.14741/) (2025)
- [A Smoothing Newton Method for Rank-one Matrix Recovery](https://mlsanity.com/paper/2507.23017/) (2025)
- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)
- [Learning to reconstruct from saturated data: audio declipping and high-dynamic range imaging](https://mlsanity.com/paper/2602.22279/) (2026)
- [Random features for Grassmannian kernel approximation with bounded rank-one projections](https://mlsanity.com/paper/2608.04227/) (2026)

## Abstract (arXiv)

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-ℓ2/ℓ1), as well as the conventional RIP-ℓ2/ℓ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.