Dans cette thèse, nous étudions les graphes aléatoires en utilisant des outils de la théorie des matrices aléatoires et l’analyse probabilistique afin de résoudre des problèmes clefs dans le domaine des réseaux complexes et Big Data. Le premier problème qu’on considère est de détecter un sous graphe Erdős–Rényi G(m,p) plante dans un graphe Erdős–Rényi G(n,q). Nous dérivons les distributions d’une statistique basée sur les propriétés spectrales d’une matrice définie du graphe. Ensuite, nous considérons le problème de la récupération des sommets du sous graphe en présence de l’information supplémentaire. Pour cela nous utilisons l’algorithme «Belief Propagation». Le BP sans informations supplémentaires ne réussit à la récupération qu’avec un SNR effectif lambda au-delà d’un seuil. Nous prouvons qu’en présence des informations supplémentaires, ce seuil disparaît et le BP réussi pour n’importe quel lambda. Finalement, nous dérivons des expressions asymptotiques pour PageRank sur une classe de graphes aléatoires non dirigés appelés « fast expanders », en utilisant des techniques théoriques à la matrice aléatoire. Nous montrons que PageRank peut être approché pour les grandes tailles du graphe comme une combinaison convexe du vecteur de dégré normalisé et le vecteur de personnalisation du PageRank, lorsque le vecteur de personnalisation est suffisamment délocalisé. Par la suite, nous caractérisons les formes asymptotiques de PageRank sur le Stochastic Block Model (SBM) et montrons qu’il contient un terme de correction qui est fonction de la structure de la communauté. / In this thesis, we study random graphs using tools from Random Matrix Theory and probability to tackle key problems in complex networks and Big Data. First we study graph anomaly detection. Consider an Erdős-Rényi (ER) graph with edge probability q and size n containing a planted subgraph of size m and probability p. We derive a statistical test based on the eigenvalue and eigenvector properties of a suitably defined matrix to detect the planted subgraph. We analyze the distribution of the derived test statistic using Random Matrix Theoretic techniques. Next, we consider subgraph recovery in this model in the presence of side-information. We analyse the effect of side-information on the detectability threshold of Belief Propagation (BP) applied to the above problem. We show that BP correctly recovers the subgraph even with noisy side-information for any positive value of an effective SNR parameter. This is in contrast to BP without side-information which requires the SNR to be above a certain threshold. Finally, we study the asymptotic behaviour of PageRank on a class of undirected random graphs called fast expanders, using Random Matrix Theoretic techniques. We show that PageRank can be approximated for large graph sizes as a convex combination of the normalized degree vector and the personalization vector of the PageRank, when the personalization vector is sufficiently delocalized. Subsequently, we characterize asymptotic PageRank on Stochastic Block Model (SBM) graphs, and show that it contains a correction term that is a function of the community structure.

Motivée par les récentes avancées dans l'analyse théorique des performances des algorithmes d'apprentissage automatisé, cette thèse s'intéresse à l'analyse de performances et à l'amélioration de la classification nonsupervisée de données et graphes en grande dimension. Spécifiquement, dans la première grande partie de cette thèse, en s'appuyant sur des outils avancés de la théorie des grandes matrices aléatoires, nous analysons les performances de méthodes spectrales sur des modèles de graphes réalistes et denses ainsi que sur des données en grandes dimensions en étudiant notamment les valeurs propres et vecteurs propres des matrices d'affinités de ces données. De nouvelles méthodes améliorées sont proposées sur la base de cette analyse théorique et démontrent à travers de nombreuses simulations que leurs performances sont meilleures comparées aux méthodes de l'état de l'art. Dans la seconde partie de la thèse, nous proposons un nouvel algorithme pour la détection de communautés hétérogènes entre plusieurs couches d'un graphe à plusieurs types d'interaction. Une approche bayésienne variationnelle est utilisée pour approximer la distribution apostériori des variables latentes du modèle. Toutes les méthodes proposées dans cette thèse sont utilisées sur des bases de données synthétiques et sur des données réelles et présentent de meilleures performances en comparaison aux approches standard de classification dans les contextes susmentionnés. / Spurred by recent advances on the theoretical analysis of the performances of the data-driven machine learning algorithms, this thesis tackles the performance analysis and improvement of high dimensional data and graph clustering. Specifically, in the first bigger part of the thesis, using advanced tools from random matrix theory, the performance analysis of spectral methods on dense realistic graph models and on high dimensional kernel random matrices is performed through the study of the eigenvalues and eigenvectors of the similarity matrices characterizing those data. New improved methods are proposed and are shown to outperform state-of-the-art approaches. In a second part, a new algorithm is proposed for the detection of heterogeneous communities from multi-layer graphs using variational Bayes approaches to approximate the posterior distribution of the sought variables. The proposed methods are successfully applied to synthetic benchmarks as well as real-world datasets and are shown to outperform standard approaches to clustering in those specific contexts.

