Search

In many areas such as computational biology, finance or social sciences, knowledge of an underlying graph explaining the interactions between agents is of paramount importance but still challenging. Considering that these interactions may be based on nonlinear relationships adds further complexity to the topology inference problem. Among the latest methods that respond to this need is a topology inference one proposed by the authors, which estimates a possibly directed adjacency matrix in an online manner. Contrasting with previous approaches based on linear models, the considered model is able to explain nonlinear interactions between the agents in a network. The novelty in the considered method is the use of a derivative-reproducing property to enforce network sparsity, while reproducing kernels are used to model the nonlinear interactions. The aim of this paper is to present a thorough convergence analysis of this method. The analysis is proven to be sane both in the mean and mean square sense. In addition, stability conditions are devised to ensure the convergence of the analyzed method., 24 pages, 11 of which of which are supplementary material; 4 figures

Convergence of the diffusion RLS (DRLS) algorithm to steady-state has been extensively studied in the literature, whereas no analysis of its transient convergence behavior has been reported yet. In this letter, we conduct a theoretical analysis of the transient behavior of the DRLS algorithm for cyclostationary colored inputs, in the mean and mean-square error sense. The resulting analytical models allows us to thoroughly investigate the convergence behavior of the algorithm over adaptive networks in such complex scenarios. Simulation results support the accuracy and correctness of the theoretical findings., Comment: 5 pages, 2 figures

In this article we illustrate what the contours of “Cliophysics” are. The term was coined by the “Cliometrics and Complexity” (CAC) team, composed of economists and physicists, and hosted by the Complex Systems Institute of ENS Lyon (IXXI). Cliophysics consists in the application of methodological tools from Complexity and Econophysics to the field of Economic history. More precisely, this new scientific challenge aims at combining Cliometrics, i.e. the application of economic modelling and econometrics to the field of Economic history, together with Complexity analysis and Econophysics. In this article, we highlight how using statistical signal processing, topological analysis and network analysis can enrich Cliometrics. To that end, we present three case studies taken from the research agenda developed within the CAC Team: 1) An original research in Cliophysics involving coïncidence analysis based on symbolic time series, aiming to revisit the classical standards of the link between public debt and economic growth in Economic history; 2) An approach in Cliophysics involving topological representations of asset markets networks, aiming to detect homogeneous eras of international monetary regimes; 3) An approach in Cliophysics involving the segmentation of multivariate time series derived from assets returns, aiming to allow for the identification of the structural breaks in the history of global capital markets. We provide evidence that Cliophysics 1) reveals new stylized facts in Economic history, 2) unveils key moments in the history of capital flows, different from the conventional view, and 3) fills a gap in historical analysis, by focusing on “structure matters in Economic history”.

International audience; Part I of this paper formulated a multitask optimization problem where agents in the network have individual objectives to meet, or individual parameter vectors to estimate, subject to a smoothness condition over the graph. A diffusion strategy was devised that responds to streaming data and employs stochastic approximations in place of actual gradient vectors, which are generally unavailable. The approach relied on minimizing a global cost consisting of the aggregate sum of individual costs regularized by a term that promotes smoothness. We examined the first-order, the second-order, and the fourth-order stability of the multitask learning algorithm. The results identified conditions on the step-size parameter, regularization strength, and data characteristics in order to ensure stability. This Part II examines steady-state performance of the strategy. The results reveal explicitly the influence of the network topology and the regularization strength on the network performance and provide insights into the design of effective multitask strategies for distributed inference over networks.

International audience; Identifying directed connectivity patterns from nodal measurements is an important problem in network analysis. Recent works proposed to leverage the performance and flexibility of strategies operating in reproducing kernel Hilbert spaces (RKHS) to model nonlinear interactions between network agents. Moreover, several applications require online and efficient solutions, which motivated the consideration of distributed adaptive learning strategies inspired by algorithms such as the kernel least mean square (KLMS). Despite showing good performance, a thorough theoretical understanding of the behavior of such algorithms is still missing. This makes applying them in practice challenging, especially because the setup of adaptive algorithms involves additional parameters like the step size and a dictionary of kernel functions. In this paper, we present a convergence analysis of the graph-topology-inference KLMS algorithm. Monte Carlo simulations demonstrate the accuracy of the theoretical models.

