Cavity approach to the first eigenvalue problem in a family of symmetric random sparse matrices

Abstract

A methodology to analyze the properties of the first (largest) eigenvalue and its eigenvector is developed for large symmetric random sparse matrices utilizing the cavity method of statistical mechanics. Under a tree approximation, which is plausible for infinitely large systems, in conjunction with the introduction of a Lagrange multiplier for constraining the length of the eigenvector, the eigenvalue problem is reduced to a bunch of optimization problems of a quadratic function of a single variable, and the coefficients of the first and the second order terms of the functions act as cavity fields that are handled in cavity analysis. We show that the first eigenvalue is determined in such a way that the distribution of the cavity fields has a finite value for the second order moment with respect to the cavity fields of the first order coefficient. The validity and utility of the developed methodology are examined by applying it to two analytically solvable and one simple but non-trivial examples in conjunction with numerical justification.

11 pages, 4 figures, to be presented at IW-SMI2010, Kyoto, March 7-10, 2010

References in corpus (2)

• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Spectra of Sparse Random Matrices

Cited by in corpus (20)

• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Cavity and replica methods for the spectral density of sparse symmetric random matrices
• Finite size correction to the spectrum of regular random graphs: an analytical solution
• Spectra of sparse non-Hermitian random matrices: an analytical solution
• Universality in the spectral and eigenfunction properties of random networks
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• First eigenvalue/eigenvector in sparse random symmetric matrices: influences of degree fluctuation
• Linear stability analysis for large dynamical systems on directed random graphs
• Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations
• Instabilities of complex fluids with partially structured and partially random interactions
• Near-optimal Binary Compressed Sensing Matrix
• Top Eigenpair Statistics for Weighted Sparse Graphs
• Second largest Eigenpair Statistics for Sparse Graphs
• Eigenvalue spectrum of neural networks with arbitrary Hebbian length
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective
• Fat-tailed distribution derived from first eigenvector of symmetric random sparse matrix
• Tail states and unusual localization transition in low-dimensional Anderson model with power-law hopping
• Rare events statistics of random walks on networks: localization and other dynamical phase transitions
• Statistics of the non-zero eigenvalues and singular values of low-rank random matrices with non-negative entries
• Statistical physics of principal minors: Cavity approach