# Compressive Recovery of Sparse Precision Matrices

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 83 references that are in the map.
- First posted on arXiv 8 Nov 2023.

## Builds on (most cited first, 23 of 23)

- [Plug-and-Play Methods Provably Converge with Properly Trained Denoisers](https://mlsanity.com/paper/1905.05406/) (2019)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Proximal Denoiser for Convergent Plug-and-Play Optimization with Nonconvex Regularization](https://mlsanity.com/paper/2201.13256/) (2022)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Network Inference via the Time-Varying Graphical Lasso](https://mlsanity.com/paper/1703.01958/) (2017)
- [Regularization by Denoising via Fixed-Point Projection (RED-PRO)](https://mlsanity.com/paper/2008.00226/) (2020)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [A characterization of proximity operators](https://mlsanity.com/paper/1807.04014/) (2018)
- [Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming](https://mlsanity.com/paper/1310.0807/) (2013)
- [ROP: Matrix recovery via rank-one projections](https://mlsanity.com/paper/1310.5791/) (2013)
- [Random Projections through multiple optical scattering: Approximating kernels at the speed of light](https://mlsanity.com/paper/1510.06664/) (2015)
- [Convergent Bregman Plug-and-Play Image Restoration for Poisson Inverse Problems](https://mlsanity.com/paper/2306.03466/) (2023)
- [Regularizing with Bregman-Moreau envelopes](https://mlsanity.com/paper/1705.06019/) (2017)
- [Compressive Statistical Learning with Random Feature Moments](https://mlsanity.com/paper/1706.07180/) (2017)
- [A Proximal Approach for a Class of Matrix Optimization Problems](https://mlsanity.com/paper/1801.07452/) (2018)
- [Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling](https://mlsanity.com/paper/2004.08085/) (2020)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [Compressed sensing of low-rank plus sparse matrices](https://mlsanity.com/paper/2007.09457/) (2020)
- [Learning partial correlation graphs and graphical models by covariance queries](https://mlsanity.com/paper/1906.09501/) (2019)
- [Regularization-free estimation in trace regression with symmetric positive semidefinite matrices](https://mlsanity.com/paper/1504.06305/) (2015)
- [Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations](https://mlsanity.com/paper/1702.08651/) (2017)
- [Precision Matrix Estimation under the Horseshoe-like Prior-Penalty Dual](https://mlsanity.com/paper/2104.10750/) (2021)
- [ROP inception: signal estimation with quadratic random sketching](https://mlsanity.com/paper/2205.08225/) (2022)

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

- [Random features for Grassmannian kernel approximation with bounded rank-one projections](https://mlsanity.com/paper/2608.04227/) (2026)

## Abstract (arXiv)

We consider the problem of learning a graph modeling the statistical relations of the d variables from a dataset with n samples X ∈ ℝn × d. Standard approaches amount to searching for a precision matrix Theta representative of a Gaussian graphical model that adequately explains the data. However, most maximum likelihood-based estimators usually require storing the d2 values of the empirical covariance matrix, which can become prohibitive in a high-dimensional setting. In this work, we adopt a compressive viewpoint and aim to estimate a sparse Theta from a sketch of the data, i.e. a low-dimensional vector of size m ll d2 carefully designed from X using non-linear random features. Under certain assumptions on the spectrum of Theta (or its condition number), we show that it is possible to estimate it from a sketch of size m=Omegaleft((d+2k)log(d)right) where k is the maximal number of edges of the underlying graph. These information-theoretic guarantees are inspired by compressed sensing theory and involve restricted isometry properties and instance optimal decoders. We investigate the possibility of achieving practical recovery with an iterative algorithm based on the graphical lasso, viewed as a specific denoiser. We compare our approach and graphical lasso on synthetic datasets, demonstrating its favorable performance even when the dataset is compressed.