Reliability and computational efficiency of classification error estimators are critical factors in classifier design. In a high-dimensional data setting where data is scarce, the conventional method of error estimation, cross-validation, can be very computationally expensive. In this thesis, we consider a particular discriminant analysis type classifier, the Randomly-Projected RLDA ensemble classifier, which operates under the assumption of such a ‘small sample’ regime. We conduct an asymptotic study of the generalization error of this classifier under this regime, which necessitates the use of tools from the field of random matrix theory. The main outcome of this study is a deterministic function of the true statistics of the data and the problem dimension that approximates the generalization error well for large enough dimensions. This is demonstrated by simulation on synthetic data. The main advantage of this approach is that it is computationally efficient. It also constitutes a major step towards the construction of a consistent estimator of the error that depends on the training data and not the true statistics, and so can be applied to real data. An analogous quantity for the Randomly-Projected LDA ensemble classifier, which appears in the literature and is a special case of the former, is also derived. We motivate its use for tuning the parameter of this classifier by simulation on synthetic data.

This thesis, divided into two parts, is concerned with the analysis of spectral and dynamical characteristics of certain quantum spin systems in the presence of either I) quenched disorder, or II) dynamical noise. In the first part, the quantum random energy model (QREM), a mean-field spin glass model with a many-body localisation transition, is studied. In Chapter 2, we attempt a diagrammatic perturbative analysis of the QREM from the ergodic side, proceeding by analogy to the single-particle theory of weak localisation. Whilst we are able to describe diffusion, the analogy breaks down and a description of the onset of localisation in terms of quantum corrections quickly becomes intractable. Some progress is possible by deriving a quantum kinetic equation, namely the relaxation of the one-spin reduced density matrix is determined, but this affords little insight and extension to two-spin quantities is difficult. We change our approach in Chapter 3, studying instead a stroboscopic version of the model using the formalism of quantum graphs. Here, an analytic evaluation of the form factor in the diagonal approximation is possible, which we find to be consistent with the universal random matrix theory (RMT) result in the ergodic regime. In Chapter 4, we replace the QREM's transverse field with a random kinetic term and present a diagrammatic calculation of the average density of states, exact in the large-N limit, and interpret the result in terms of the addition of freely independent random variables. In the second part, we turn our attention to noisy quantum spins. Chapter 5 is concerned with noninteracting spins coupled to a common stochastic field; correlations arising from the common noise relax only due to the spins' differing precession frequencies. Our key result is a mapping of the equation of motion of n-spin correlators onto the (integrable) non-Hermitian Richardson-Gaudin model, enabling exact calculation of the relaxation rate of correlations. The second problem, addressed in Chapter 6, is that of the dynamics of operator moments in a noisy Heisenberg model; qualitatively different behaviour is found depending on whether or not the noise conserves a component of spin. In the case of nonconserving noise, we report that the evolution of the second moment maps onto the Fredrickson-Andersen model - a kinetically constrained model originally introduced to describe the glass transition. This facilitates a rigorous study of operator spreading in a continuous-time model, providing a complementary viewpoint to recent investigations of random unitary circuits.

This dissertation presents the applications of state-of-the-art computation techniques and data analysis algorithms in three physical and biological problems: assembling DNA pieces, optimizing self-assembly yield, and identifying correlations from large multivariate datasets. In the first topic, in-depth analysis of using Sequencing by Hybridization (SBH) to reconstruct target DNA sequences shows that a modified reconstruction algorithm can overcome the theoretical boundary without the need for different types of biochemical assays and is robust to error. In the second topic, consistent with theoretical predictions, simulations using Graphics Processing Unit (GPU) demonstrate how controlling the short-ranged interactions between particles and controlling the concentrations optimize the self-assembly yield of a desired structure, and nonequilibrium behavior when optimizing concentrations is also unveiled by leveraging the computation capacity of GPUs. In the last topic, a methodology to incorporate existing categorization information into the search process to efficiently reconstruct the optimal true correlation matrix for multivariate datasets is introduced. Simulations on both synthetic and real financial datasets show that the algorithm is able to detect signals below the Random Matrix Theory (RMT) threshold. These three problems are representatives of using massive computation techniques and data analysis algorithms to tackle optimization problems, and outperform theoretical boundary when incorporating prior information into the computation. / Engineering and Applied Sciences

