We consider the problem of learning a graph modeling the statistical
relations of the $d$ variables of a dataset with $n$ samples $X \in
\mathbb{R}^{n \times 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 $d^{2}$ 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 d^{2}$
carefully designed from $X$ using nonlinear 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=\Omega((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.

本研究旨在通过对数据的草图进行估计，从而学习一个能够准确解释数据的稀疏图模型，采用了压缩视角和基于图形套索的迭代算法，同时研究了通过合成数据集进行性能对比的可能性。