Nous considérons le problème de l'apprentissage d'un graphe modélisant les relations statistiques de $d$ variables à partir d'un $n$-échantillon $\mathbf{X} \in \mathbb{R}^{n \times d}$.
Les approches classiques consistent à rechercher une matrice de précision $\boldsymbol\Theta$ représentative d'un modèle graphique gaussien expliquant correctement les relations entre les variables.
Cependant, la plupart des estimateurs basés sur le maximum de vraisemblance nécessitent généralement de stocker les $d^{2}$ valeurs de la matrice de covariance empirique, ce qui peut devenir problématique en grande dimension.
Ici, nous adoptons un point de vue ``compressif" et estimons une matrice $\boldsymbol\Theta$ parcimonieuse à partir d'un \emph{sketch} des données, c'est-à-dire un vecteur de faible dimension $m \ll d^{2}$ conçu à partir de $\mathbf{X}$ via des \textit{features} aléatoires non-linéaires.
Sous certaines hypothèses sur le spectre de $\boldsymbol\Theta$ (ou son conditionnement), nous montrons qu'il est possible de l'estimer à partir d'un sketch de taille $m=\Omega\left((d+2k)\log(d)\right)$ où $k$ est le nombre maximal d'arêtes du graphe sous-jacent.
Nous proposons une reconstruction pratique de $\boldsymbol\Theta$ à partir du sketch avec un algorithme itératif basé sur le \emph{graphical lasso} vu comme un débruiteur. Nous avons comparé notre approche avec le \emph{graphical lasso} sur des ensembles de données synthétiques, démontrant ses performances favorables même lorsque l'ensemble de données est compressé.