Multiple antennas at each side of the communication channel seem to be vital for future wireless communication systems. Multi-antenna communication provides throughput gains roughly proportional to the smallest number of antennas at the communicating terminals. On the other hand, multiple antennas at a terminal inevitably increase the hardware complexity of the latter. For efficient design of such systems relevant mathematical tools, capable of capturing the most significant features of the wireless multi-antenna channel - such as fading, spatial correlation, interference - are essential. This thesis, based on the asymptotic methods from statistical physics and random matrix theory, develops a series of asymptotic approximations for various metrics characterizing the performance of multi-antenna systems in different settings. The approximations become increasingly precise as the number of antennas at each terminal grows large and are shown to significantly simplify the performance analysis. This, in turn, enables efficient performance optimization, which would otherwise be intractable. After a general introduction, provided in Chapter 2, this thesis provides four different applications of large-system analysis. Thus, Chapter 3 analyzes multi-antenna multiple-access channel in the presence of non-Gaussian interference. The obtained large-system approximation of the sum rate is further used to carry out the precoder optimization routine for both Gaussian and finite-alphabet types of inputs. Meanwhile, Chapter 4 carries out the large-system analysis for a multi-hop relay channel with an arbitrary number of hops. Suboptimality of some conventional detectors has been captured through the concept of generalized posterior mean estimate. The obtained decoupling principle allows performance evaluation for a number of conventional detection schemes in terms of achievable rates and bit error rate. Chapter 5, in turn, studies achievable secrecy rates of multi-antenna wiretap channels in three different scenarios. In the quasi-static scenario, an alternating-optimization algorithm for the non-convex precoder optimization problem is proposed. The algorithm is shown to outperform the existing solutions, and it is conjectured to provide a secrecy capacity-achieving precoder. In the uncorrelated ergodic scenario, a large-system analysis is carried out for the ergodic secrecy capacity yielding a closed-form expression. In the correlated ergodic scenario, the obtained large-system approximation is used to address the corresponding problem of precoder optimization. Finally, Chapter6 addresses a practical case of random network topology for two scenarios: i) cellular mobile networks with randomly placed mobile users and ii) wiretap channel with randomly located eavesdroppers. Large-system approximations for the achievable sum rates are derived for each scenario, yielding simplified precoder optimization procedures for various system parameters. / <p>QC 20140901</p>

