Prediction of Partially Observed Dynamical Processes Over Networks via Dictionary Learning

被引:27
作者
Forero, Pedro A. [1 ]
Rajawat, Ketan [2 ]
Giannakis, Georgios B. [3 ]
机构
[1] SPAWAR Syst Ctr Pacific, Maritime Syst Div, San Diego, CA 92152 USA
[2] Indian Inst Technol, Dept Elect Engn, Kanpur 208016, Uttar Pradesh, India
[3] Univ Minnesota, Dept Elect & Comp Engn, Minneapolis, MN 55455 USA
基金
美国国家科学基金会;
关键词
Dictionary learning; estimation over networks; online learning; semi-supervised learning; MATRIX-FACTORIZATION; SPARSE SIGNALS; REGULARIZATION; SELECTION;
D O I
10.1109/TSP.2014.2325798
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
080906 [电磁信息功能材料与结构]; 082806 [农业信息与电气工程];
摘要
Prediction of dynamical processes evolving over network graphs is a basic task encountered in various areas of science and engineering. The prediction challenge is exacerbated when only partial network observations are available, that is when only measurements from a subset of nodes are available. To tackle this challenge, the present work introduces a joint topology- and data-driven approach for network-wide prediction able to handle partially observed network data. First, the known network structure and historical data are leveraged to design a dictionary for representing the network process. The novel approach draws from semi-supervised learning to enable learning the dictionary with only partial network observations. Once the dictionary is learned, network-wide prediction becomes possible via a regularized least-squares estimate which exploits the parsimony encapsulated in the design of the dictionary. Second, an online network-wide prediction algorithm is developed to jointly extrapolate the process over the network and update the dictionary accordingly. This algorithm is able to handle large training datasets at a fixed computational cost. More important, the online algorithm takes into account the temporal correlation of the underlying process, and thereby improves prediction accuracy. The performance of the novel algorithms is illustrated for prediction of real Internet traffic. There, the proposed approaches are shown to outperform competitive alternatives.
引用
收藏
页码:3305 / 3320
页数:16
相关论文
共 43 条
[1]
Abrams Z, 2004, IPSN '04: THIRD INTERNATIONAL SYMPOSIUM ON INFORMATION PROCESSING IN SENSOR NETWORKS, P424
[2]
On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them [J].
Aharon, Michal ;
Elad, Michael ;
Bruckstein, Alfred M. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 416 (01) :48-67
[3]
Sparse and Redundant Modeling of Image Content Using an Image-Signature-Dictionary [J].
Aharon, Michal ;
Elad, Michael .
SIAM JOURNAL ON IMAGING SCIENCES, 2008, 1 (03) :228-247
[4]
Online Adaptive Estimation of Sparse Signals: Where RLS Meets the l1-Norm [J].
Angelosante, Daniele ;
Bazerque, Juan Andres ;
Giannakis, Georgios B. .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2010, 58 (07) :3436-3447
[5]
[Anonymous], 2009, NONLINEAR PROGRAMMIN
[6]
[Anonymous], 2008, P ADV NEURAL INFORM
[7]
Argyriou A., 2005, Advances in Neural Information Processing Systems, P67
[8]
Barrat A., 2008, Dynamical Processes on Complex Networks
[9]
Belkin M, 2006, J MACH LEARN RES, V7, P2399
[10]
Matrix Completion With Noise [J].
Candes, Emmanuel J. ;
Plan, Yaniv .
PROCEEDINGS OF THE IEEE, 2010, 98 (06) :925-936