Equivalence of replica and cavity methods for computing spectra of sparse random matrices

We show by direct calculation that the replica and cavity methods are exactly equivalent for the spectrum of an Erdős-Rényi random graph. We introduce a variational formulation based on the cavity method and use it to find approximate solutions for the density of eigenvalues. We also use this variational method for calculating spectra of sparse covariance matrices.

Figure 1

Density of states for the adjacency matrix of an Erdős-Rényi graph, with average degree $\mu =3$. The solid line shows the result of the numerical diagonalization of a matrix of size $N=1000$, averaged over $75\hspace{0.5em}000$ random realizations. The dotted line is the result of an effective medium approximation, the dot-dashed line is the single-defect approximation, and the dashed line is the single-shell approximation. In the inset, a detail of the density of states around the center of the band is plotted in semilogarithmic scale.

Figure 2

The detail of the left tail of the density of states shown in Fig. 1. The solid line shows the result of numerical diagonalization, the dotted line is the result of effective medium approximation, the dot-dashed line is the single-defect approximation, and the dashed line is the single-shell approximation.

Figure 3

Density of states for the correlation matrix based on a sparse adjacency matrix, for $\alpha =0.3$. The average degree is ${\mu }_A=3$ (dash-dotted line), $5$ (dotted line), and $50$ (dashed line). The full line is the Marčenko-Pastur density (41), i.e., the limit ${\mu }_A\to \infty$.