1. Introduction

In the previous post, we saw how to use the replica method to calculate the spectral norm of the spiked GOE matrix. Besides the spectral norm, another interesting quantity of random matrices is the spectral density: the limiting empirical distribution of eigenvalues. In this post, we show how to calculate the spectral density of random matrices using the replica method. Let us take the GOE matrix as an example.

The prerequisite knowledge for this post is Stieltjes transforms. For a basic introduction to Stieltjes transforms and its applications to the GOE matrix, I recommend reading Terrence Tao’s blog. The shape of the spectral density of the GOE matrix is a semicircle, and hence this famous result is called the semicircle law.

2. Spectral density and Stieltjes transforms

Let be a symmetric matrix. Let ( is the imaginary part of ). We denote the resolvent of by

\[ R_{\bA_n}(z) = (\bA_n - z \id_n)^{-1}. \]

Denoting the ‘th largest eigenvalue of by , and the empirical eigenvalue distribution (spectral density) of by \[ \mu_{\bA_n} = \frac{1}{n} \sum_{i=1}^n \delta_{\lambda_i(\bA_n)}. \]

For a probability measure on the real line, we denote its Stieltjes transform by \[ s_{\mu}(z) = \int \frac{1}{\lambda - z} \mu(\de \lambda). \] The next two lemmas characterize the properties of Stieltjes transforms.

[Inverse Stieltjes transforms] The scaled imaginary part of the Stieltjes transform for is a probability measure on the real line . The sequence of probability measures indexed by converges weakly to as .
[Stieltjes continuity] Let be a sequence of random probability measures on the real line, and let be a deterministic probability measure. Then converges in expectation to in the vague topology if and only if converges to for every in the upper half-plane.

The next theorem gives the limiting Stieltjes transform of the GOE matrix. Combining with the two lemmas above, we recover the semicircle law of the GOE matrix.

[Stieltjes transform of the GOE matrix] Let . That is, is a symmetric matrix with and . Denote by the Stieltjes transform of empirical eigenvalue distribution of . Then for , we have \[ \lim_{n \to \infty}\E[s_{\bW_n}(z)] = \frac{-z + \sqrt{z^2 - 4}}{2}. \]

Combining the above theorem with the Stieltjes continuity lemma, for , we have \[ \lim_{n \to \infty} \E[\# \{ \lambda_i(\bW_n): \lambda_i(\bW_n) \in [a, b] \} / n] = \sigma_{\rm sc}([a, b]), \] where \[ \sigma_{\rm sc}(\de x) = \frac{1}{2\pi} \sqrt{4 - x^2} \cdot \ones\{ x \in [-2, 2] \} \de x. \]

In the following sections, I will formally calculate using the replica method.

3. The determinant trick

3.1. The connection of determinant and Stieltjes transform

Let be the complex log function defined on , with branch cut along the negative real axis. Define function as \[ D_{\bW_n}(\xi) = \frac{1}{n} \sum_{i=1}^n \log(\lambda_i(\bW_n) - \xi). \] Then the derivative of gives the negative Stieltjes transform \[ \frac{\de}{\de \xi} D_{\bW_n}(\xi) = - \frac{1}{n} \sum_{i=1}^n \frac{1}{\lambda_i(\bW_n) - \xi} = - s_{\bW_n}(\xi). \] The function is almost the normalized log-determinant of , up to a phase shift \[ D_{\bW_n}(\xi) = \frac{1}{n}\log \det(\bW_n - \xi \id_n) + \frac{2 \pi \bi k(\bW_n, \xi)}{n}, \] where is an integer. Moreover, will remain the same under an infinitesimal change of . Hence we have \begin{align} &~\lim_{n \to \infty} \E[s_{\bW_n}(\xi)] = - \lim_{n \to \infty} \frac{\de}{\de \xi} \E[D_{\bW_n}(\xi)] = - \lim_{n \to \infty} \frac{\de}{\de \xi} \frac{1}{n} \E[\log \det(\bW_n - \xi \id_n)]\nonumber \\ \stackrel{\cdot}{=}&~ - \frac{\de}{\de \xi} \lim_{n \to \infty} \frac{1}{n} \E[\log \det(\bW_n - \xi \id_n)]\tag{1}\label{eq:1} \end{align} In the last step, we heuristically exchanged the limit operator and the differential operator.

Determinants are easier to work with than Stieltjes transforms. The following identity expresses the power of determinant in terms of integration of exponentials \[ \det(\bA)^{-k/2} = \int_{\R^n} \frac{1}{(2 \pi)^{nk/2}} \exp\Big\{ - \frac{1}{2} \sum_{j = 1}^k \langle \bx_j, \bA \bx_j \rangle \Big\} \prod_{j \in [k]} \de \bx_j. \] This identity holds whenever is positive semi-definite. Though, we will formally use this identity for a complex matrix .

3.2. The replica approach

In order to calculate , by Eq. \eqref{eq:1}, we need to calculate , and then differentiate with respect to . However, there is no straightforward way to calculate the expectation of . One possible way is to use the replica formula introduced in my last post \[ \E[\log Z] = \lim_{k \to 0} \frac{1}{k} \log \E[Z^k]. \] The replica formula reduces the problem to calculating the moments .

3.3. An easier approach

Instead of calculating for a sequence of , we just calculate . Note \[ \frac{1}{n} \log \det(\bW_n - \xi \id_n ) = -\frac{2}{n} \log [\det(\bW_n - \xi \id_n)^{-1/2}]. \] We expect that concentrates tightly around its mean, so that \begin{align} &~\lim_{n \to \infty} \frac{1}{n} \E[ \log \det(\bW_n - \xi \id_n)] \stackrel{\cdot}{=} \lim_{n \to \infty} \frac{1}{n}\log \det(\bW_n - \xi \id_n)] \nonumber\\ \stackrel{\cdot}{=}&~ \lim_{n \to \infty} - \frac{2}{n}\log \det(\bW_n - \xi \id_n)^{-1/2}] \stackrel{\cdot}{=} \lim_{n \to \infty} -\frac{2}{n} \log \E[\det(\bW_n - \xi \id_n)^{-1/2}]. \tag{2}\label{eq:2} \end{align} This is completely heuristic, but it finally gives the correct answer.

