Seminar Details
2023-02-28 (14h) : Towards Compressive Recovery of Sparse Precision Matrices
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Titouan Vayer (OCKHAM, LIP, ENS Lyon, France)
Abstract :
We consider the problem of learning a graph modeling the statistical relations of the "d" variables of a dataset with "n" samples. 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 to store the "d^2" values of the empirical covariance matrix, which is often too costly in a high-dimensional setting. In this work we adopt a “compressive” viewpoint and look for estimating a sparse Θ from a sketch of the data, i.e. a lowdimensional vector of size "n ≪ d^2" carefully designed from the data using nonlinear random features. Under certain assumptions on the spectrum of Θ, we show that it is theoretically possible to estimate it robustly from a sketch of size "m = O((d + 2k) ln(d))" where "k" is the maximal number of edges of the underlying graph and with an error that decreases in "O(n^{-1/2})". These guarantees are inspired from the compressed sensing theory and involve restricted isometric properties and instance optimal decoders. Our estimator requires solving a non-convex inverse problem and we investigate the possibility of achieving practical recovery by a variant of the Davis-Yin three operator splitting algorithm. We compare our approach with “Graphical LASSO” type estimators on synthetic datasets. Finally, we discuss in a last part the limitations and perspectives of this work, which partially answers some questions but also opens many others.