Cavity and replica methods for the spectral density of sparse symmetric random matrices

Dear Editor,

we would like to resubmit our paper \textit{Cavity and replica methods for the spectral density of sparse symmetric random matrices} for publication in Sci Post Lecture Notes series.

After reviewing our revised version, one of the referees (Report 2 received 25th May 2021) has provided additional comments that we would like to address in this letter.


\begin{enumerate}

\item \textit{After eq. (128), the authors say that the normalization of the spectral density is fulfilled at any order in $1/c$, since the $1/c$ correction is even. It gives
the impression that this is a sufficient condition, which is not really precise. It is more correct to say that normalization implies that the integral of $\rho_1(x)$ over [-2,2] is zero. An analogous counterexample appears in the calculation of the $1/N$ correction to the spectral density of regular random graphs: the $1/N$ correction to the Kesten-McKay distribution is not an even function around $x=0$, but its integral is zero.}

We agree with the referee. To this purpose we have modified the main text after Eq. (128).

\item \textit{Below eq. (164), the authors argue that this equation may cease to be valid above the percolation transition, because of the presence of cycles. If this is correct and the tree-like assumption fails, why does the spectral density is well captured by the cavity equations above percolation? Besides that, there is plenty of evidence in other fields (spin-glasses, information science, etc) that the tree-like assumption holds above the percolation threshold, so the argument of the authors is not really supported by evidence. }

In the paragraph below Eq.\,(164), we did not wish to imply that the cavity method fails entirely above the percolation threshold due to the presence of loops. Indeed its continued usefulness is clearly demonstrated by its ability to capture the spectral density of sparse matrices, as extensively demonstrated and discussed in the review. Instead, what we meant to be saying is that Eq.\,(164), i.e.
\begin{equation}
{\rm Im}\, G(\lambda_\varepsilon)_{ii} = \mathrm{Re}\left[ \frac{1}{\omega_i}\right] = \pi \sum_\alpha \delta_\varepsilon(\lambda-\lambda_\alpha) u_{i\alpha}^2
\end{equation}
may in the $\varepsilon\to0$-limit not allow one to correctly infer the statistics of squared eigenvector components $ u_{i\alpha}^2$, when evaluated using the cavity method in situations where it is only approximate, despite the fact that its summed version
\begin{equation}
\rho_J(\lambda)=\lim_{\varepsilon\to 0^+}\frac{1}{\pi N} \mathrm{Im} \sum_{i=1}^N G(\lambda_\varepsilon)_{ii}
\label{eq:sum_identity}
\end{equation}
apparently does reproduce the spectral density rather well.

This need not be a contradiction, as the sum (2) may very well be robust against the approximations induced by the cavity method (which fails to be exact above the percolation threshold), even though its individual contributions Eq. (1) may not.

One possible, and indeed plausible mechanism is that an approximate evaluation of Eq.\,(1) using the cavity method may --- for quasi-degenerate eigenvalues in the continuous part of the spectrum --- effectively replace the eigenvector components appearing in Eq.\,(1) (and thus (2)) by components of vectors which are in fact superpositions or hybridizations of eigenvectors corresponding to several quasi-degenerate eigenvalues, i.e. by
\begin{equation}
{\rm Im}\, G(\lambda_\varepsilon)_{ii} = \mathrm{Re}\left[ \frac{1}{\omega_i}\right] \simeq \pi \sum_\alpha \delta_\varepsilon(\lambda-\lambda_\alpha) \tilde u_{i\alpha}^2\ ,
\end{equation}
in which the $\tilde u_{i\alpha}$ are linear superpositions of the form $\tilde u_{i\alpha} = \sum_{\mu \in I_\alpha} c_{\mu\alpha} u_{i\alpha}$. Assuming these superpositions to respect normalization, one immediately sees, that such a mechanism can induce even large discrepancies between the $u_{i\alpha}$ and the $\tilde u_{i\alpha}$ while leaving the spectral density as evaluated in terms of Eq. (2) unmodified due to orthonormality of the true eigenvectors.

We have modified the text after Eq.\,(164) to make this issue clearer in the revised manuscript.
\end{enumerate}

We trust that with these clarifications the paper is now ready to be accepted for publication in Sci Post Lecture Notes series.


Yours faithfully,

Vito Antonio Rocco Susca, Pierpaolo Vivo and Reimer K\"uhn