Le travail effectué dans cette thèse concerne les domaines de la théorie des matrices aléatoires et des probabilités libres, dont on connaît les riches connexions depuis le début des années 90. Les résultats s'organisent principalement en deux parties : la première porte sur la liberté infinitésimale, la seconde sur les matrices aléatoires déformées. Plus précisément, on jette les bases d'une théorie combinatoire de la liberté infinitésimale, au premier ordre d'abord, telle que récemment introduite par Belinschi et Shlyakhtenko, puis aux ordres supérieurs. On en donne un cadre simple et général, et on introduit des fonctionnelles de cumulants non-croisés, caractérisant la liberté infinitésimale. L'accent est mis sur la combinatoire et les idées d'essence différentielle qui sous-tendent cette notion. La seconde partie poursuit l'étude des déformations de modèles matriciels, qui a été ces dernières années un champ de recherche très actif. Les résultats présentés sont originaux en ce qu'ils concernent des perturbations déterministes Hermitiennes de rang non nécessairement fini de matrices de Wigner et de Wishart. En outre, un apport de ce travail est la mise en lumière du lien entre la convergence des valeurs propres de ces modèles et les probabilités libres, plus particulièrement le phénomène de subordination pour la convolution libre. Ce lien donne une illustration de la puissance des idées des probabilités libres dans les problèmes de matrices aléatoires.

Ce mémoire de HDR est conçu comme un guide de lecture. Pour chacun de mes thèmes de recherche, j'ai cherché à décrire le cadre dans lequel se situe le travail et à en expliquer les résultats principaux. Le lecteur est invité à se réferrer aux articles pour plus de détails, notamment sur le développement des outils théoriques. Cette notice couvre la période allant d'octobre 2000 (début de mon postdoc à Cornell) à septembre 2007.

Le sujet principal de cette thèse est la physique des verres de spin. Les verres de spin ont été introduits au début des années 70 pour décrire alliages magnétiques diluées. Ils ont désormais été considerés pour comprendre le comportement de liquides sousrefroidis. Parmis les systèmes qui peuvent être décrits par le langage des systèmes desordonnés, on trouve les problèmes d’optimisation combinatoire. Dans la première partie de cette thèse, nous considérons les modèles de verre de spin avec intéraction de Kac pour investiguer la phase de basse température des liquides sous-refroidis. Dans les chapitres qui suivent, nous montrons comment certaines caractéristiques des modèles de verre de spin peuvent être obtenues à partir de résultats de la théorie des matrices aléatoires en connection avec la statistique des valeurs extrêmes. Dans la dernière partie de la thèse, nous considérons la connexion entre la théorie desverres de spin et la science computationnelle, et présentons un nouvel algorithme qui peut être appliqué à certains problèmes dans le domaine des finances. / The main subject of this thesis is the physics of spin glasses. After their introduction in the 70s in order to describe dilute magnetic alloys, spin-glass models have been considered prototype models to understand the behavior of supercooled liquids. Among the systems that can be described and analyzed using the language of disordered systems, there are problems of combinatorial optimization. In the first part of the thesis, we consider spin-glass models with Kac interactions in order to investigate the supercooled phase of glass-forming liquids. Afterwards, we show how some features of spin-glass models can be described by ubiquitous results of Random Matrix Theory in connection with Extreme Value Statistics. Finally, from the interaction of spin-glass theory and computer science, we put forward a new algorithm of immediate application in Financial problems.

