OGM: Online Gaussian Graphical Models on the Fly

Abstract

Gaussian Graphical Model is widely used to understand the dependencies between variables from high-dimensional data and can enable a wide range of applications such as principal component analysis, discriminant analysis, and canonical analysis. With respect to the streaming nature of big data, we study a novel Online Gaussian Graphical Model (OGM) that can estimate the inverse covariance matrix over the high-dimensional streaming data, in this paper. Specifically, given a small number of samples to initialize the learning process, OGM first estimates a low-rank estimation of inverse covariance matrix; then, when each individual new sample arrives, it updates the estimation of inverse covariance matrix using a low-complexity updating rule, without using the past data and matrix inverse. The significant edges of Gaussian graphical models can be discovered through thresholding the inverse covariance matrices. Theoretical analysis shows the convergence rate of OGM to the true parameters is guaranteed under Bernstein-style with mild conditions. We evaluate OGM using extensive experiments. The evaluation results backup our theory.

Department(s)

Computer Science

Comments

This work was supported by the National Key Research and Development Program of China (2018YFE0126000), the National Natural Science Foundation of China (NSFC) (No. 61972050), the Beijing Natural Science Foundation (No. L191012) and the 111 Project (No. B08004).

Keywords and Phrases

Advanced Analytics; Gaussian Graphical Models; Online Learning over Streaming Data

International Standard Serial Number (ISSN)

1573-7497; 0924-669X

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2022 Springer, All rights reserved.

Publication Date

01 Feb 2022

Share

 
COinS