4. The replica calculations

In this section, we use the replica method to calculate the last expression of Eq. \eqref{eq:2}, and then derive the expression of the limiting Stieltjes transform. We will mostly use formal calculations that are not rigorous.

4.1. Step 1: Get rid of the expectation operator

The first step of the calculation is to get rid of the expectation operator. Suppose we need to calculate , where . First we need to find a way to express as the following integral form \[ f(\bw) = \int_{\R^n} \exp\{ \langle \bw, \bt(\bx)\rangle \} h(\bx) \de \bx, \] such that using the formula of the moment generating function of Gaussian random variables , we get \[ \E[f(\bw)] = \int_{\R^n} \exp\{ \Vert \bt(\bx) \Vert_2^2/2 \} h(\bx) \de \bx. \]

For the current example, note a formal identity gives (it is formal because is a complex matrix)

\[ \det(\bW_n - \xi \id_n)^{-1/2} = \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp\Big\{ - \bx^\sT (\bW_n - \xi \id_n) \bx / 2 \Big\} \de \bx. \]

Let with . Then the distributions of and are identital. As a consequence, we get \[ \begin{aligned} \E[\det(\bW_n - \xi \id_n)^{-1/2}] =&~ \E\Big[ \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp\Big\{ - \Big\langle (\bG + \bG^\sT) / \sqrt {2n} - \xi \id_n, \bx \bx^\sT \Big\rangle / 2 \Big\} \de \bx \Big]\\ =&~ \E\Big[ \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp\Big\{ - \Big\langle \bG , \bx \bx^\sT \Big\rangle / \sqrt {2n} + \xi \Vert \bx \Vert_2^2 /2 \Big\} \de \bx \Big]\\ =&~ \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp\Big\{ \xi \Vert \bx \Vert_2^2 /2 \Big\} \E\Big[\exp\Big\{ - \Big\langle \bG , \bx \bx^\sT \Big\rangle / \sqrt {2n} \Big\}\Big] \de \bx. \end{aligned} \] Using the formula of the moment generating function of Gaussian random variables, we get \begin{align} \E[\det(\bW_n - \xi \id_n)^{-1/2}] =&~ \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp\Big\{ \xi \Vert \bx \Vert_2^2 /2 + \Vert \bx \bx^\sT \Vert_F^2 / (4n) \Big\} \de \bx \nonumber \\ =&~ \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp\Big\{ \xi \Vert \bx \Vert_2^2 /2 + \Vert \bx \Vert_2^4 / (4n) \Big\} \de \bx. \tag{3}\label{eq:3} \\ \end{align} Now, we have got rid of the expectation operator, and expressed the quantity of interest in terms of an integral.

