ﻻ يوجد ملخص باللغة العربية
In this paper we analyze a simple spectral method (EIG1) for the problem of matrix alignment, consisting in aligning their leading eigenvectors: given two matrices $A$ and $B$, we compute $v_1$ and $v_1$ two corresponding leading eigenvectors. The algorithm returns the permutation $hat{pi}$ such that the rank of coordinate $hat{pi}(i)$ in $v_1$ and that of coordinate $i$ in $v_1$ (up to the sign of $v_1$) are the same. We consider a model of weighted graphs where the adjacency matrix $A$ belongs to the Gaussian Orthogonal Ensemble (GOE) of size $N times N$, and $B$ is a noisy version of $A$ where all nodes have been relabeled according to some planted permutation $pi$, namely $B= Pi^T (A+sigma H) Pi $, where $Pi$ is the permutation matrix associated with $pi$ and $H$ is an independent copy of $A$. We show the following zero-one law: with high probability, under the condition $sigma N^{7/6+epsilon} to 0$ for some $epsilon>0$, EIG1 recovers all but a vanishing part of the underlying permutation $pi$, whereas if $sigma N^{7/6-epsilon} to infty$, this method cannot recover more than $o(N)$ correct matches. This result gives an understanding of the simplest and fastest spectral method for matrix alignment (or complete weighted graph alignment), and involves proof methods and techniques which could be of independent interest.
This paper considers the empirical spectral measure of a power of a random matrix drawn uniformly from one of the compact classical matrix groups. We give sharp bounds on the $L_p$-Wasserstein distances between this empirical measure and the uniform
We explore the boundaries of sine kernel universality for the eigenvalues of Gaussian perturbations of large deterministic Hermitian matrices. Equivalently, we study for deterministic initial data the time after which Dysons Brownian motion exhibits
In this work, we examine spectral properties of Markov transition operators corresponding to Gaussian perturbations of discrete time dynamical systems on the circle. We develop a method for calculating asymptotic expressions for eigenvalues (in the z
Let $A$ and $B$ be two $N$ by $N$ deterministic Hermitian matrices and let $U$ be an $N$ by $N$ Haar distributed unitary matrix. It is well known that the spectral distribution of the sum $H=A+UBU^*$ converges weakly to the free additive convolution
The topic of this paper is the typical behavior of the spectral measures of large random matrices drawn from several ensembles of interest, including in particular matrices drawn from Haar measure on the classical Lie groups, random compressions of r