Abstract

Numerous and large dimensional data is now a default setting in modern machine learning (ML). Standard ML algorithms, starting with kernel methods such as support vector machines and graph-based methods like the PageRank algorithm, were however initially designed out of small dimensional intuitions and tend to misbehave, if not completely collapse, when dealing with real-world large datasets. Random matrix theory has recently developed a broad spectrum of tools to help understand this new curse of dimensionality, to help repair or completely recreate the suboptimal algorithms, and most importantly to provide new intuitions to deal with modern data mining.
This monograph primarily aims to deliver these intuitions, by providing a digest of the recent theoretical and applied breakthroughs of random matrix theory into machine learning. Targeting a broad audience, spanning from undergraduate students interested in statistical learning to AI engineers and researchers alike, the mathematical prerequisites to the book are minimal (basics of probability theory, linear algebra and real and complex analysis are sufficient): as opposed to introductory books in the mathematical literature of random matrix theory and large dimensional statistics, the theoretical focus here is restricted to the essential requirements to machine learning applications. These applications range from detection, statistical inference and estimation, to graph- and kernel-based supervised, semi-supervised and unsupervised classification, as well as neural networks: for these, a precise theoretical prediction of the algorithm performance (often inaccessible when not resorting to a random matrix analysis), large dimensional insights, methods of improvement, along with a fundamental justification of the wide-scope applicability of the methods to real data, are provided.
Most methods, algorithms, and figure proposed in the monograph are coded in MATLAB and Python and made available to the readers (github.com/Zhenyu-LIAO/RMT4ML). The monograph also contains a series of exercises of two types: short exercises with corrections appended to the end of the book to familiarize the reader with the basic theoretical notions and tools in random matrix analysis, as well as long guided exercises to apply these tools to further concrete machine learning applications.

Abstract

Blending theoretical results with practical applications, this book provides an introduction to random matrix theory and shows how it can be used to tackle a variety of problems in wireless communications. The Stieltjes transform method, free probability theory, combinatoric approaches, deterministic equivalents and spectral analysis methods for statistical inference are all covered from a unique engineering perspective. Detailed mathematical derivations are presented throughout, with thorough explanation of the key results and all fundamental lemmas required for the reader to derive similar calculus on their own. These core theoretical concepts are then applied to a wide range of real-world problems in signal processing and wireless communications, including performance analysis of CDMA, MIMO and multi-cell networks, as well as signal detection and estimation in cognitive radio networks. The rigorous yet intuitive style helps demonstrate to students and researchers alike how to choose the correct approach for obtaining mathematically accurate results.

Chapter Updates

The book chapters are being constantly updated. Here are the latest of these.

• Chapter 6 - Deterministic equivalents: This chapter will be profoundly changed in the future in order to better introduce the Gaussian tools and to confront it to the Bai-Silverstein approach. Some changes were already implemented. [chapter]
• The statement and proofs of Theorems 6.16-6.17 were incorrect and have been updated.
• Chapter 7 - Spectrum Analysis: A better consistency between the results for the sample covariance matrix and the information plus noise models has been implemented. [chapter]
• The statement of Theorem 7.8 was erroenous and has been updated.
• Chapter 9 - Extreme eigenvalues and eigenspace projections: Formerly called "Extreme Eigenvalues", this chapter was largely revisited. [chapter]
• Many new results concerning the spiked model are introduced.
• The spiked model results are now written in a more consistent manner.
• The method of orthogonal polynomials is pushed further to explain the convergence to the Tracy-Widom law.

List of Typos

Some errors concerning statements of theorems of the 2011 version of the book are listed below.

• Theorem 3.18. The correct expression of $\Theta^2$ is $$\Theta^2=-\log\left(1-\frac{cm_F(-1/x)^{\color{red}2}}{(1+cm_F(-1/x))^2}\right)+\kappa \frac{cm_F(-1/x)^{\color{red}2}}{(1+cm_F(-1/x))^2}.$$
• Theorems 6.14. The entries of ${\bf Y}_N$ have variance $\sigma_{ij}^2/\color{red}n$.
• Theorems 6.16-6.17. The results only hold for $c_i<1$ and $\lim\sup_n c_i<1$, instead of $0\leq c_i\leq 1$ as previously stated.
• Theorem 7.8. The statement was mixed up with the statement of Theorem 7.2. See updates in the new Chapter 7.
• Theorems 9.2-9.3,9.10. Some sign and division symbols are erroneous. See updates in the new Chapter 9.

---