6533b825fe1ef96bd12832bf
RESEARCH PRODUCT
Online Topology Identification from Vector Autoregressive Time Series
Daniel RomeroBakht ZamanLuis Miguel Lopez RamosBaltasar Beferull-lozanosubject
Signal Processing (eess.SP)FOS: Computer and information sciencesTheoretical computer scienceComputer scienceEstimatorMachine Learning (stat.ML)020206 networking & telecommunicationsRegret02 engineering and technologyCausalitySynthetic dataCausality (physics)Autoregressive modelGranger causalityStatistics - Machine LearningSignal ProcessingFOS: Electrical engineering electronic engineering information engineering0202 electrical engineering electronic engineering information engineeringAnomaly detectionElectrical and Electronic EngineeringTime seriesElectrical Engineering and Systems Science - Signal Processingdescription
Causality graphs are routinely estimated in social sciences, natural sciences, and engineering due to their capacity to efficiently represent the spatiotemporal structure of multivariate data sets in a format amenable for human interpretation, forecasting, and anomaly detection. A popular approach to mathematically formalize causality is based on vector autoregressive (VAR) models and constitutes an alternative to the well-known, yet usually intractable, Granger causality. Relying on such a VAR causality notion, this paper develops two algorithms with complementary benefits to track time-varying causality graphs in an online fashion. Their constant complexity per update also renders these algorithms appealing for big-data scenarios. Despite using data sequentially, both algorithms are shown to asymptotically attain the same average performance as a batch estimator which uses the entire data set at once. To this end, sublinear (static) regret bounds are established. Performance is also characterized in time-varying setups by means of dynamic regret analysis. Numerical results with real and synthetic data further support the merits of the proposed algorithms in static and dynamic scenarios.
year | journal | country | edition | language |
---|---|---|---|---|
2019-04-03 |