Chiara Ravazzi

Chiara Ravazzi, Paolo Frasca, Roberto Tempo et al.

This paper regards the relative localization problem in sensor networks. We study a randomized algorithm, which is based on input-driven consensus dynamics and involves pairwise "gossip" communications and updates. Due to the randomness of the updates, the state of this algorithm ergodically oscillates around a limit value. Exploiting the ergodicity of the dynamics, we show that the time-average of the state almost surely converges to the least-squares solution of the localization problem. Remarkably, the computation of the time-average does not require the sensors to share any common clock. Hence, the proposed algorithm is fully distributed and asynchronous.

Fabio Fagnani, Sophie M. Fosson, Chiara Ravazzi

In this paper, we address the problem of simultaneous classification and estimation of hidden parameters in a sensor network with communications constraints. In particular, we consider a network of noisy sensors which measure a common scalar unknown parameter. We assume that a fraction of the nodes represent faulty sensors, whose measurements are poorly reliable. The goal for each node is to simultaneously identify its class (faulty or non-faulty) and estimate the common parameter. We propose a novel cooperative iterative algorithm which copes with the communication constraints imposed by the network and shows remarkable performance. Our main result is a rigorous proof of the convergence of the algorithm and a characterization of the limit behavior. We also show that, in the limit when the number of sensors goes to infinity, the common unknown parameter is estimated with arbitrary small error, while the classification error converges to that of the optimal centralized maximum likelihood estimator. We also show numerical results that validate the theoretical analysis and support their possible generalization. We compare our strategy with the Expectation-Maximization algorithm and we discuss trade-offs in terms of robustness, speed of convergence and implementation simplicity.

Chiara Ravazzi, Nelson P. K. Chan, Paolo Frasca

This paper studies the problem of estimation from relative measurements in a graph, in which a vector indexed over the nodes has to be reconstructed from pairwise measurements of differences between its components associated to nodes connected by an edge. In order to model heterogeneity and uncertainty of the measurements, we assume them to be affected by additive noise distributed according to a Gaussian mixture. In this original setup, we formulate the problem of computing the Maximum-Likelihood (ML) estimates and we design two novel algorithms, based on Least Squares regression and Expectation-Maximization (EM). The first algorithm (LS- EM) is centralized and performs the estimation from relative measurements, the soft classification of the measurements, and the estimation of the noise parameters. The second algorithm (Distributed LS-EM) is distributed and performs estimation and soft classification of the measurements, but requires the knowledge of the noise parameters. We provide rigorous proofs of convergence of both algorithms and we present numerical experiments to evaluate and compare their performance with classical solutions. The experiments show the robustness of the proposed methods against different kinds of noise and, for the Distributed LS-EM, against errors in the knowledge of noise parameters.

Chiara Ravazzi, Sarah Hojjatinia, Constantino M. Lagoa et al.

In this paper, we propose a technique for the estimation of the influence matrix in a sparse social network, in which $n$ individual communicate in a gossip way. At each step, a random subset of the social actors is active and interacts with randomly chosen neighbors. The opinions evolve according to a Friedkin and Johnsen mechanism, in which the individuals updates their belief to a convex combination of their current belief, the belief of the agents they interact with, and their initial belief, or prejudice. Leveraging recent results of estimation of vector autoregressive processes, we reconstruct the social network topology and the strength of the interconnections starting from \textit{partial observations} of the interactions, thus removing one of the main drawbacks of finite horizon techniques. The effectiveness of the proposed method is shown on randomly generation networks.

Antonio Longo, Chiara Ravazzi, Fabrizio Dabbene et al.

Motivated by the increasing interest of the control community towards social sciences and the study of opinion formation and belief systems, in this paper we address the problem of exploiting voting data for inferring the underlying affinity of individuals to competing ideology groups. In particular, we mine key voting records of the Italian Senate during the XVII legislature, in order to extract the hidden information about the closeness of senators to political parties, based on a parsimonious feature extraction method that selects the most relevant bills. Modeling the voting data as outcomes of a mixture of random variables and using sparse learning techniques, we cast the problem in a probabilistic framework and derive an information theoretic measure, which we refer to as Political Data-aNalytic Affinity (Political DNA). The advantages of this new affinity measure are discussed in the paper. The results of the numerical analysis on voting data unveil underlying relationships among political exponents of the Italian Senate.

Diego Valsesia, Sophie Marie Fosson, Chiara Ravazzi et al.

Embeddings provide compact representations of signals in order to perform efficient inference in a wide variety of tasks. In particular, random projections are common tools to construct Euclidean distance-preserving embeddings, while hashing techniques are extensively used to embed set-similarity metrics, such as the Jaccard coefficient. In this letter, we theoretically prove that a class of random projections based on sparse matrices, called SparseHash, can preserve the Jaccard coefficient between the supports of sparse signals, which can be used to estimate set similarities. Moreover, besides the analysis, we provide an efficient implementation and we test the performance in several numerical experiments, both on synthetic and real datasets.

Attilio Fiandrotti, Sophie M. Fosson, Chiara Ravazzi et al.

Compressive sensing promises to enable bandwidth-efficient on-board compression of astronomical data by lifting the encoding complexity from the source to the receiver. The signal is recovered off-line, exploiting GPUs parallel computation capabilities to speedup the reconstruction process. However, inherent GPU hardware constraints limit the size of the recoverable signal and the speedup practically achievable. In this work, we design parallel algorithms that exploit the properties of circulant matrices for efficient GPU-accelerated sparse signals recovery. Our approach reduces the memory requirements, allowing us to recover very large signals with limited memory. In addition, it achieves a tenfold signal recovery speedup thanks to ad-hoc parallelization of matrix-vector multiplications and matrix inversions. Finally, we practically demonstrate our algorithms in a typical application of circulant matrices: deblurring a sparse astronomical image in the compressed domain.

Paolo Frasca, Chiara Ravazzi, Roberto Tempo et al.

In this paper we study a novel model of opinion dynamics in social networks, which has two main features. First, agents asynchronously interact in pairs, and these pairs are chosen according to a random process. We refer to this communication model as "gossiping". Second, agents are not completely open-minded, but instead take into account their initial opinions, which may be thought of as their "prejudices". In the literature, such agents are often called "stubborn". We show that the opinions of the agents fail to converge, but persistently undergo ergodic oscillations, which asymptotically concentrate around a mean distribution of opinions. This mean value is exactly the limit of the synchronous dynamics of the expected opinions.