Press "Enter" to skip to content

20 search results for "circular law"

Spectrum of non-Hermitian heavy tailed random matrices

Spectrum and its module for a single realization of A:=X/n^(1/a) when the law F of Xij is the law of (Uniform^(-1/a)-1)*Rademacher, with n=5000 and a=1. Click to get the GNU Octave code.

I have recently uploaded the paper arXiv:1006.1713 [math.PR] entitled Spectrum of non-Hermitian heavy tailed random matrices, written in collaboration with Charles Bordenave and Pietro Caputo.

We provide a rigorous analysis of the phenomenon behind the pictures above. Let \( {(X_{jk})_{j,k\geq1}} \) be i.i.d. complex random variables with cumulative distribution function \( {F} \). Our main result is a heavy tailed counterpart of Girko’s circular law when \( {F} \) has an infinite second moment. Roughly, if \( {F} \) is in the attraction domain of an \( {\alpha} \)-stable law, with \( {0<\alpha<2} \), then we prove that there exist a deterministic sequence \( {a_n\sim n^{1/\alpha}} \) and a probability measure \( {\mu_\alpha} \) on \( {\mathbb{C}} \) depending only on \( {\alpha} \) such that with probability one, the empirical distribution of the eigenvalues of the rescaled matrix \( {(a_n^{-1}X_{jk})_{1\leq j,k\leq n}} \) converges weakly to \( {\mu_\alpha} \) as \( {n\rightarrow\infty} \). Our approach combines Aldous & Steele’s objective method with Girko’s Hermitization using logarithmic potentials. The underlying limiting object is defined on a bipartized version of Aldous’ Poisson Weighted Infinite Tree. Recursive relations on the tree provide some properties of \( {\mu_\alpha} \). In contrast with the Hermitian and Hermitized cases, we find that \( {\mu_\alpha} \) is not heavy tailed.

Let us first recall that the eigenvalues of an \( {n\times n} \) complex matrix \( {M} \) are the roots in \( {\mathbb{C}} \) of its characteristic polynomial. We label them \( {\lambda_1(M),\ldots,\lambda_n(M)} \) with non growing modules and growing phases. We also denote by \( {s_1(M)\geq\cdots\geq s_n(M)} \) the singular values of \( {M} \), defined for every \( {1\leq k\leq n} \) by \( {s_k(M):=\lambda_k(\sqrt{MM^*})} \). We define the empirical spectral measure and the empirical singular values measure as

\[ \mu_M = \frac 1 n \sum_{k=1} ^n \delta_{\lambda_k (M)} \quad \text{and } \quad \nu_M = \frac 1 n \sum_{k=1} ^n \delta_{s_k (M)}. \]

Let us define the \( {n\times n} \) random matrix \( {X = (X_{ij}) _{ 1 \leq i, j \leq n}} \). Following Dozier and Silverstein, if \( {F} \) has finite positive variance \( {\sigma^2} \), then for every \( {z\in\mathbb{C}} \), there exists a probability measure \( {\mathcal{Q}_{\sigma,z}} \) on \( {[0,\infty)} \) depending only on \( {\sigma} \) and \( {z} \), with explicit Cauchy-Stieltjes transform, such that a.s. (almost surely)

\[ \nu_{\frac{1}{\sqrt{n}}X-zI} \underset{n\rightarrow\infty}{\rightsquigarrow} \mathcal{Q}_{\sigma,z} \ \ \ \ \ (1) \]

