Online topology estimation of graph-connected time series is challenging, especially since the causal dependencies in many real-world networks are nonlinear. In this paper, we propose a kernel-based algorithm for graph topology estimation. The algorithm uses a Fourier-based Random feature approximation to tackle the curse of dimensionality associated with the kernel representations. Exploiting the fact that the real-world networks often exhibit sparse topologies, we propose a group lasso based optimization framework, which is solve using an iterative composite objective mirror descent method, yielding an online algorithm with fixed computational complexity per iteration. The experiments conducted on real and synthetic data show that the proposed method outperforms its competitors.
翻译:图形连接时间序列的在线地貌学估计具有挑战性,特别是因为许多现实世界网络的因果关系依赖性不是线性。在本文件中,我们提出一个基于内核的图表地貌估计算法。该算法使用基于Fourier的随机地貌近似法来解决与内核表征相关的维度诅咒。我们利用现实世界网络往往呈现出稀有的地表问题这一事实,提出了一个基于集体的Lasso优化框架,这个框架使用迭接复合目标反射下降法解决了这个问题,产生了一个每个迭代都具有固定计算复杂性的在线算法。对真实和合成数据进行的实验表明,拟议方法优于竞争者。