Il est attendu que les radios flexibles constituent un tournant technologique majeur dans le domaine des communications sans fil. Le point de vue adopté en radios flexibles est de considérer les canaux de communication comme un ensemble de ressources qui peuvent être accédées sur demande par un réseau primaire sous licence ou de manière opportuniste par un réseau secondaire à plus faible priorité. Du point de vue de la couche physique, le réseau primaire n’a aucune information sur l’existence de réseaux secondaires, de sorte que ces derniers doivent explorer l’environnement aérien de manière autonome à la recherche d’opportunités spectrales et exploiter ces ressources de manière optimale. Les phases d’exploration et d’exploitation, qui impliquent la gestion de nombreux agents, doivent être très fiables, rapides et efficaces. L’objectif de cette thèse est de modéliser, d’analyser et de proposer des solutions efficaces et quasi optimales pour ces dernières opérations.En ce qui concerne la phase d’exploration, nous calculons le test optimal de Neyman-Pearson de détection de plusieurs sources primaires via un réseau de capteurs. Cette procédure permet à un réseau secondaire d’établir la présence de ressources spectrales disponibles. La complexité calculatoire de l’approche optimale appelle cependant la mise en place de méthodes moins onéreuses, que nous rappelons et discutons. Nous étendons alors le test de détection en l’estimation aveugle de la position de sources multiples, qui permet l’acquisition d’informations détaillées sur les ressources spectrales disponibles.Le second volet de cette thèse est consacré à la phase d’exploitation optimale des ressources au niveau du réseau secondaire. Pour ce faire, nous obtenons une approximation fine du débit ergodique d’un canal multi-antennes à accès multiples et proposons des solutions peu coûteuses en termes de feedback afin que les réseaux secondaires s’adaptent rapidement aux évolutions rapides du réseau primaire. / Future cognitive radio networks are expected to come as a disruptive technological advance in the currently saturated field of wireless communications. The idea behind cognitive radios is to think of the wireless channels as a pool of communication resources, which can be accessed on-demand by a primary licensed network or opportunistically preempted (or overlaid) by a secondary network with lower access priority. From a physical layer point of view, the primary network is ideally oblivious of the existence of a co-localized secondary networks. The latter are therefore required to autonomously explore the air in search for resource left-overs, and then to optimally exploit the available resource. The exploration and exploitation procedures, which involve multiple interacting agents, are requested to be highly reliable, fast and efficient. The objective of the thesis is to model, analyse and propose computationally efficient and close-to-optimal solutions to the above operations.Regarding the exploration phase, we first resort to the maximum entropy principle to derive communication models with many unknowns, from which we derive the optimal multi-source multi-sensor Neyman-Pearson signal sensing procedure. The latter allows for a secondary network to detect the presence of spectral left-overs. The computational complexity of the optimal approach however calls for simpler techniques, which are recollected and discussed. We then proceed to the extension of the signal sensing approach to the more advanced blind user localization, which provides further valuable information to overlay occupied spectral resources.The second part of the thesis is dedicaded to the exploitation phase, that is, the optimal sharing of available resources. To this end, we derive an (asymptotically accurate) approximated expression for the uplink ergodic sum rate of a multi-antenna multiple-access channel and propose solutions for cognitive radios to adapt rapidly to the evolution of the primary network at a minimum feedback cost for the secondary networks.

