Tata Institute of Fundamental Research

Recovering Causality Graphs from Time Series Data

STCS Colloquium
Speaker: Ravi R. Mazumdar (University Research Chair Professor Dept. of Electrical and Computer Engineering University of Waterloo, Canada)
Organiser: Sandeep K Juneja
Date: Friday, 26 Apr 2019, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  Abstract: Suppose we have N time series available where one time-series could be causally dependent on others. For example, such dependence can be found in economic data or weather data. The goal is to recover the directed causality graph that links these time series.
As is well known causality and correlation are not the same and thus one of the important questions is how to address this issue. There are several frameworks such as directed information, the notion of Granger causality, etc. However working with directed information requires too much a priori knowledge about the structure of the time series that is unavailable.
In this talk I will show how the notion of Granger causality can be tied to Wiener filtering that allows us to recover a directed random graph whose edges are represented by the innovations filters. This approach as well as the directed information approach assuming Gaussianity are however quite computationally intensive. To address this issue we show how it is possible to consider a sparse problem based on a mixed L1 - H1 norm, a generalized GLASSO approach that takes into account the temporal dependencies that leads to an approach for selecting edges in a directed graph characterized by complex polynomials. This results in a convex optimization problem and modern techniques such as ADMM are well suited to such problems.
We then discuss the sparsification problem associated with Granger causality graphs when local neighbourhoods are used. The basic issue is to find the sub-graph of the causality graph that is closest to the original in terms of a suitable norm. In this context we study both the l2 as well as the graph support recovery problem subject to sparsity constraints [jointly with Syamantak Dattagupta (Morgan Stanley) and Ryan Kinnear (Waterloo)].
Bio: The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD under A. V. Balakrishnan at UCLA in 1983.
He is currently a University Research Chair Professor in the Dept. of ECE at the University of Waterloo, Ont., Canada where he has been since September 2004. Prior to this he was Professor of ECE at Purdue University, West Lafayette, USA. He is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay. He is a Fellow of the IEEE and the Royal Statistical Society. He is a recipient of the Best Paper Awards at INFOCOM 2006, the International Teletraffic Congress 2015, Performance 2015, and was runner-up for the Best Paper Award at INFOCOM 1998.
His research interests are in complex networks, stochastic analysis, and randomized algorithms.