4.2. Step 2: Calculate the integral

Eq. \eqref{eq:3} is an intractable high dimensional integration. In statistical physics, there is a systematic approach to heuristically deal with such an integration.

4.2.1. A systematic approach to deal with the integration

Suppose is an integration of form \[ I_n = \int_{\R^n} \exp\{ n \cdot f(h_1(\bx), \ldots, h_k(\bx)) \} \de \bx, \] where ’s are in the form (with a slight abuse of notation) \[ h_j(x_1, \ldots, x_n) = \frac{1}{n}\sum_{i = 1}^n h_j(x_i). \] First by the identity that \begin{align} \int_\R \delta(n h_j(\bx) - n s_j) \de s_j = 1, \end{align} we have \[ I_n = \int_{\R^k} \prod_{j \in [k]} \de s_j \cdot \exp\{ n \cdot f(s_1, \ldots, s_k) \} \int_{\R^n} \prod_{j \in [k]} \delta( n h_j(\bx) - n s_j) \de \bx. \] Then, by the delta identity formula \[ \delta(x) = \int_{\bi \R} \exp\{ \lambda x \} \de [\lambda/ (2 \pi)], \] we get \[ \begin{aligned} I_n =&~ \int_{\R^k} \prod_{j \in [k]} \de s_j \cdot \exp\{ n \cdot f(s_1, \ldots, s_k) \} \int_{(\bi \R)^k} \prod_{j \in [k]} \de [\lambda_j / (2\pi)] \int_{\R^n} \exp\Big\{ \sum_{j = 1}^k \sum_{i = 1}^n \Big[ \lambda_j h_j(x_i) - \lambda_j s_j \Big] \Big\} \de \bx \\ =&~ \int_{\R^k} \prod_{j \in [k]} \de s_j \int_{(\bi \R)^k} \prod_{j = 1}^k \de [\lambda_j/(2\pi)] \exp \Big\{ n \cdot \Big[ f(s_1, \ldots, s_k) - \sum_{j=1}^k \lambda_j s_j \Big] \Big\} \cdot \Big( \int \exp\Big\{ \sum_{j = 1}^n \lambda_j h_j(x) \Big\} \de x \Big)^n \\ =&~ \int_{\R^k} \prod_{j \in [k]} \de s_j \int_{(\bi \R)^k} \prod_{j = 1}^k \de [\lambda_j/(2\pi)] \exp \Big\{ n \cdot \Big[ f(s_1, \ldots, s_k) - \sum_{j=1}^k \lambda_j s_j + \log J(\lambda_1, \ldots, \lambda_k) \Big] \Big\},\\ \end{aligned} \] where \[ J(\lambda_1, \ldots, \lambda_k) = \int \exp\Big\{ \sum_{j = 1}^n \lambda_j h_j(x) \Big\} \de x. \] Using the method of steepest descent (my understanding is that, it is like the Laplace method but it deals with integration of complex functions), we have \[ \lim_{n \to \infty} n^{-1} \log I_n \stackrel{\cdot}{=} \ext_{s_j, \lambda_j} \Big[ f(s_1, \ldots, s_k) - \sum_{j=1}^k \lambda_j s_j + \log J(\lambda_1, \ldots, \lambda_k) \Big], \] where denotes the extremum operator.

4.2.2. Application to this example

