Characterization and Inference of Graph Diffusion Processes From Observations of Stationary Signals

被引:97
作者
Pasdeloup, Bastien [1 ]
Gripon, Vincent [1 ]
Mercier, Gregoire [1 ]
Pastor, Dominique [1 ]
Rabbat, Michael G. [2 ]
机构
[1] Telecom Bretagne, Lab STICC, CNRS, UMR, F-29280 Plouzane, France
[2] McGill Univ, Dept Elect & Comp Engn, Montreal, PQ H3A 0E9, Canada
来源
IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS | 2018年 / 4卷 / 03期
基金
欧洲研究理事会; 加拿大自然科学与工程研究理事会;
关键词
Graph signal processing; graph inference; stationary signals; COVARIANCE; LASSO; VARIABLES; INSIGHTS; ROOTS;
D O I
10.1109/TSIPN.2017.2742940
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
Many tools from the field of graph signal processing exploit knowledge of the underlying graph's structure (e.g., as encoded in the Laplacian matrix) to process signals on the graph. Therefore, in the case when no graph is available, graph signal processing tools cannot be used anymore. Researchers have proposed approaches to infer a graph topology from observations of signals on its vertices. Since the problem is ill-posed, these approaches make assumptions, such as smoothness of the signals on the graph, or sparsity priors. In this paper, we propose a characterization of the space of valid graphs, in the sense that they can explain stationary signals. To simplify the exposition in this paper, we focus here on the case where signals were i.i.d. at some point back in time and were observed after diffusion on a graph. We show that the set of graphs verifying this assumption has a strong connection with the eigenvectors of the covariance matrix, and forms a convex set. Along with a theoretical study in which these eigenvectors are assumed to be known, we consider the practical case when the observations are noisy, and experimentally observe how fast the set of valid graphs converges to the set obtained when the exact eigenvectors are known, as the number of observations grows. To illustrate how this characterization can be used for graph recovery, we present two methods for selecting a particular point in this set under chosen criteria, namely graph simplicity and sparsity. Additionally, we introduce a measure to evaluate how much a graph is adapted to signals under a stationarity assumption. Finally, we evaluate how state-of-the-art methods relate to this framework through experiments on a dataset of temperatures.
引用
收藏
页码:481 / 496
页数:16
相关论文
共 63 条
[1]   A Spectral Graph Uncertainty Principle [J].
Agaskar, Ameya ;
Lu, Yue M. .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (07) :4338-4356
[2]   On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems [J].
Amaldi, E ;
Kann, V .
THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :237-260
[3]   ASYMPTOTIC THEORY FOR PRINCIPAL COMPONENT ANALYSIS [J].
ANDERSON, TW .
ANNALS OF MATHEMATICAL STATISTICS, 1963, 34 (01) :122-&
[4]  
[Anonymous], 2015, THESIS ECOLE NORMALE
[5]  
[Anonymous], 1997, Spectral Graph Theory
[6]   COVARIANCE REGULARIZATION BY THRESHOLDING [J].
Bickel, Peter J. ;
Levina, Elizaveta .
ANNALS OF STATISTICS, 2008, 36 (06) :2577-2604
[7]   OPTIMAL RATES OF CONVERGENCE FOR SPARSE COVARIANCE MATRIX ESTIMATION [J].
Cai, T. Tony ;
Zhou, Harrison H. .
ANNALS OF STATISTICS, 2012, 40 (05) :2389-2420
[8]   Adaptive Thresholding for Sparse Covariance Matrix Estimation [J].
Cai, Tony ;
Liu, Weidong .
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 2011, 106 (494) :672-684
[9]   Semi-supervised graph-based hyperspectral image classification [J].
Camps-Valls, Gustavo ;
Bandos, Tatyana V. ;
Zhou, Dengyong .
IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING, 2007, 45 (10) :3044-3054
[10]   Atomic decomposition by basis pursuit [J].
Chen, SSB ;
Donoho, DL ;
Saunders, MA .
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1998, 20 (01) :33-61