  We consider the problem of learning a graph modeling the statistical
relations of the $d$ variables from 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
\emph{sketch} of the data, i.e. a low-dimensional vector of size $m \ll d^{2}$
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=\Omega\left((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.