This thesis challenges several concepts in finance. Firstly, it is the Markowitz's solution to the portfolio problem. It introduces a new method which de- noises the covariance matrix - the cornerstone of the portfolio management. Random Matrix Theory originates in particle physics and was recently intro- duced to finance as the intersection between economics and natural sciences has widened over the past couple of years. Often discussed Efficient Market Hypothesis is opposed by adopting the assumption, that financial returns are driven by Paretian distributions, in- stead of Gaussian ones, as conjured by Mandelbrot some 50 years ago. The portfolio selection is set in a framework, where Expected Shortfall replaces the standard deviation as the risk measure. Therefore, direct optimi- sation of the portfolio is implemented to be compared with the performance of the classical solution and its denoised counterpart. The results are evalu- ated in a controlled environment of Monte Carlo simulation as well as using empirical data from S&P 500 constituents. 1

Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-09-27T18:02:45Z No. of bitstreams: 2 Dissertação - Eric Gomes Arrais Cavalcante - 2016.pdf: 2072393 bytes, checksum: c41dbeb585036af1c9bb4448250b6edd (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-09-28T12:29:27Z (GMT) No. of bitstreams: 2 Dissertação - Eric Gomes Arrais Cavalcante - 2016.pdf: 2072393 bytes, checksum: c41dbeb585036af1c9bb4448250b6edd (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-09-28T12:29:27Z (GMT). No. of bitstreams: 2 Dissertação - Eric Gomes Arrais Cavalcante - 2016.pdf: 2072393 bytes, checksum: c41dbeb585036af1c9bb4448250b6edd (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-08-22 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / Results from classical Random Matrix Theory (RMT) are well recognized as a way to describe spectral statistical properties of classically chaotic quantum systems, such as the level spacing distribution. We investigate, both numerically and analytically, if RMT can be used, at least for some regimes, to predict the behavior of the statistics of work performed by quenching some external parameter dictating the dynamics of a quantum chaotic system. This is done by comparison of the characteristic function of work obtained numerically from a well known quantum chaotic system called Dicke Model and from matrices pertaining to one of the classical ensembles of RMT, namely GOE. We also show one analytical result for the RMT average of the characteristic function that holds in the limit of high temperatures. / É reconhecido que a teoria de matrizes aleatórias (RMT) é capaz de descrever corretamente o comportamento de propriedades estatísticas espectrais de sistemas quânticos classicamente caóticos, como, por exemplo, suas distribuições de espaçamento de níveis. Investigamos, tanto numericamente quanto analiticamente, se a RMT pode ser usada, ao menos em alguns regimes, para predizer o comportamento da estatística do trabalho realizado ao se realizar um quench sobre um parâmetro externo que dita a dinâmica de um sistema quântico caótico. Isso é feito através da comparação da função característica do trabalho obtida numericamente a partir de um sistema quântico caótico bem conhecido, chamado modelo de Dicke, com a obtida a partir de matrizes pertencentes a um dos ensembles clássicos da RMT, chamado GOE. Mostramos também um resultado analítico para a média RMT da função característica que é válida para o limite de altas temperaturas.

Le résultat principal de cette thèse est une formule asymptotique pour le quatrième moment des fonctions L automorphes de niveau p', où p est un nombre premier et v-x. Il prolonge le travail de Rouymi, qui a calculé les trois premiers moments de niveau p, et il généralise les résultats obtenus en niveau premier par Duke, Friedlander & Iwaniec et Kowalski, Michel & Vanderkam. / The main result of this dissertation is an asymptotic formula for the fourth moment of automorphic L-functions of prime power level p, v-x. This is a continuation of the work of Rouymi, who computed the first three moments at prime power level, and a generalisation of results obtained for prime level by Duke, Friedlander & Iwaniec and Kowalski, Michel & Vanderkam.

Graph signal processing analyzes signals supported on the nodes of a network with respect to a shift operator matrix that conforms to the graph structure. For shift-invariant graph filters, which are polynomial functions of the shift matrix, the filter response is defined by the value of the filter polynomial at the shift matrix eigenvalues. Thus, information regarding the spectral decomposition of the shift matrix plays an important role in filter design. However, under stochastic conditions leading to uncertain network structure, the eigenvalues of the shift matrix become random, complicating the filter design task. In such case, empirical distribution functions built from the random matrix eigenvalues may exhibit deterministic limiting behavior that can be exploited for problems on large-scale random networks. Acceleration filters for distributed average consensus dynamics on random networks provide the application covered in this thesis work. The thesis discusses methods from random matrix theory appropriate for analyzing adjacency matrix spectral asymptotics for both directed and undirected random networks, introducing relevant theorems. Network distribution properties that allow computational simplification of these methods are developed, and the methods are applied to important classes of random network distributions. Subsequently, the thesis presents the main contributions, which consist of optimization problems for consensus acceleration filters based on the obtained asymptotic spectral density information. The presented methods cover several cases for the random network distribution, including both undirected and directed networks as well as both constant and switching random networks. These methods also cover two related optimization objectives, asymptotic convergence rate and graph total variation.

Le "Big Data'' et les grands systèmes d'apprentissage sont omniprésents dans les problèmes d'apprentissage automatique aujourd’hui. Contrairement à l'apprentissage de petite dimension, les algorithmes d'apprentissage en grande dimension sont sujets à divers phénomènes contre-intuitifs et se comportent de manière très différente des intuitions de petite dimension sur lesquelles ils sont construits. Cependant, en supposant que la dimension et le nombre des données sont à la fois grands et comparables, la théorie des matrices aléatoires (RMT) fournit une approche systématique pour évaluer le comportement statistique de ces grands systèmes d'apprentissage, lorsqu'ils sont appliqués à des données de grande dimension. L’objectif principal de cette thèse est de proposer un schéma d'analyse basé sur la RMT, pour une grande famille de systèmes d’apprentissage automatique: d'évaluer leurs performances, de mieux les comprendre et finalement les améliorer, afin de mieux gérer les problèmes de grandes dimensions aujourd'hui.Précisément, nous commençons par exploiter la connexion entre les grandes matrices à noyau, les projection aléatoires non-linéaires et les réseaux de neurones aléatoires simples. En considérant que les données sont tirées indépendamment d'un modèle de mélange gaussien, nous fournissons une caractérisation précise des performances de ces systèmes d'apprentissage en grande dimension, exprimée en fonction des statistiques de données, de la dimensionnalité et, surtout, des hyper-paramètres du problème. Lorsque des algorithmes d'apprentissage plus complexes sont considérés, ce schéma d'analyse peut être étendu pour accéder à de systèmes d'apprentissage qui sont définis (implicitement) par des problèmes d'optimisation convexes, lorsque des points optimaux sont atteints. Pour trouver ces points, des méthodes d'optimisation telles que la descente de gradient sont régulièrement utilisées. À cet égard, dans le but d'avoir une meilleur compréhension théorique des mécanismes internes de ces méthodes d'optimisation et, en particulier, leur impact sur le modèle d'apprentissage, nous évaluons aussi la dynamique de descente de gradient dans les problèmes d'optimisation convexes et non convexes.Ces études préliminaires fournissent une première compréhension quantitative des algorithmes d'apprentissage pour le traitement de données en grandes dimensions, ce qui permet de proposer de meilleurs critères de conception pour les grands systèmes d’apprentissage et, par conséquent, d'avoir un gain de performance remarquable lorsqu'il est appliqué à des jeux de données réels. Profondément ancré dans l'idée d'exploiter des données de grandes dimensions avec des informations répétées à un niveau "global'' plutôt qu'à un niveau "local'', ce schéma d'analyse RMT permet une compréhension renouvelée et la possibilité de contrôler et d'améliorer une famille beaucoup plus large de méthodes d'apprentissage automatique, ouvrant ainsi la porte à un nouveau schéma d'apprentissage automatique pour l'intelligence artificielle. / Large dimensional data and learning systems are ubiquitous in modern machine learning. As opposed to small dimensional learning, large dimensional machine learning algorithms are prone to various counterintuitive phenomena and behave strikingly differently from the low dimensional intuitions upon which they are built. Nonetheless, by assuming the data dimension and their number to be both large and comparable, random matrix theory (RMT) provides a systematic approach to assess the (statistical) behavior of these large learning systems, when applied on large dimensional data. The major objective of this thesis is to propose a full-fledged RMT-based framework for various machine learning systems: to assess their performance, to properly understand and to carefully refine them, so as to better handle large dimensional problems that are increasingly needed in artificial intelligence applications.Precisely, we exploit the close connection between kernel matrices, random feature maps, and single-hidden-layer random neural networks. Under a simple Gaussian mixture modeling for the input data, we provide a precise characterization of the performance of these large dimensional learning systems as a function of the data statistics, the dimensionality, and most importantly the hyperparameters (e.g., the choice of the kernel function or activation function) of the problem. Further addressing more involved learning algorithms, we extend the present RMT analysis framework to access large learning systems that are implicitly defined by convex optimization problems (e.g., logistic regression), when optimal points are assumed reachable. To find these optimal points, optimization methods such as gradient descent are regularly used. Aiming to have a better theoretical grasp of the inner mechanism of optimization methods and their impact on the resulting learning model, we further evaluate the gradient descent dynamics in training convex and non-convex objects.These preliminary studies provide a first quantitative understanding of the aforementioned learning algorithms when large dimensional data are processed, which further helps propose better design criteria for large learning systems that result in remarkable gains in performance when applied on real-world datasets. Deeply rooted in the idea of mining large dimensional data with repeated patterns at a global rather than a local level, the proposed RMT analysis framework allows for a renewed understanding and the possibility to control and improve a much larger range of machine learning approaches, and thereby opening the door to a renewed machine learning framework for artificial intelligence.

Massive MIMO systems are shown to be a promising technology for next generations of wireless communication networks. The realization of the attractive merits promised by massive MIMO systems requires advanced linear precoding and receiving techniques in order to mitigate the interference in downlink and uplink transmissions. This work considers the precoder and receiver design in massive MIMO systems. We first consider the design of the linear precoder and receiver that maximize the minimum signal-to-interference-plus-noise ratio (SINR) subject to a given power constraint. The analysis is carried out under the asymptotic regime in which the number of the BS antennas and that of the users grow large with a bounded ratio. This allows us to leverage tools from random matrix theory in order to approximate the parameters of the optimal linear precoder and receiver by their deterministic approximations. Such a result is of valuable practical interest, as it provides a handier way to implement the optimal precoder and receiver. To reduce further the complexity, we propose to apply the truncated polynomial expansion (TPE) concept on a per-user basis to approximate the inverse of large matrices that appear on the expressions of 4 the optimal linear transceivers. Using tools from random matrix theory, we determine deterministic approximations of the SINR and the transmit power in the asymptotic regime. Then, the optimal per-user weight coefficients that solve the max-min SINR problem are derived. The simulation results show that the proposed precoder and receiver provide very close to optimal performance while reducing significantly the computational complexity. As a second part of this work, the TPE technique in a per-user basis is applied to the optimal linear precoding that minimizes the transmit power while satisfying a set of target SINR constraints. Due to the emerging research field of green cellular networks, such a problem is receiving increasing interest nowadays. Closed form expressions of the optimal parameters of the proposed low complexity precoding for power minimization are derived. Numerical results show that the proposed power minimization precoding approximates well the performance of the optimal linear precoding while being more practical for implementation.