Learning Time-Varying Graphs from Online Data
  This work proposes an algorithmic framework to learn time-varying graphs from
online data. The generality offered by the framework renders it
model-independent, i.e., it can be theoretically analyzed in its abstract
formulation and then instantiated under a variety of model-dependent graph
learning problems. This is possible by phrasing (time-varying) graph learning
as a composite optimization problem, where different functions regulate
different desiderata, e.g., data fidelity, sparsity or smoothness. Instrumental
for the findings is recognizing that the dependence of the majority (if not
all) data-driven graph learning algorithms on the data is exerted through the
empirical covariance matrix, representing a sufficient statistic for the
estimation problem. Its user-defined recursive update enables the framework to
work in non-stationary environments, while iterative algorithms building on
novel time-varying optimization tools explicitly take into account the temporal
dynamics, speeding up convergence and implicitly including a
temporal-regularization of the solution. We specialize the framework to three
well-known graph learning models, namely, the Gaussian graphical model (GGM),
the structural equation model (SEM), and the smoothness-based model (SBM),
where we also introduce ad-hoc vectorization schemes for structured matrices
(symmetric, hollows, etc.) which are crucial to perform correct gradient
computations, other than enabling to work in low-dimensional vector spaces and
hence easing storage requirements. After discussing the theoretical guarantees
of the proposed framework, we corroborate it with extensive numerical tests in
synthetic and real data.