In this example, we need to deal with an integration of form Eq. \eqref{eq:3}. We take and . Using the method introduced above, we have \[ \begin{aligned} \E[\det(\bW_n - \xi \id_n)^{-1/2}] =&~ \int_{\R} \de s \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp\Big\{ \xi \Vert \bx \Vert_2^2 /2 + \Vert \bx \Vert_2^4 / (4n) \Big\} \cdot \delta(\Vert \bx \Vert_2^2 - n s) \de \bx \\ =&~ \int_{\R} \de s \int_{\R^{n}} \frac{1}{(2 \pi)^{n/2}} \exp \{ n \xi s /2 + n s^2 / 4 \} \cdot \delta(\Vert \bx \Vert_2^2 - n s) \de \bx \\ =&~ \int_{\R} \de s \int_{\bi R} [\de \lambda / (2 \pi)] \exp \Big\{ n \Big[\xi s /2 + s^2 / 4 - \lambda s \Big] \Big\} \cdot \Big( \int_R \frac{1}{(2 \pi)^{1/2}} \exp\{ \lambda x^2 \} \de x \Big)^n \\ =&~ \int_{\R} \de s \int_{\bi R} [\de \lambda / (2 \pi)] \exp \Big\{ n \Big[\xi s /2 + s^2 / 4 - \lambda s + J(\lambda) \Big] \Big\} \\ \end{aligned} \] where \[ J(\lambda) = \log \int_R \frac{1}{(2 \pi)^{1/2}} \exp\{ \lambda x^2\} \de x = - \frac{1}{2} \log ( - 2 \lambda). \] Therefore, we have \[ \lim_{n \to \infty} \frac{1}{n} \log \E[\det(\bW_n - \xi \id_n)^{-1/2}] = \ext_{s, \lambda} \Big[ \frac{ \xi s}{2} + \frac{s^2}{4} - \lambda s - \frac{1}{2} \log( - 2\lambda) \Big]. \] Define \[ P(s, \lambda) = \frac{ \xi s}{2} + \frac{s^2}{4} - \lambda s - \frac{1}{2} \log( - 2 \lambda). \] Letting , we have , which gives \[ P(s) \equiv \ext_{\lambda} P(s, \lambda) = \frac{ \xi s}{2} + \frac{s^2}{4} + \frac{1}{2} \log(s) + \frac{1}{2}. \] Then we differentiate , its extremum satisfies \begin{align}\tag{5}\label{eq:5} \xi + s_\star + \frac{1}{s_\star} = 0. \end{align} As a result, we get \[ \lim_{n \to \infty} \frac{1}{n} \log \E[\det(\bW_n - \xi \id_n)^{-1/2}] \stackrel{\cdot}{=} \frac{ \xi s_\star}{2} + \frac{s_\star^2}{4} + \frac{1}{2} \log(s_\star) + \frac{1}{2}, \] and by Eq. \eqref{eq:2} we get \[ \lim_{n \to \infty} \frac{1}{n}\E[\log \det(\bW_n - \xi \id_n)] \stackrel{\cdot}{=} - \xi s_\star - \frac{s_\star^2}{2} - \log(s_\star) - 1. \] where gives the solution of Eq. \eqref{eq:5}. Finally, by Eq. \eqref{eq:1}, we have \[ \begin{aligned} \lim_{n \to \infty} \E[s_{\bW_n}(\xi)] \stackrel{\cdot}{=}&~ - \frac{\de}{\de \xi} \lim_{n \to \infty} \frac{1}{n} \E[ \log \det(\bW_n - \xi \id_n)] \\ =&~ - \frac{\de }{\de \xi} \Big[- \xi s_\star(\xi) - \frac{s_\star^2(\xi)}{2} - \log s_\star(\xi) - 1\Big] = - \frac{\partial }{\partial \xi} \Big[- \xi s - \frac{s^2}{2} - \log s - 1\Big] \Big\vert_{s = s_\star(\xi)} \\ =&~ s_\star(\xi). \end{aligned} \] Let , and finding the solution of Eq. \eqref{eq:5} with positive imaginary part, we get \[ s_\star(\xi) = \frac{- z + \sqrt{z^2 - 4}}{2}. \] This is exactly the limiting Stieltjes transform of the GOE matrix. Of course, to prove rigorously this formula, we need to adopt other techniques.

5. Summary

We showed a systematic approach for formally calculating the spectral density of random matrices. Here is one exercise for the readers: calculating the limiting Stieltjes transform of the empirical covariance matrix of isotropic Gaussian data, where with , in the asymptotic regime as . The spectral density of the empirical covariance matrix, which can be derived from the exercise above, gives the famous Marchenko-Pastur law.

In my next post, I will introduce some applications of the replica method to machine learning.