Online network change point detection with missing values and temporal dependence
arXiv:2110.06450
Abstract
In this paper we study online change point detection in dynamic networks with time heterogeneous missing pattern within networks and dependence across the time course. The missingness probabilities, the entrywise sparsity of networks, the rank of networks and the jump size in terms of the Frobenius norm, are all allowed to vary as functions of the pre-change sample size. On top of a thorough handling of all the model parameters, we notably allow the edges and missingness to be dependent. To the best of our knowledge, such general framework has not been rigorously nor systematically studied before in the literature. We propose a polynomial time change point detection algorithm, with a version of soft-impute algorithm (e.g. Mazumder et al., 2010; Klopp, 2015) as the imputation sub-routine. Piecing up these standard sub-routines algorithms, we are able to solve a brand new problem with sharp detection delay subject to an overall Type-I error control. Extensive numerical experiments are conducted demonstrating the outstanding performances of our proposed method in practice.
References in corpus (12)
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Changepoint detection for high-dimensional time series with missing data
- A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
- Matrix Completion via Max-Norm Constrained Optimization
- Change-Point Estimation in High-Dimensional Markov Random Field Models
- ecp: An R Package for Nonparametric Multiple Change Point Analysis of Multivariate Data
- Spectral Clustering for Multiple Sparse Networks: I
- Sequential Change-point Detection for High-dimensional and non-Euclidean Data
- Sequential change-point detection in high-dimensional Gaussian graphical models
- A review on minimax rates in change point detection and localisation
- Optimal network online change point localisation
- Change-Point Detection in Dynamic Networks with Missing Links