International audience; The generalized Hermitian eigendecomposition problem is ubiquitous in signal and machine learning applications. Considering the need of processing streaming data in practice and restrictions of existing methods, this paper is concerned with fast and efficient generalized eigenvectors tracking. We first present a computationally efficient algorithm based on randomization termed alternate-projections randomized eigenvalue decomposition (APR-EVD) to solve a standard eigenvalue problem. By exploiting rank-1 strategy, two online algorithms based on APR-EVD are developed for the dominant generalized eigenvectors extraction. Numerical examples show the practical applicability and efficacy of the proposed online algorithms.

International audience; In many applications, such as brain network connectivity or shopping recommendations, the underlying graph explaining the different interactions between participating agents is unknown. Moreover, many of these interactions may be based on nonlinear relationships, rendering the topology inference problem more complex. This paper presents a new topology inference method that estimates a possibly directed adjacency matrix in an online manner. In contrast to previous approaches which are based on additive models, the proposed model is able to explain general nonlinear interactions between the agents. Partial-derivative-imposed sparsity is implemented, while reproducing kernels are used to model nonlinearities. The impact of the increasing number of data points is alleviated by using dictionaries of kernel functions. A comparison with a previously developed method showcases the generality of the new model.

The recursive least-squares algorithm with $\ell_1$-norm regularization ($\ell_1$-RLS) exhibits excellent performance in terms of convergence rate and steady-state error in identification of sparse systems. Nevertheless few works have studied its stochastic behavior, in particular its transient performance. In this letter, we derive analytical models of the transient behavior of the $\ell_1$-RLS in the mean and mean-square sense. Simulation results illustrate the accuracy of these models., Comment: 5 pages, 2 figures

International audience; Modeling relations between local optimum parameter vectors in multitask networks has attracted much attention over the last years. This work considers a distributed optimization problem for parameter vectors with a jointly sparse structure among nodes, that is, the parameter vectors share the same support set. By introducing an L∞,1-norm penalty at each node, and using a proximal gradient method to minimize the regularized cost, we devise a proximal multitask diffusion LMS algorithm which promotes the joint-sparsity to enhance the estimation performance. Analyses are provided to ensure the stability. Simulation results are presented to highlight the performance.

International audience; Detecting changes in network-structured time series data is of utmost importance in critical applications as diverse as detecting denial of service attacks against online service providers or monitoring energy and water supplies. The aim of this paper is to address this challenge when anomalies activate unknown groups of nodes in a network. We devise an online change-point detection algorithm that fully benefits from the recent advances in graph signal processing to exploit the characteristics of the data that lie on irregular supports. Built upon the kernel machinery, it performs density ratio estimation in an online way. The algorithm is scalable in the sense that it is spatially distributed over the nodes to monitor large-scale dynamic networks. The detection and localization performances of the algorithm are illustrated with simulated data.

International audience; In graph signal processing, there are often settings where the graph topology is not known beforehand and has to be estimated from data. Moreover, some graphs can be dynamic, such as brain activity supported by neurons or brain regions. This paper focuses on estimating in an online and adaptive manner a network structure capturing the non-linear dependencies among streaming graph signals in the form of a possibly directed, adjacency matrix. By projecting data into a higher-or infinite-dimension space, we focus on capturing nonlinear relationships between agents. In order to mitigate the increasing number of data points, we employ kernel dictionaries. Finally, we run a series of tests in order to experimentally illustrate the usefulness of our kernel-based approach on biomedical data, on which we obtain results comparable to state-of-the-art methods.

Diffusion adaptation is a powerful strategy for distributed estimation and learning over networks. Motivated by the concept of combining adaptive filters, this work proposes a combination framework that aggregates the operation of multiple diffusion strategies for enhanced performance. By assigning a combination coefficient to each node, and using an adaptation mechanism to minimize the network error, we obtain a combined diffusion strategy that benefits from the best characteristics of all component strategies simultaneously in terms of excess-mean-square error (EMSE). Analyses of the universality are provided to show the superior performance of affine combination scheme and to characterize its behavior in the mean and mean-square sense. Simulation results are presented to demonstrate the effectiveness of the proposed strategies, as well as the accuracy of theoretical findings., 31 pages