Dans cette thèse, on étudie l'application de la méthode des moments pour les télécommunications. On analyse cette méthode et on montre son importance pour l'étude des matrices aléatoires. On utilise le cadre de probabilités libres pour analyser cette méthode. La notion de produit de convolution/déconvolution libre peut être utilisée pour prédire le spectre asymptotique de matrices aléatoires qui sont asymptotiquement libres. On montre que la méthode de moments est un outil puissant même pour calculer les moments/moments asymptotiques de matrices qui n'ont pas la propriété de liberté asymptotique. En particulier, on considère des matrices aléatoires gaussiennes de taille finie et des matrices de Vandermonde al ?eatoires. On développe en série entiére la distribution des valeurs propres de differents modèles, par exemple les distributions de Wishart non-centrale et aussi les distributions de Wishart avec des entrées corrélées de moyenne nulle. Le cadre d'inference pour les matrices des dimensions finies est suffisamment souple pour permettre des combinaisons de matrices aléatoires. Les résultats que nous présentons sont implémentés en code Matlab en générant des sous-ensembles, des permutations et des relations d'équivalence. On applique ce cadre à l'étude des réseaux cognitifs et des réseaux à forte mobilité. On analyse les moments de matrices de Vandermonde aléatoires avec des entrées sur le cercle unitaire. On utilise ces moments et les détecteurs à expansion polynomiale pour décrire des détecteurs à faible complexité du signal transmis par des utilisateurs mobiles à une station de base (ou avec deux stations de base) représentée par des réseaux linéaires uniformes. / In this thesis, we focus on the analysis of the moments method, showing its importance in the application of random matrices to wireless communication. This study is conducted in the free probability framework. The concept of free convolution/deconvolution can be used to predict the spectrum of sums or products of random matrices which are asymptotically free. In this framework, we show that the moments method is very appealing and powerful in order to derive the moments/asymptotic moments for cases when the property of asymptotic freeness does not hold. In particular, we focus on Gaussian random matrices with finite dimensions and structured matrices as Vandermonde matrices. We derive the explicit series expansion of the eigenvalue distribution of various models, as noncentral Wishart distributions, as well as correlated zero mean Wishart distributions. We describe an inference framework so flexible that it is possible to apply it for repeated combinations of random ma- trices. The results that we present are implemented generating subsets, permutations, and equivalence relations. We developped a Matlab routine code in order to perform convolution or deconvolution numerically in terms of a set of input moments. We apply this inference framework to the study of cognitive networks, as well as to the study of wireless networks with high mobility. We analyze the asymptotic moments of random Vandermonde matrices with entries on the unit circle. We use them and polynomial expansion detectors in order to design a low complexity linear MMSE decoder to recover the signal transmitted by mobile users to a base station or two base stations, represented by uniform linear arrays.

Les prévisions relatives trafic de données au sein des systèmes de communications sans-fil suggèrent une croissance exponentielle, principalement alimentée par l’essor de transferts vidéo mobiles. Etant donné la nature soudaine et fluctuante des demandes de transfert vidéo, il faut dès à présent réfléchir à de nouveaux algorithmes d’allocation de ressources performants. En effet, les algorithmes en couche physique traditionnels, qui réalisent de l’allocation de ressources sous l’hypothèse classique que les transmetteurs sont toujours saturés avec des bits d’information, risquent à l’avenir de s’avérer inefficients. Pour cette raison, les algorithmes de demain se doivent d’être dynamiques, dans le sens où ils seront capables de prendre en compte la nature stochastique des fluctuations du trafic de données et qu’ils intégreront des informations issus de processus de couches supérieures.L’idée centrale de cette thèse est de développer des algorithmes, travaillant avec des informations issues de la couche PHY et de la couche NET, dans un scénario Multi-cells et MIMO (Multiple Inputs, Multiple Outputs).Plus particulièrement, nous considérons un réseau de stations de base (BS) équipés avec plusieurs antennes, chargés de servir plusieurs terminaux mobiles équipés d’une seule antenne (UT) dans leurs cellules respectives. Ce qui nous différencie des travaux précédents, c’est que nous tenons compte de l’aléa avec lequel des demandes de transferts peuvent arriver et que, pour cette raison, nous modélisons la formation de queue de données au niveau des stations de base. Dans cette disposition, nous développons plusieurs algorithmes multicouches, réalisant de l’allocation de ressources décentralisée, et ce, dans une optique d’efficacité énergétique. En particulier, il s’agit ici de réaliser des algorithmes réalisant du beamforming de façon décentralisée et capables de contrôler des fluctuations de trafic, des algorithmes optimisant l’efficacité énergétique sous une contrainte de qualité de service moyenne, des algorithmes de planification décentralisés dans des scénarios multi-cellulaires. Dans cette perspective, nous choisissons de recourir non seulement à des outils d’optimisation de la théorie de Lyapunov, mais également à la théorie des matrices aléatoires et à la théorie du contrôle stochastique. / Future wireless communication systems are expected to see an explosion in the wireless traffic which is mainly fueled by mobile video traffic. Due to the time varying and bursty nature of video traffic, wireless systems will see a widerrange of fluctuations in their traffic patterns. Therefore, traditional physical layer based algorithms which perform resource allocation under the assumption that the transmitters are always saturated with information bits, might no longer be efficient. It is, thus, important to design dynamic resource allocation algorithms which can incorporate higher layer processes and account for the stochastic nature of the wireless traffic.The central idea of this thesis is to develop cross-layer design algorithmsbetween the physical and the network layer in a multiple input multiple output (MIMO) multi-cell setup. Specifically, we consider base stations (BSs) equipped with multiple antennas serving multiple single antenna user terminals (UTs) in their respective cells. In contrast to the previous works, we consider the randomness in the arrival of information bits and hence account for the queuing at the BSs. With this setup, we develop various cross-layer based resource allocation algorithms. We incorporate two important design considerations namely decentralized design and energy efficiency. In particular, we focus on developing decentralized beamforming and traffic flow controller design, energy efficient design under time average QoS constraints and decentralized scheduling strategy in a multi-cell scenario. To this end, we use tools from Lyapunov optimization, random matrix theory and stochastic control theory.