where \( {\rightsquigarrow} \) denotes the weak convergence of probability measures. The proof of (1) is based on a classical approach for Hermitian random matrices with bounded second moment: truncation, centralization, recursion on the resolvent, and cubic equation for the limiting Cauchy-Stieltjes transform (fixed point characterization). In the special case \( {z=0} \), the statement (1) reduces to the quartercircular law theorem (square version of the Marchenko-Pastur theorem (see e.g. Marchenko and Pastur, Wachter, Yin) and the probability measure \( {Q_{\sigma,0}} \) is the quartercircular law with Lebesgue density

\[ x\mapsto \frac{1}{\pi\sigma^2}\sqrt{4\sigma^2-x^2}\mathbf{1}_{[0,2\sigma]}(x). \ \ \ \ \ (2) \]

Girko’s famous circular law theorem states under the same assumptions that a.s.

\[ \mu_{\frac{1}{\sqrt{n}}X} \underset{n\rightarrow\infty}{\rightsquigarrow} \mathcal{U}_\sigma \ \ \ \ \ (3) \]

where \( {\mathcal{U}_\sigma} \) is the uniform law on the disc \( {\{z\in\mathbb{C};|z|\leq\sigma\}} \). This statement was established through a long sequence of partial results Mehta, Girko, Silverstein, Edelman, Girko, Bai, Girko, Bai and Silverstein, Pan and Zhou, Götze and Tikhomirov, Tao and Vu, the general case (3) being finally obtained by Tao and Vu, by using Girko’s Hermitization with logarithmic potentials and uniform integrability, the convergence (1), and polynomial bounds on the extremal singular values. The idea of using directly logarithmic potentials was already present in the work of Goldsheid and Khoruzhenko for non-Hermitian random tridiagonal matrices.

The aim of our work is to investigate what happens when \( {F} \) does not have a finite second moment. We shall consider the following hypothesis:

  • (H1) there exists a slowly varying function \( {L} \) (i.e. \( {\lim_{t\rightarrow\infty}L(x\,t)/L(t) = 1} \) for any \( {x>0} \)) and a real number \( {\alpha\in(0,2)} \) such that for every \( {t\geq1} \)

    \[ \mathbb{P} ( |X_{11}| \geq t ) = \int_{\{z\in\mathbb{C};|z| \geq t\}}\!dF(z) = L(t)t^{-\alpha}, \]

    and there exists a probability measure \( {\theta} \) on the unit circle \( {\mathbb{S}^1:=\{z\in\mathbb{C};|z|=1\}} \) of the complex plane such that for every Borel set \( {D\subset \mathbb{S}^1} \),

    \[ \lim_{t \rightarrow \infty} \mathbb{P} \left( \frac{X_{11}}{|X_{11}|} \in D \Bigm| |X_{11} | \geq t \right) = \theta(D). \]

Assumption (H1) states a complex version of the classical criterion for the domain of attraction of a real \( {\alpha} \)-stable law, see e.g. theorem IX.8.1a in Feller’s book. For instance, if \( {X_{11}=V_1+iV_2} \) with \( {i=\sqrt{-1}} \) and where \( {V_1} \) and \( {V_2} \) are independent real random variables both belonging to the domain of attraction of an \( {\alpha} \)-stable law then (H1) holds. When (H1) holds, we define the sequence

\[ a_n := \inf\{a > 0 \text{ s.t. } n \mathbb{P}(|X_{11}| \geq a) \leq 1\} \]

and (H1) implies that

\[ \lim_{n\rightarrow\infty}n \mathbb{P}(|X_{11}| \geq a_n ) = \lim_{n\rightarrow\infty} n a_n^{-\alpha} L(a_n)=1. \]

It follows then classically that for every \( {n\geq1} \)

\[ a_n = n^{1/\alpha}\ell(n) \]

for some slowly varying function \( {\ell} \). The additional possible assumptions on \( {F} \) to be considered in the sequel are the following:

  • (H2) \( {\mathbb{P}(|X_{11}|\geq t) \sim_{t \rightarrow \infty} c\, t^{-\alpha}} \) for some \( {c>0} \) (this implies \( {a_n\sim_{n\rightarrow\infty}c^{1/\alpha}n^{1/\alpha}} \))
  • (H3) \( {X_{11}} \) has a bounded probability Lebesgue density on \( {\mathbb{R}} \) or on \( {\mathbb{C}} \).

One can check that (H1-H2-H3) hold e.g. when the module \( {|X_{11}|} \) and the phase \( {X_{11}/|X_{11}|} \) are independent with \( {|X_{11}|=|S|} \) where \( {S} \) is real symmetric \( {\alpha} \)-stable and the phase follows a Dirac mass or an absolutely continuous law. Another basic example is given by \( {X_{11}=\varepsilon W^{-1/\alpha}} \) with \( {\varepsilon} \) and \( {W} \) independent such that \( {\varepsilon} \) takes values in \( {\{-1,1\}} \) and \( {W} \) is uniform on \( {[0,1]} \).

For every \( {n\geq1} \), let us define the i.i.d. \( {n\times n} \) complex matrix \( {A =A_n} \) by

\[ A_{ij} := a_n ^{-1}X_{ij} \ \ \ \ \ (4) \]

for every \( {1\leq i,j\leq n} \). Our first result concerns the singular values of \( {A-zI} \), \( {z\in\mathbb{C}} \).

Theorem 1 (Singular values) If (H1) holds then for all \( {z \in \mathbb{C}} \), there exists a probability measure \( {\nu_{\alpha,z}} \) on \( {[0,\infty)} \) depending only on \( {\alpha} \) and \( {z} \) such that a.s.

\[ \nu_{A-zI} \underset{n\rightarrow\infty}{\rightsquigarrow} \nu_{\alpha,z}. \]

The case \( {z=0} \) was already obtained by Belinschi, Dembo and Guionnet. Theorem 1 is a heavy tailed version of the Dozier and Silverstein theorem (1). Our main results below give a heavy tailed version of Girko’s circular law theorem (3), as well as a non-Hermitian version of Wigner’s theorem for Lévy matrices considered by Bouchaud and Cizeau, Ben Arous and Guionnet, Belinschi, Dembo and Guionnet, and arXiv:0903.3528 [math.PR].

Theorem 2 (Eigenvalues) If (H1-H2-H3) hold then there exists a probability measure \( {\mu_\alpha} \) on \( {\mathbb{C}} \) depending only on \( {\alpha} \) such that a.s.

\[ \mu_{A} \underset{n\rightarrow\infty}{\rightsquigarrow} \mu_\alpha. \]

Theorem 3 (Limiting law) The probability distribution \( {\mu_\alpha} \) from theorem 2 is isotropic and has a continuous density. Its density at \( {z=0} \) equals

\[ \frac{\Gamma(1+2/\alpha)^2\Gamma(1+\alpha/2)^{2/ \alpha}} {2\pi\Gamma(1-\alpha/2)^{2/\alpha}}. \]

Furthermore, up to a multiplicative constant, the density of \( {\mu_\alpha} \) is equivalent, as \( {\left|z\right|\rightarrow\infty} \), to

\[ |z|^{2 ( \alpha – 1) } e^{- \frac{\alpha}{2} |z|^\alpha}. \]

Recall that for a normal matrix (i.e. which commutes with its adjoint), the module of the eigenvalues are equal to the singular values. Theorem 3 reveals a striking contrast between \( {\mu_\alpha} \) and \( {\nu_{\alpha,0}} \). The limiting law of the eigenvalues \( {\mu_{\alpha}} \) has a stretched exponential tail while the limiting law \( {\nu_{\alpha,0}} \) of the singular values is heavy tailed with power exponent \( {\alpha} \), see e.g. Belinschi, Dembo and Guionnet. This does not contradict the identity

\[ \prod_{k=1}^n|\lambda_k(A)|= \prod_{k=1}^ns_k(A) \]

and the Weyl inequalities but it does indicate that \( {A} \) is typically far from being a normal matrix. A similar shrinking phenomenon appears already in the finite second moment case (13): the law of the module under the circular law \( {\mathcal{U}_\sigma} \) has density

\[ r\mapsto 2\sigma^{-2}r\mathbf{1}_{[0,\sigma]}(r) \]

in contrast with the density (2) of the quartercircular law \( {\mathcal{Q}_{\sigma,0}} \) (even the supports differ by a factor \( {2} \)).

The proof of theorem 1 relies on an extension to non-Hermitian matrices of the “objective method” approach developed in arXiv:0903.3528 [math.PR]. More precisely, we build an explicit operator on Aldous’ Poisson Weighted Infinite Tree (PWIT) and prove that it is the local limit of the matrices \( {A_n} \) in an appropriate sense. While Poisson statistics arises naturally as in all heavy tailed phenomena, the fact that a tree structure appears in the limit is roughly explained by the observation that non vanishing entries of the rescaled matrix \( {A_n=a_n^{-1}X} \) can be viewed as the adjacency matrix of a sparse random graph which locally looks like a tree. In particular, the convergence to PWIT is a weighted-graph version of familiar results on the local structure of Erdös-Rényi random graphs. The method relies on the local weak convergence, a notion introduced by Benjamini and Schramm, Aldous and Steele, see also Aldous and Lyons.

The proof of theorem 2 relies on Girko’s Hermitization method with logarithmic potentials, on theorem 1, and on polynomial bounds on the extremal singular values needed to establish a uniform integrability property. This extends the Hermitization method to more general settings, by successfully mixing various arguments already developed in arXiv:0903.3528 [math.PR], arXiv:0808.1502 [math.PR], and by Tao and Vu. Following them, one of the key step will be a lower bound on the distance of a row of the matrix \( {A} \) to a subspace of dimension at most \( {n – n^{1- \gamma}} \), for some small \( {\gamma >0} \). We also use a concentration for empirical spectral distributions in order to obtain the almost sure convergence in the Hermitization.

Girko’s Hermitization method gives a characterization of \( {\mu_\alpha} \) in terms of its logarithmic potential. In our settings, however, this is not convenient to derive properties of the measure \( {\mu_\alpha} \), and our proof of theorem 3 is based on an analysis of a self-adjoint operator on the PWIT and a recursive characterization of the spectral measure from the resolvent of this operator. We develop an efficient machinery to analyze the complex spectral measures which avoids a direct use of the logarithmic potential and the singular values. Our approach builds upon similar methods in the physics literature, e.g. Feinberg and Zee, Gudowska-Nowak, Nowak, and Pappe, and Rogers and Castillo. The Cauchy-Stieltjes transform is based on complex numbers and constitutes an efficient tool for the spectral analysis of Hermitian random matrices. Beyond Hermitian random matrices, a quaternionic version of it may be used. However, for non normal random matrices, this does not work. We propose a new approach based on bipartization, in which the quaternions are replaced by suitable \( {2\times 2} \) matrices.

The derivation of a Markovian version of theorems 1 and 2 is an interesting open problem that will be analyzed elsewhere, see arXiv:0903.3528 [math.PR] for the symmetric case and arXiv:0808.1502 [math.PR] for the light tailed non-symmetric case. It is also tempting to seek for an interpretation of \( {\nu_{\alpha,z}} \) and \( {\mu_\alpha} \) in terms of a sort of graphical free probability theory. With a proper notion of trace, it is possible to define the spectral measure of an operator, see e.g. Brown, Haagerup and Schultz, Lyons, but we do not pursue this goal here. The study of localization of eigenvectors of heavy tailed random matrices is also an interesting problem.

Leave a Comment

Large deviations for random matrices

Matrix

I am not fond of the large deviations industry, but I like very much the Sanov theorem associated to the law of large numbers expressed on empirical distributions. The rate function in this large deviation principle is the Kullback-Leibler relative entropy.  It turns out that a very pleasant Sanov type theorem exists for certain models of random matrices. Namely, let $V:\mathbb{R}\to\mathbb{R}$ be a continuous function such that $\exp(-V)$ is Lebesgue integrable and  $V$ grows faster than the logarithm at infinity. For instance, one may take $V(x)=x^2/2$. Let $H_n$ be a random $n\times n$ Hermitian matrix with Lebesgue density proportional to

$$H\mapsto \exp\left(-n\mathrm{Tr}(V(H))\right).$$

Let $\lambda_{n,1},\ldots,\lambda_{n,n}$ be the eigenvalues of $H_n$. Their ordering  does not matter here. These eigenvalues are real since $H_n$ is Hermitian.  The unitary invariance of the law of $H_n$ allows to show that the law of $\lambda_{n,1},\ldots,\lambda_{n,n}$ , quotiented by the action of the symmetric group, has Lebesgue density proportional to

$$(\lambda_{n,1},\ldots,\lambda_{n,n})\mapsto \exp\left(-\sum_{k=1}^n nV(\lambda_{n,k})\right)\prod_{i\neq j}|\lambda_{n,i}-\lambda_{n,j}|^2$$

which can be rewritten as

$$(\lambda_{n,1},\ldots,\lambda_{n,n})\mapsto \exp\left(-\sum_{k=1}^n nV(\lambda_{n,k})+\frac{1}{2}\sum_{i\neq j}\log|\lambda_{n,i}-\lambda_{n,j}|\right).$$

The Vandermonde determinant comes from the Jacobian of the diagonalization seen as a change of variable (integration over the eigenvectors), and can also be seen as the discriminant (resultant of $P, P’$) of the characteristic polynomial $P$. Let us consider the random counting probability measure of these eigenvalues:

$$L_n:=\frac{1}{n}\sum_{k=1}^n\delta_{\lambda_{n,k}}$$

which is a random element of the convex set $\mathcal{P}$ of probability measures on $\mathbb{R}$. A very nice result due to Ben Arous and Guionnet states that for the topology of the narrow convergence, the sequence $(L_n)_{n\geq1}$ satisfies to a large deviation principle with speed $n^2$ and good rate function $\Phi$ given up to an additive constant by

$$\mu\in\mathcal{P}\mapsto \Phi(\mu):=\int\!V\,d\mu-\int\!\int\!\log|x-y|\,d\mu(x)d\mu(y).$$

In other words, we have for every nice set $A\subset\mathcal{P}$, as $n\to\infty$,

$$\mathbb{P}(L_n\in A)\approx \exp\left(-n^2\inf_{\mu\in A}\Phi(\mu)\right).$$

The second term in the definition of $\Phi(\mu)$ is the logarithmic energy of $\mu$ (minus the Voiculescu free entropy). When $V(x)=x^2/2$, then $H_n$ belongs to the Gaussian Unitary Ensemble and  the Wigner semicircle law is a maximum of this entropy under a second moment constraint, see e.g. the book by Saff and Totik. In particular, since the proof does not involve the underlying almost sure convergence theorem (in contrary to the Cramer theorem which involves the law of large numbers), the large deviation principle of Ben Arous and Guionnet yields via the first Borel-Cantelli lemma a new proof of the Wigner theorem.

In my opinion (I have a mathematical physicist soul!) the large deviation principle of Ben Arous and Guionnet is one of the nicest results in random matrix theory. It explains the appearance of the Wigner semicircle law in the Wigner theorem via a maximum entropy or minimum energy under moments constraints. Unfortunately, the result is only available for unitary invariant ensembles and does not cover the case of non Gaussian Wigner matrices with i.i.d. entries, for which the Wigner theorem is still valid. It is tempting to seek for a version of this large deviation principle for such non Gaussian Wigner matrices. The answer is not known. It is not clear that the sole finite positive variance assumption is enough to ensure that the rate function is the one of the Gaussian Unitary Ensemble. It is probable that the rate function will depend on the law of the entries. However, the arg-infimum of this function is still the Wigner semicircle law.

The proof of Ben Arous and Guionnet relies crucially on the explicit knowledge of the law of the spectrum, due to the unitary invariance of the model (roughly, if one puts the Vandermonde determinant into the exponential as a potential, it looks like a discrete Voiculescu entropy). Ben Arous and Zeitouni have used essentially the same method in order to establish a large deviation principle for the non-Hermitian version of the model, yielding a new proof of the circular law theorem for the Ginibre Ensemble.

It could be nice to connect these large deviations principles with transport inequalities. For connections between these two universes, take a look at the recent survey by Gozlan and Leonard.

4 Comments

Logarithmic potential and Hermitization

The logarithmic potential is a classical object of potential theory intimately connected with the two dimensional Laplacian. It appears also in free probability theory via the free entropy, and in partial differential equations e.g. Patlak-Keller-Segel models. This post concerns only it usage for the spectra of non Hermitian random matrices.

Let \( {\mathcal{P}(\mathbb{C})} \) be the set of probability measures on \( {\mathbb{C}} \) which integrate \( {\log\left|\cdot\right|} \) in a neighborhood of infinity. For every \( {\mu\in\mathcal{P}(\mathbb{C})} \), the logarithmic potential \( {U_\mu} \) of \( {\mu} \) on \( {\mathbb{C}} \) is the function

\[ U_\mu:\mathbb{C}\rightarrow(-\infty,+\infty] \]

defined for every \( {z\in\mathbb{C}} \) by

\[ U_\mu(z)=-\int_{\mathbb{C}}\!\log|z-z’|\,\mu(dz’) =-(\log\left|\cdot\right|*\mu)(z). \ \ \ \ \ (1) \]

This integral in well defined in \( {(-\infty,+\infty]} \) thanks to the assumption \( {\mu\in\mathcal{P}(\mathbb{C})} \). Note that \( {U_\mu(z)=+\infty} \) if \( {\mu} \) has an atom at point \( {z} \). For the circular law \( {\mathcal{U}_\sigma} \) of density

\[ (\sigma^2\pi)^{-1}\mathbf{1}_{\{z\in\mathbb{C}:|z|\leq\sigma\}} \]

we have, for all \( {z\in\mathbb{C}} \), the remarkable formula

\[ U_{\mathcal{U}_\sigma}(z)= \begin{cases} \log(\sigma)-\log|z\sigma^{-1}| & \text{if } |z|>\sigma, \\ \log(\sigma)-\frac{1}{2}(|z\sigma^{-1}|^2-1) & \text{if } |z|\leq\sigma, \end{cases} \ \ \ \ \ (2) \]

see e.g. the book of Saff and Totik. Let \( {\mathcal{D}'(\mathbb{C})} \) be the set of Schwartz-Sobolev distributions (generalized functions). Since \( {\log\left|\cdot\right|} \) is Lebesgue locally integrable on \( {\mathbb{C}} \), one can check by using the Fubini theorem that \( {U_\mu} \) is Lebesgue locally integrable on \( {\mathbb{C}} \). In particular,

\[ U_\mu<\infty \]

Lebesgue almost everywhere (a.e.), and

\[ U_\mu\in\mathcal{D}'(\mathbb{C}). \]

Since \( {\log\left|\cdot\right|} \) is the fundamental solution of the Laplace equation in \( {\mathbb{C}} \), we have, in \( {\mathcal{D}'(\mathbb{C})} \),

\[ \Delta U_\mu=-2\pi\mu. \ \ \ \ \ (3) \]

In other words, for every smooth and compactly supported “test function” \( {\varphi:\mathbb{C}\rightarrow\mathbb{R}} \),

\[ \int_{\mathbb{C}}\!\Delta\varphi(z)U_\mu(z)\,dz =-2\pi\int_{\mathbb{C}}\!\varphi(z)\,\mu(dz). \]

The identity (3) means that \( {\mu\mapsto U_\mu} \) in the distributional Green potential of the Laplacian in \( {\mathbb{C}} \). The function \( {U_\mu} \) contains enough information to recover \( {\mu} \):

Lemma 1 (Unicity) For every \( {\mu,\nu\in\mathcal{P}(\mathbb{C})} \), if \( {U_\mu=U_\nu} \) a.e. then \( {\mu=\nu} \).

Proof: Since \( {U_\mu=U_\nu} \) in \( {\mathcal{D}'(\mathbb{C})} \), we get \( {\Delta U_\mu=\Delta U_\nu} \) in \( {\mathcal{D}'(\mathbb{C})} \). Now (3) gives \( {\mu=\nu} \) in \( {\mathcal{D}'(\mathbb{C})} \), and thus \( {\mu=\nu} \) as measures since \( {\mu} \) and \( {\nu} \) are Radon measures. ☐

Let \( {A} \) be an \( {n\times n} \) complex matrix. We define the discrete probability measure on \( {\mathbb{C}} \)

\[ \mu_A:=\frac{1}{n}\sum_{k=1}^n\delta_{\lambda_k(A)} \]

where \( {\lambda_1(A),\ldots,\lambda_n(A)} \) are the eigenvalues of \( {A} \), i.e. the roots in \( {\mathbb{C}} \) of its characteristic polynomial \( {P_A(z):=\det(A-zI)} \). We also define the discrete probability measure on \( {[0,\infty)} \)

\[ \nu_A:=\frac{1}{n}\sum_{k=1}^n\delta_{s_k(A)} \]

where \( {s_1(A),\ldots,s_n(A)} \) are the singular values of \( {A} \), i.e. the eigenvalues of the positive semidefinite Hermitian matrix \( {\sqrt{AA^*}} \). We have now

\[ U_{\mu_A}(z) =-\int_{\mathbb{C}}\!\log\left| z’-z\right|\,\mu_A(dz’) =-\frac{1}{n}\log\left|\det(A-zI)\right| =-\frac{1}{n}\log\left| P_A(z)\right| \]

for every \( {z\in\mathbb{C}\setminus\{\lambda_1(A),\ldots,\lambda_n(A)\}} \). We have also the alternative expression

\[ U_{\mu_A}(z) =-\frac{1}{n}\log\det(\sqrt{(A-zI)(A-zI)^*}) =-\int_0^\infty\!\log(t)\,\nu_{A-zI}(dt). \ \ \ \ \ (4) \]

The identity (4) bridges the eigenvalues with the singular values, and is at the heart of the following lemma, which allows to deduce the convergence of \( {\mu_A} \) from the one of \( {\nu_{A-zI}} \). The strength of this Hermitization lies in the fact that in contrary to the eigenvalues, one can control the singular values with the entries of the matrix. The price payed here is the introduction of the auxiliary variable \( {z} \) and the uniform integrability. We recall that on a Borel measurable space \( {(E,\mathcal{E})} \), we say that a Borel function \( {f:E\rightarrow\mathbb{R}} \) is uniformly integrable for a sequence of probability measures \( {(\eta_n)_{n\geq1}} \) on \( {E} \) when

\[ \lim_{t\rightarrow\infty}\varlimsup_{n\rightarrow\infty}\int_{\{|f|>t\}}\!|f|\,d\eta_n=0. \ \ \ \ \ (5) \]

We will use this property as follows: if \( {(\eta_n)_{n\geq1}} \) converges weakly to \( {\eta} \) and \( {f} \) is continuous and uniformly integrable for \( {(\eta_n)_{n\geq1}} \) then \( {f} \) is \( {\eta} \)-integrable and \( {\lim_{n\rightarrow\infty}\int\!f\,d\eta_n=\int\!f\,\eta} \). The idea of using Hermitization goes back at least to Girko. However, theorem 2 and lemma 3 below are inspired from the approach of Tao and Vu.

Theorem 2 (Girko Hermitization) Let \( {(A_n)_{n\geq1}} \) be a sequence of complex random matrices where \( {A_n} \) is \( {n\times n} \) for every \( {n\geq1} \), defined on a common probability space. Suppose that for a.a. \( {z\in\mathbb{C}} \), there exists a probability measure \( {\nu_z} \) on \( {[0,\infty)} \) such that a.s.

  • (i) \( {(\nu_{A_n-zI})_{n\geq1}} \) converges weakly to \( {\nu_z} \) as \( {n\rightarrow\infty} \)
  • (ii) \( {\log(\cdot)} \) is uniformly integrable for \( {\left(\nu_{A_n-zI}\right)_{n\geq1}} \)

Then there exists a probability measure \( {\mu\in\mathcal{P}(\mathbb{C})} \) such that

  • (j) a.s. \( {(\mu_{A_n})_{n\geq1}} \) converges weakly to \( {\mu} \) as \( {n\rightarrow\infty} \)
  • (jj) for a.a. \( {z\in\mathbb{C}} \),

    \[ U_\mu(z)=-\int_0^\infty\!\log(t)\,\nu_z(dt). \]

Moreover, if \( {(A_n)_{n\geq1}} \) is deterministic, then the statements hold without the “a.s.”

Proof: Let \( {z} \) and \( {\omega} \) be such that (i-ii) hold. For every \( {1\leq k\leq n} \), define

\[ a_{n,k}:=|\lambda_k(A_n-zI)| \quad\text{and}\quad b_{n,k}:=s_k(A_n-zI) \]

and set \( {\nu:=\nu_z} \). Note that \( {\mu_{A_n-zI}=\mu_{A_n}*\delta_{-z}} \). Thanks to the Weyl inequalities and to the assumptions (i-ii), one can use lemma 3 below, which gives that \( {(\mu_{A_n})_{n\geq1}} \) is tight, that \( {\log\left| z-\cdot\right|} \) is uniformly integrable for \( {(\mu_{A_n})_{n\geq1}} \), and that

\[ \lim_{n\rightarrow\infty}U_{\mu_{A_n}}(z)=-\int_0^\infty\!\log(t)\,\nu_z(dt)=:U(z). \]

Consequently, a.s. \( {\mu\in\mathcal{P}(\mathbb{C})} \) and \( {U_\mu=U} \) a.e. for every adherence value \( {\mu} \) of \( {(\mu_{A_n})_{n\geq1}} \). Now, since \( {U} \) does not depend on \( {\mu} \), by lemma 1, a.s. \( {\left(\mu_{A_n}\right)_{n\geq1}} \) has a unique adherence value \( {\mu} \), and since \( {(\mu_n)_{n\geq1}} \) is tight, \( {(\mu_{A_n})_{n\geq1}} \) converges weakly to \( {\mu} \) by the Prohorov theorem. Finally, by (3), \( {\mu} \) is deterministic since \( {U} \) is deterministic, and (j-jj) hold. ☐

The following lemma is in a way the skeleton of the Girko Hermitization of theorem 2. It states essentially a propagation of a uniform logarithmic integrability for a couple of triangular arrays, provided that a logarithmic majorization holds between the arrays. See arXiv:0808.1502v2 for a proof.

Lemma 3 (Logarithmic majorization and uniform integrability) Let \( {(a_{n,k})_{1\leq k\leq n}} \) and \( {(b_{n,k})_{1\leq k\leq n}} \) be two triangular arrays in \( {[0,\infty)} \). Define the discrete probability measures

\[ \mu_n:=\frac{1}{n}\sum_{k=1}^n\delta_{a_{n,k}} \quad\text{and}\quad \nu_n:=\frac{1}{n}\sum_{k=1}^n\delta_{b_{n,k}}. \]

If the following properties hold

  • (i) \( {a_{n,1}\geq\cdots\geq a_{n,n}} \) and \( {b_{n,1}\geq\cdots\geq b_{n,n}} \) for \( {n\gg1} \),
  • (ii) \( {\prod_{i=1}^k a_{n,i} \leq \prod_{i=1}^k b_{n,i}} \) for every \( {1\leq k\leq n} \) for \( {n\gg1} \),
  • (iii) \( {\prod_{i=k}^n b_{n,i} \leq \prod_{i=k}^n a_{n,i}} \) for every \( {1\leq k\leq n} \) for \( {n\gg1} \),
  • (iv) \( {(\nu_n)_{n\geq1}} \) converges weakly to some probability measure \( {\nu} \) as \( {n\rightarrow\infty} \),
  • (v) \( {\log(\cdot)} \) is uniformly integrable for \( {(\nu_n)_{n\geq1}} \),

then

  • (j) \( {(\mu_n)_{n\geq1}} \) is tight,
  • (jj) \( {\log(\cdot)} \) is uniformly integrable for \( {(\mu_n)_{n\geq1}} \),
  • (jjj) we have, as \( {n\rightarrow\infty} \),

    \[ \int_0^\infty\!\log(t)\,\mu_n(dt) =\int_0^\infty\!\log(t)\,\nu_n(dt)\rightarrow\int_0^\infty\!\log(t)\,\nu(dt), \]

and in particular, for every adherence value \( {\mu} \) of \( {(\mu_n)_{n\geq1}} \),

\[ \int_0^\infty\!\log(t)\,\mu(dt)=\int_0^\infty\!\log(t)\,\nu(dt). \]

The logarithmic potential is related to the Cauchy-Stieltjes transform of \( {\mu} \) via

\[ S_\mu(z) :=\int_{\mathbb{C}}\!\frac{1}{z’-z}\,\mu(dz’) =(\partial_x-i\partial_y)U_\mu(z) \quad\text{and thus}\quad (\partial_x+i\partial_y)S_\mu=-2\pi\mu \]

in \( {\mathcal{D}'(\mathbb{C})} \). The term “logarithmic potential” comes from the fact that \( {U_\mu} \) is the electrostatic potential of \( {\mu} \) viewed as a distribution of charges in \( {\mathbb{C}\equiv\mathbb{R}^2} \). The logarithmic energy

\[ \mathcal{E}(\mu) :=\int_{\mathbb{C}}\!U_\mu(z)\,\mu(dz) =-\int_{\mathbb{C}}\int_{\mathbb{C}}\!\log\left| z-z’\right|\,\mu(dz)\mu(dz’) \]

is up to a sign the Voiculescu free entropy of \( {\mu} \) in free probability theory. The circular law \( {\mathcal{U}_\sigma} \) minimizes \( {\mu\mapsto\mathcal{E}(\mu)} \) under a second moment constraint. In the spirit of (4) and beyond matrices, the Brown spectral measure of a nonnormal bounded operator \( {a} \) is

\[ \mu_a:=(-4\pi)^{-1}\Delta\int_0^\infty\!\log(t)\,\nu_{a-zI}(dt) \]

where \( {\nu_{a-zI}} \) is the spectral distribution of the self-adjoint operator \( {(a-zI)(a-zI)^*} \). Due to the logarithm, the Brown spectral measure \( {\mu_a} \) depends discontinuously on the \( {*} \)-moments of \( {a.} \) For random matrices, this problem is circumvented in the Girko Hermitization by requiring a uniform integrability, which turns out to be a.s. satisfied for random matrices with i.i.d. entries with finite positive variance.

Leave a Comment

Eigenvectors universality for random matrices

Let $(X_{jk})_{j,k\geq1}$ be an infinite table of complex random variables and set $X:=(X_{j,k})_{1\leq j,k\leq n}$. If $X_{11}$ is Gaussian then $X$ belongs to the so called Ginibre Ensemble. Consider the random unitary matrices $U$ and $V$ such that $X=UDV$ where $D=\mathrm{diag}(s_1,\ldots,s_n)$ and where $s_1,\ldots,s_n$ are the singular values of $X$, i.e. the eigenvalues of $\sqrt{XX^*}$. When $X_{11}$ is Gaussian, the law of $X$ is rotationally invariant, and the matrices $U$ and $V$ are distributed according to the Haar law on the unitary group $\mathbb{U}_n$. The Gaussian version of the Marchenko-Pastur theorem tells us that with probability one, the counting probability distribution of the singular values, appropriately scaled, tends weakly to the quartercircular  law as $n\to\infty$.

The Marchenko-Pastur theorem is universal in the sense that it holds with the same limit beyond the Gaussian case provided that $X_{11}$ has moments identical to the Gaussian up to the order 2. One can ask if a similar statement holds for the eigenvectors, i.e. for the matrices $U$ and $V$. Are they asymptotically Haar distributed? For instance, one may ask if $W_2(\mathcal{L}(U),\mathrm{Haar}(\mathbb{U}_n))$ tends to zero as $n\to\infty$, where $W_2$ is the Wasserstein coupling distance. The distance choice is important. One may consider  many other distances including for instance the Fourier distance $\sup_g|\Phi_\mu(g)-\Phi_\nu(g)|$ where $\Phi_\mu$ denotes the Fourier transforrm of $\mu$ (characteristic function). A weakened version of this statement consist in asking if linear functionals of $U$ and $V$ behave asymptotically as Brownian bridges. Indeed, it is well known that linear functionals of the Haar law on the unitary group behave asmptotically like this. Silverstein has done some work in this direction. Of course, one can ask the same question for the eigenvectors in the Girko circular law and in the Wigner theorem. One can guess that a finite fourth moment assumption on $X_{11}$ is needed, otherwise the top of the spectrum will blow up and the corresponding eigenvectors will maybe localize.

If you do not trust me, just do simulations or… computations! There is here potentially a whole line of research, sparsely explored for the moment. If you like free probability, you may ask if $U’XV’$ is close to $X$ when $U’$ and $V’$ are Haar distributed and independent of $X$.

There is some literature on the behavior of eigenvectors of deterministic matrices under perturbations of the entries of the matrix, see e.g. the book of Bhatia (ch. VII). Among many results, if $A$ and $B$ are two invertible $n\times n$ complex matrices with respective polar unitary factors $U_A$ and $U_B$ in their polar factorization then for any unitary invariant norm $\left\Vert\cdot\right\Vert$ we have

$\displaystyle\left\Vert U_A-U_B\right\Vert\leq 2\frac{\left\Vert A-B\right\Vert}{\left\Vert A^{-1}\right\Vert^{-1}+\left\Vert B^{-1}\right\Vert^{-1}}.$

The eigenvectors are more sensitive than the bulk of the spectrum to perturbations on $X$, and one may understand this by remembering that for a normal matrix, they are arg-suprema while the eigenvalues are suprema. Also, one can guess that the asymptotic uniformization of the eigenvectors may be even sensitive to the skewness of the law of $X_{11}$.

It is well known that the $k$-dimensional projection of the uniform law on the sphere of $\mathbb{R}^n$ of radius $\sqrt{n}$ tends to the Gaussian law as $n\to\infty$. By viewing $\mathbb{U}_n$ as a bunch of exchangeable spheres, one can guess that the Haar law on the unitary group, appropriately scaled, will converge in some sense to the Brownian sheet bridge as the dimension tends to infinity. Recent addition to this post: this was proved in a paper by Donati-Martin and Rouault! We conjecture that this result is universal for  the eigenvectors matrix of random matrices with i.i.d. entries and moments identical to the Gaussian moments up to order $4$.

The uniformization of the eigenvectors of random matrices is related to their delocalization, a phenomenon recently investigated by Erdös, Schlein, Ramirez, Yau, Tao, Vu, as a byproduct of their analysis of the universality of local statistics of the spectrum. This is a huge contrast with the well known Anderson localization phenomenon in mathematical physics for random Schrödinger operators.

The unitary group $\mathbb{U}_n$ is a purely $\ell^2$ object. Its $\ell^1$ analogue is the Birkhoff polytope of doubly stochastic matrices, also known as the transportation polytope,  assignment polytope, or perfect matching polytope, but this is another story…

This post benefined from discussions with Charles Bordenave and Florent Benaych-Georges.

1 Comment

Can't find what you're looking for? Try refining your search:

Syntax · Style · .