Modeling relations between local optimum parameter vectors to estimate in multitask networks has attracted much attention over the last years. This work considers a distributed optimization problem with jointly sparse structure among nodes, that is, the local solutions have the same sparse support set. Several mixed norm have been proposed to address the jointly sparse structure in the literature. Among several candidates, the (reweighted) $\ell _{\infty,1}$ -norm is element-wise separable, it is more convenient to evaluate their approximate proximal operators. Thus by introducing a (reweighted) $\ell _{\infty,1}$ -norm penalty term at each node, and using a proximal gradient method to minimize the regularized cost, we devise a proximal multitask diffusion LMS algorithm which can promote joint-sparsity. Analyses are provided to characterize the algorithm behavior in the mean and mean-square sense. Simulation results are presented to show its effectiveness, as well as the accuracy of the theoretical findings.

Combining diffusion strategies with complementary properties enables enhanced performance when they can be run simultaneously. In this article, we first propose two schemes for the convex combination of two diffusion strategies, namely, the power-normalized scheme and the sign-regressor scheme. Then, we conduct theoretical analysis for one of the schemes, i.e., the power-normalized one. An analysis of universality shows that it cannot perform worse than any of its component strategies in terms of the excess mean-square-error (EMSE) at steady state, and sometimes even better. An analysis of stability also reveals that it is more stable than affine combination schemes already proposed by the authors in the literature. Next, several adjustments are proposed to further improve the performance of convex combination schemes. A discussion about the computational and communication complexity is provided, as well as a comparison between convex and affine combination schemes. Finally, simulation results are shown to demonstrate their effectiveness, the accuracy of the theoretical results, and the improved stability of the convex power-normalized scheme over the affine one.

International audience; The problem of learning simultaneously several related tasks has received considerable attention in several domains, especially in machine learning with the so-called multitask learning problem or learning to learn problem [1], [2]. Multitask learning is an approach to inductive transfer learning (using what is learned for one problem to assist in another problem) and helps improve generalization performance relative to learning each task separately by using the domain information contained in the training signals of related tasks as an inductive bias. Several strategies have been derived within this community under the assumption that all data are available beforehand at a fusion center. However, recent years have witnessed an increasing ability to collect data in a distributed and streaming manner. This requires the design of new strategies for learning jointly multiple tasks from streaming data over distributed (or networked) systems. This article provides an overview of multitask strategies for learning and adaptation over networks. The working hypothesis for these strategies is that agents are allowed to cooperate with each other in order to learn distinct, though related tasks. The article shows how cooperation steers the network limiting point and how different cooperation rules allow to promote different task relatedness models. It also explains how and when cooperation over multitask networks outperforms non-cooperative strategies.

We study the problem of distributed estimation over adaptive networks where communication delays exist between nodes. In particular, we investigate the diffusion Least-Mean- Square (LMS) strategy where delayed intermediate estimates (due to the communication channels) are employed during the combination step. One important question is: Do the delays affect the stability condition and performance? To answer this question, we conduct a detailed performance analysis in the mean and in the mean-square-error sense of the diffusion LMS with delayed estimates. Stability conditions, transient and steady-state mean-square-deviation (MSD) expressions are provided. One of the main findings is that diffusion LMS with delays can still converge under the same step-sizes condition of the diffusion LMS without delays. Finally, simulation results illustrate the theoretical findings., to appear in IEEE Signal Processing Letters

International audience; We study the problem of parametric modeling of network-structured signals with graph filters. To benefit from the properties of several graph shift operators simultaneously, and to enhance interpretability, we investigate combinations of parallel graph filters with different shift operators. Due to their extra degrees of freedom, these models might suffer from over-fitting. We address this problem through a weighted ℓ 2 -norm regularization formulation to perform model selection by encouraging group sparsity. What makes this formulation interesting is that it is actually a smooth convex optimization problem. Experiments on real-world data structured by undirected and directed graphs show the effectiveness of this method.

In this work, we are interested in adaptive and distributed estimation of graph filters from streaming data. We formulate this problem as a consensus estimation problem over graphs, which can be addressed with diffusion LMS strategies. Most popular graph-shift operators such as those based on the graph Laplacian matrix, or the adjacency matrix, are not energy preserving. This may result in an ill-conditioned estimation problem, and reduce the convergence speed of the distributed algorithms. To address this issue and improve the transient performance, we introduce a preconditioned graph diffusion LMS algorithm. We also propose a computationally efficient version of this algorithm by approximating the Hessian matrix with local information. Performance analyses in the mean and mean-square sense are provided. Finally, we consider a more general problem where the filter coefficients to estimate may vary over the graph. To avoid a large estimation bias, we introduce an unsupervised clustering method for splitting the global estimation problem into local ones. Numerical results show the effectiveness of the proposed algorithms and validate the theoretical results., 14 pages, 13 figures