La finesse de la résolution spectrale et spatiale des images hyperspectrales en font des données de très grande dimension. C'est également le cas d'autres types de données, où leur taille tend à augmenter pour de plus en plus d'applications. La complexité des données provenant de l'hétérogénéité spectrale et spatiale, de la non gaussianité du bruit et des processus physiques sous-jacents, renforcent la richesse des informations présentes sur une image hyperspectrale. Exploiter ces informations demande alors des outils statistiques adaptés aux grandes données mais aussi à leur nature non gaussienne. Des méthodes reposant sur la théorie des matrices aléatoires, théorie adaptée aux données de grande dimension, et reposant sur la robustesse, adaptée aux données non gaussiennes, sont ainsi proposées dans cette thèse, pour des applications à l'imagerie hyperspectrale. Cette thèse propose d'améliorer deux aspects du traitement des images hyperspectrales : l'estimation du nombre d'endmembers ou de l'ordre du modèle et le problème du démélange spectral. En ce qui concerne l'estimation du nombre d'endmembers, trois nouveaux algorithmes adaptés au modèle choisi sont proposés, le dernier présentant de meilleures performances que les deux autres, en raison de sa plus grande robustesse.Une application au domaine de la finance est également proposée. Pour le démélange spectral, trois méthodes sont proposées, qui tiennent comptent des diff érentes particularités possibles des images hyperspectrales. Cette thèse a permis de montrer que la théorie des matrices aléatoires présente un grand intérêt pour le traitement des images hyperspectrales. Les méthodes développées peuvent également s'appliquer à d'autres domaines nécessitant le traitement de données de grandes dimensions. / Hyperspectral imaging generates large data due to the spectral and spatial high resolution, as it is the case for more and more other kinds of applications. For hyperspectral imaging, the data complexity comes from the spectral and spatial heterogeneity, the non-gaussianity of the noise and other physical processes. Nevertheless, this complexity enhances the wealth of collected informations, that need to be processed with adapted methods. Random matrix theory and robust processes are here suggested for hyperspectral imaging application: the random matrix theory is adapted to large data and the robustness enables to better take into account the non-gaussianity of the data. This thesis aims to enhance the model order selection on a hyperspectral image and the unmixing problem. As the model order selection is concerned, three new algorithms are developped, and the last one, more robust, gives better performances. One financial application is also presented. As for the unmixing problem, three methods that take into account the peculierities of hyperspectral imaging are suggested. The random matrix theory is of great interest for hyperspectral image processing, as demonstrated in this thesis. Differents methods developped here can be applied to other field of signal processing requiring the processing of large data.

No description available.