Papers › Compressive Recovery of Sparse Precision Matrices

Compressive Recovery of Sparse Precision Matrices

8 Nov 2023arXiv:2311.04673archive 2025-07-28

Titouan Vayer, Etienne Lasalle, Rémi Gribonval, Paulo Gonçalves

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 Θ representative of a Gaussian graphical model that adequately explains the data. However, most maximum likelihood-based estimators usually require storing the d² 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 Θ from a sketch of the data, i.e. a low-dimensional vector of size m ≪d² carefully designed from X using non-linear random features. Under certain assumptions on the spectrum of Θ (or its condition number), we show that it is possible to estimate it from a sketch of size m=Ω((d+2k)log(d)) 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.

PaperPDFCode

Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.

Code

tvayer/compressedprecisionmatrix officialmentioned in papermentioned on GitHubSyntology: not harvested report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

2kcompressed sensing

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections