Distributed iterative algorithms are of great importance, as they are known to provide low-complexity and approximate solutions to what are otherwise high-dimensional intractable optimization problems. The theory of message-passing based algorithms is fairly well developed in the coding, machine learning and statistical physics literatures. Even though several applications of message-passing algorithms have already been identified, this work aims at establishing that a plethora of other applications exist where it can be of great importance. In particular, the goal of this work is to develop and demonstrate applications of this class of algorithms in network communications and computational biology. In the domain of communications, message-passing based algorithms provide distributed ways of inferring the optimal solution without the aid of a central agent for various optimization problems that happen in the resource allocation of communication networks. Our main framework is Affinity Propagation (AP), originally developed for clustering problems. We reinterpret this framework to unify the development of distributed algorithms for discrete resource allocation problems. Also, we consider a network-coded communication network, where continuous rate allocation is studied. We formulate an optimization problem with a linear cost function, and then utilize a Belief Propagation (BP) approach to determine a decentralized rate allocation strategy. Next, we move to the domain of computational biology, where graphical representations and computational biology play a major role. First, we consider the motif finding problem with several DNA sequences. In effect, this is a sequence matching problem, which can be modeled using various graphical representations and also solved using low-complexity algorithms based on message-passing techniques. In addition, we address the application of message-passing algorithms for a DNA sequencing problem where the one dimensional structure of a single DNA sequence is identified. We reinterpret the problem as being equivalent to the decoding of a nonlinear code. Based on the iterative decoding framework, we develop an appropriate graphical model which enables us to derive a message-passing algorithm to improve the performance of the DNA sequencing problem. Although this work consists of disparate application domains of communications, networks and computational biology, graphical models and distributed message-passing algorithms form a common underlying theme. / text

In this thesis, we consider the problem of decentralized estimation under communication constraints in the context of Collaborative Signal and Information Processing. Motivated by sensor network applications, a high volume of data collected at distinct locations and possibly in diverse modalities together with the spatially distributed nature and the resource limitations of the underlying system are of concern. Designing processing schemes which match the constraints imposed by the system while providing a reasonable accuracy has been a major challenge in which we are particularly interested in the tradeoff between the estimation performance and the utilization of communications subject to energy and bandwidth constraints. One remarkable approach for decentralized inference in sensor networks is to exploit graphical models together with message passing algorithms. In this framework, after the so-called information graph of the problem is constructed, it is mapped onto the underlying network structure which is responsible for delivering the messages in accordance with the schedule of the inference algorithm. However it is challenging to provide a design perspective that addresses the tradeoff between the estimation accuracy and the cost of communications. Another approach has been performing the estimation at a fusion center based on the quantized information provided by the peripherals in which the fusion and quantization rules are sought while taking a restricted set of the communication constraints into account. We consider two classes of in-network processing strategies which cover a broad range of constraints and yield tractable Bayesian risks that capture the cost of communications as well as the penalty for estimation errors. A rigorous design setting is obtained in the form of a constrained optimization problem utilizing the Bayesian risks. These processing schemes have been previously studied together with the structures that the solutions exhibit in the context of decentralized detection in which a decision out of finitely many choices is made. We adopt this framework for the estimation problem. However, for the case, computationally infeasible solutions arise that involve integral operators that are impossible to evaluate exactly in general. In order not to compromise the fidelity of the model we develop an approximation framework using Monte Carlo methods and obtain particle representations and approximate computational schemes for both the in-network processing strategies and the solution schemes to the design problem. Doing that, we can produce approximating strategies for decentralized estimation networks under communication constraints captured by the framework including the cost. The proposed Monte Carlo optimization procedures operate in a scalable and efficient manner and can produce results for any family of distributions of concern provided that samples can be produced from the marginals. In addition, this approach enables a quantification of the tradeoff between the estimation accuracy and the cost of communications through a parameterized Bayesian risk.

Face au déluge actuel de données principalement non structurées, les graphes ont démontré, dans une variété de domaines scientifiques, leur importance croissante comme language abstrait pour décrire des interactions complexes entre des objets complexes. L’un des principaux défis posés par l’étude de ces réseaux est l’inférence de propriétés macroscopiques à grande échelle, affectant un grand nombre d’objets ou d’agents, sur la seule base des interactions microscopiquesqu’entretiennent leurs constituants élémentaires. La physique statistique, créée précisément dans le but d’obtenir les lois macroscopiques de la thermodynamique à partir d’un modèle idéal de particules en interaction, fournit une intuition décisive dans l’étude des réseaux complexes.Dans cette thèse, nous utilisons des méthodes issues de la physique statistique des systèmes désordonnés pour mettre au point et analyser de nouveaux algorithmes d’inférence sur les graphes. Nous nous concentrons sur les méthodes spectrales, utilisant certains vecteurs propres de matrices bien choisies, et sur les graphes parcimonieux, qui contiennent une faible quantité d’information. Nous développons une théorie originale de l’inférence spectrale, fondée sur une relaxation de l’optimisation de certaines énergies libres en champ moyen. Notre approche est donc entièrement probabiliste, et diffère considérablement des motivations plus classiques fondées sur l’optimisation d’une fonction de coût. Nous illustrons l’efficacité de notre approchesur différents problèmes, dont la détection de communautés, la classification non supervisée à partir de similarités mesurées aléatoirement, et la complétion de matrices. / In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between complex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties affecting a large number of objects, based solely on he microscopic interactions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks.In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an original theory of spectral inference based on a relaxation of various meanfield free energy optimizations. Our approach is therefore fully probabilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion.