No Outliers in the Spectrum of the Product of Independent Non-Hermitian Random Matrices with Independent Entries

We consider products of independent square random non-Hermitian matrices. More precisely, let \(n\ge 2\) and let \(X_1,\ldots ,X_n\) be independent \(N\times N\) random matrices with independent centered entries (either real or complex with independent real and imaginary parts) with variance \(N^{-1}\). In Götze and Tikhomirov (On the asymptotic spectrum of products of independent random matrices, 2011. arXiv:1012.2710) and O’Rourke and Soshnikov (Electron J Probab 16(81):2219–2245, 2011) it was shown that the limit of the empirical spectral distribution of the product \(X_1\cdots X_n\) is supported in the unit disk. We prove that if the entries of the matrices \(X_1,\ldots ,X_n\) satisfy uniform subexponential decay condition, then the spectral radius of \(X_1\cdots X_n\) converges to 1 almost surely as \(N\rightarrow \infty \).     

Precise large deviations for dependent regularly varying sequences

We study a precise large deviation principle for a stationary regularly varying sequence of random variables. This principle extends the classical results of Nagaev (Theory Probab Appl 14:51–64, 193–208, 1969) and Nagaev (Ann Probab 7:745–789, 1979) for iid regularly varying sequences. The proof uses an idea of Jakubowski (Stoch Proc Appl 44:291–327, 1993; 68:1–20, 1997) in the context of central limit theorems with infinite variance stable limits. We illustrate the principle for stochastic volatility models, real valued functions of a Markov chain satisfying a polynomial drift condition and solutions of linear and non-linear stochastic recurrence equations.     

A quenched invariance principle for non-elliptic random walk in i.i.d. balanced random environment

We consider a random walk on $\mathbb{Z }^d,\ d\ge 2$ , in an i.i.d. balanced random environment, that is a random walk for which the probability to jump from $x\in \mathbb{Z }^d$ to nearest neighbor $x+e$ is the same as to nearest neighbor $x-e$ . Assuming that the environment is genuinely $d$ -dimensional and balanced we show a quenched invariance principle: for $P$ almost every environment, the diffusively rescaled random walk converges to a Brownian motion with deterministic non-degenerate diffusion matrix. Within the i.i.d. setting, our result extend both Lawler’s uniformly elliptic result (Comm Math Phys, 87(1), pp 81–87, 1982/1983) and Guo and Zeitouni’s elliptic result (to appear in PTRF, 2010) to the general (non elliptic) case. Our proof is based on analytic methods and percolation arguments.     

Sparse recovery in probability via <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>-minimization with Weibull random matrices for 0 &lt; <Emphasis Type="Italic">q</Emphasis> ≤ 1

Although Gaussian random matrices play an important role of measurement matrices in compressed sensing, one hopes that there exist other random matrices which can also be used to serve as the measurement matrices. Hence, Weibull random matrices induce extensive interest. In this paper, we first propose the l_2,q robust null space property that can weaken the D-RIP, and show that Weibull random matrices satisfy the l_2,q robust null space property with high probability. Besides, we prove that Weibull random matrices also possess the l _q quotient property with high probability. Finally, with the combination of the above mentioned properties, we give two important approximation characteristics of the solutions to the l _q -minimization with Weibull random matrices, one is on the stability estimate when the measurement noise e ∈ ? ⁿ needs a priori ||e||₂ ≤ ?, the other is on the robustness estimate without needing to estimate the bound of ||e||₂. The results indicate that the performance of Weibull random matrices is similar to that of Gaussian random matrices in sparse recovery.     

Convergence of empirical spectral distributions of large dimensional quaternion sample covariance matrices

In this paper, we establish the limit of empirical spectral distributions of quaternion sample covariance matrices. Motivated by Bai and Silverstein (Spectral analysis of large dimensional random matrices, Springer, New York, 2010) and Mar?enko and Pastur (Matematicheskii Sb, 114:507–536, 1967), we can extend the results of the real or complex sample covariance matrix to the quaternion case. Suppose \(\mathbf X_n = ({x_{jk}^{(n)}})_{p\times n}\) is a quaternion random matrix. For each \(n\), the entries \(\{x_{ij}^{(n)}\}\) are independent random quaternion variables with a common mean \(\mu \) and variance \(\sigma ^2>0\). It is shown that the empirical spectral distribution of the quaternion sample covariance matrix \(\mathbf S_n=n^{-1}\mathbf X_n\mathbf X_n^*\) converges to the Mar?enko–Pastur law as \(p\rightarrow \infty \), \(n\rightarrow \infty \) and \(p/n\rightarrow y\in (0,+\infty )\).     

Singular Values Distribution of Squares of Elliptic Random Matrices and Type B Narayana Polynomials

We consider Gaussian elliptic random matrices X of a size \(N \times N\) with parameter \(\rho \), i.e., matrices whose pairs of entries \((X_{ij}, X_{ji})\) are mutually independent Gaussian vectors with \(\mathbb {E}\,X_{ij} = 0\), \(\mathbb {E}\,X^2_{ij} = 1\) and \(\mathbb {E}\,X_{ij} X_{ji} = \rho \). We are interested in the asymptotic distribution of eigenvalues of the matrix \(W =\frac{1}{N^2} X^2 X^{*2}\). We show that this distribution is determined by its moments, and we provide a recurrence relation for these moments. We prove that the (symmetrized) asymptotic distribution is determined by its free cumulants, which are Narayana polynomials of type B:

$$\begin{aligned} c_{2n} = \sum _{k=0}^n {\left( {\begin{array}{c}n\\ k\end{array}}\right) }^2 \rho ^{2k}. \end{aligned}$$

     

Outliers in the Single Ring Theorem

This text is about spiked models of non-Hermitian random matrices. More specifically, we consider matrices of the type \({\mathbf {A}}+{\mathbf {P}}\), where the rank of \({\mathbf {P}}\) stays bounded as the dimension goes to infinity and where the matrix \({\mathbf {A}}\) is a non-Hermitian random matrix, satisfying an isotropy hypothesis: its distribution is invariant under the left and right actions of the unitary group. The macroscopic eigenvalue distribution of such matrices is governed by the so called Single Ring Theorem, due to Guionnet, Krishnapur and Zeitouni. We first prove that if \({\mathbf {P}}\) has some eigenvalues out of the maximal circle of the single ring, then \({\mathbf {A}}+{\mathbf {P}}\) has some eigenvalues (called outliers) in the neighborhood of those of \({\mathbf {P}}\), which is not the case for the eigenvalues of \({\mathbf {P}}\) in the inner cycle of the single ring. Then, we study the fluctuations of the outliers of \({\mathbf {A}}\) around the eigenvalues of \({\mathbf {P}}\) and prove that they are distributed as the eigenvalues of some finite dimensional random matrices. Such kind of fluctuations had already been shown for Hermitian models. More surprising facts are that outliers can here have very various rates of convergence to their limits (depending on the Jordan Canonical Form of \({\mathbf {P}}\)) and that some correlations can appear between outliers at a macroscopic distance from each other (a fact already noticed by Knowles and Yin in (Ann Probab 42:1980–2031, 2014) in the Hermitian case, but only for non Gaussian models, whereas spiked Gaussian matrices belong to our model and can have such correlated outliers). Our first result generalizes a result by Tao proved specifically for matrices with i.i.d. entries, whereas the second one (about the fluctuations) is new.     

The Green function estimates for strongly elliptic systems of second order

We establish existence and pointwise estimates of fundamental solutions and Green’s matrices for divergence form, second order strongly elliptic systems in a domain $\Omega \subseteq {\mathbb{R}}^n, n \geq 3We establish existence and pointwise estimates of fundamental solutions and Green’s matrices for divergence form, second order strongly elliptic systems in a domain , under the assumption that solutions of the system satisfy De Giorgi-Nash type local H?lder continuity estimates. In particular, our results apply to perturbations of diagonal systems, and thus especially to complex perturbations of a single real equation.     

Fréchet Means for Distributions of Persistence Diagrams

Given a distribution \(\rho \) on persistence diagrams and observations \(X_{1},\ldots ,X_{n} \mathop {\sim }\limits ^{iid} \rho \) we introduce an algorithm in this paper that estimates a Fréchet mean from the set of diagrams \(X_{1},\ldots ,X_{n}\) . If the underlying measure \(\rho \) is a combination of Dirac masses \(\rho = \frac{1}{m} \sum _{i=1}^{m} \delta _{Z_{i}}\) then we prove the algorithm converges to a local minimum and a law of large numbers result for a Fréchet mean computed by the algorithm given observations drawn iid from \(\rho \) . We illustrate the convergence of an empirical mean computed by the algorithm to a population mean by simulations from Gaussian random fields.     

Central Limit Theorems for Random Permanents with Correlation Structure

Central limit theorems for permanents of random m×n matrices of iid columns with a common intercomponent correlation as n–m are derived. The results are obtained by introducing a Hoeffding-like orthogonal decomposition of a random permanent and deriving the variance formulae for a permanent with the homogeneous correlation structure.     

On the Semicircular Law of Large-Dimensional Random Quaternion Matrices

It is well known that the Gaussian symplectic ensemble is defined on the space of \(n\times n\) quaternion self-dual Hermitian matrices with Gaussian random elements. There is a huge body of literature regarding this kind of matrices based on the exact known form of the density function of the eigenvalues (see Erd?s in Russ Math Surv 66(3):507–626, 2011; Erd?s in Probab Theory Relat Fields 154(1–2):341–407, 2012; Erd?s et al. in Adv Math 229(3):1435–1515, 2012; Knowles and Yin in Probab Theory Relat Fields, 155(3–4):543–582, 2013; Tao and Vu in Acta Math 206(1):127–204, 2011; Tao and Vu in Electron J Probab 16(77):2104–2121, 2011). Due to the fact that multiplication of quaternions is not commutative, few works about large-dimensional quaternion self-dual Hermitian matrices are seen without normality assumptions. As in natural, we shall get more universal results by removing the Gaussian condition. For the first step, in this paper, we prove that the empirical spectral distribution of the common quaternion self-dual Hermitian matrices tends to the semicircular law. The main tool to establish the universal result is given as a lemma in this paper as well.     

Optimal lower exponent for the higher gradient integrability of solutions to two-phase elliptic equations in two dimensions

We study the higher gradient integrability of distributional solutions u to the equation \({{\mathrm{div}}}(\sigma \nabla u) = 0\) in dimension two, in the case when the essential range of \(\sigma \) consists of only two elliptic matrices, i.e., \(\sigma \in \{\sigma _1, \sigma _2\}\) a.e. in \(\Omega \). In Nesi et al. (Ann Inst H Poincaré Anal Non Linéaire 31(3):615–638, 2014), for every pair of elliptic matrices \(\sigma _1\) and \(\sigma _2\), exponents \(p_{\sigma _1,\sigma _2}\in (2,+\infty )\) and \(q_{\sigma _1,\sigma _2}\in (1,2)\) have been found so that if \(u\in W^{1,q_{\sigma _1,\sigma _2}}(\Omega )\) is solution to the elliptic equation then \(\nabla u\in L^{p_{\sigma _1,\sigma _2}}_{\mathrm{weak}}(\Omega )\) and the optimality of the upper exponent \(p_{\sigma _1,\sigma _2}\) has been proved. In this paper we complement the above result by proving the optimality of the lower exponent \(q_{\sigma _1,\sigma _2}\). Precisely, we show that for every arbitrarily small \(\delta \), one can find a particular microgeometry, i.e., an arrangement of the sets \(\sigma ^{-1}(\sigma _1)\) and \(\sigma ^{-1}(\sigma _2)\), for which there exists a solution u to the corresponding elliptic equation such that \(\nabla u \in L^{q_{\sigma _1,\sigma _2}-\delta }\), but \(\nabla u \notin L^{q_{\sigma _1,\sigma _2}}\). The existence of such optimal microgeometries is achieved by convex integration methods, adapting to the present setting the geometric constructions provided in Astala et al. (Ann Scuola Norm Sup Pisa Cl Sci 5(7):1–50, 2008) for the isotropic case.     

Invariant theory for the elliptic normal quintic, I. Twists of X(5)

A genus one curve of degree 5 is defined by the $4 \times 4$ Pfaffians of a $5 \times 5$ alternating matrix of linear forms on $\mathbb{P }^4$ . We describe a general method for investigating the invariant theory of such models. We use it to explain how we found our algorithm for computing the invariants and to extend our method for computing equations for visible elements of order 5 in the Tate-Shafarevich group of an elliptic curve. As a special case of the latter we find a formula for the family of elliptic curves 5-congruent to a given elliptic curve in the case the 5-congruence does not respect the Weil pairing. We also give an algorithm for doubling elements in the $5$ -Selmer group of an elliptic curve, and make a conjecture about the matrices representing the invariant differential on a genus one normal curve of arbitrary degree.     

Fluctuation Theory for Markov Random Walks

Two fundamental theorems by Spitzer–Erickson and Kesten–Maller on the fluctuation-type (positive divergence, negative divergence or oscillation) of a real-valued random walk \((S_{n})_{n\ge 0}\) with iid increments \(X_{1},X_{2},\ldots \) and the existence of moments of various related quantities like the first passage into \((x,\infty )\) and the last exit time from \((-\infty ,x]\) for arbitrary \(x\ge 0\) are studied in the Markov-modulated situation when the \(X_{n}\) are governed by a positive recurrent Markov chain \(M=(M_{n})_{n\ge 0}\) on a countable state space \(\mathcal {S}\); thus, for a Markov random walk \((M_{n},S_{n})_{n\ge 0}\). Our approach is based on the natural strategy to draw on the results in the iid case for the embedded ordinary random walks \((S_{\tau _{n}(i)})_{n\ge 0}\), where \(\tau _{1}(i),\tau _{2}(i),\ldots \) denote the successive return times of M to state i, and an analysis of the excursions of the walk between these epochs. However, due to these excursions, generalizations of the aforementioned theorems are surprisingly more complicated and require the introduction of various excursion measures so as to characterize the existence of moments of different quantities.     

Averaging Fluctuations in Resolvents of Random Band Matrices

We consider a general class of random matrices whose entries are centred random variables, independent up to a symmetry constraint. We establish precise high-probability bounds on the averages of arbitrary monomials in the resolvent matrix entries. Our results generalize the previous results of Erd?s et al. (Ann Probab, arXiv:1103.1919, 2013; Commun Math Phys, arXiv:1103.3869, 2013; J Combin 1(2):15–85, 2011) which constituted a key step in the proof of the local semicircle law with optimal error bound in mean-field random matrix models. Our bounds apply to random band matrices and improve previous estimates from order 2 to order 4 in the cases relevant to applications. In particular, they lead to a proof of the diffusion approximation for the magnitude of the resolvent of random band matrices. This, in turn, implies new delocalization bounds on the eigenvectors. The applications are presented in a separate paper (Erd?s et al., arXiv:1205.5669, 2013).     

Some explicit solutions of the additive Deligne-Simpson problem and their applications

In this paper we construct three infinite series and two extra triples (E₈ and ) of complex matrices B, C, and A=B+C of special spectral types associated to Simpson's classification in Amer. Math. Soc. Proc. 1 (1992) 157 and Magyar et al. classification in Adv. Math. 141 (1999) 97. This enables us to construct Fuchsian systems of differential equations which generalize the hypergeometric equation of Gauss-Riemann. In a sense, they are the closest relatives of the famous equation, because their triples of spectral flags have finitely many orbits for the diagonal action of the general linear group in the space of solutions. In all the cases except for E₈, we also explicitly construct scalar products such that A, B, and C are self-adjoint with respect to them. In the context of Fuchsian systems, these scalar products become monodromy invariant complex symmetric bilinear forms in the spaces of solutions.When the eigenvalues of A, B, and C are real, the matrices and the scalar products become real as well. We find inequalities on the eigenvalues of A, B, and C which make the scalar products positive-definite.As proved by Klyachko, spectra of three hermitian (or real symmetric) matrices B, C, and A=B+C form a polyhedral convex cone in the space of triple spectra. He also gave a recursive algorithm to generate inequalities describing the cone. The inequalities we obtain describe non-recursively some faces of the Klyachko cone.     

Improved elliptic curve hashing and point representation

For a large class of functions \(f:\mathbb {F}_q\rightarrow E(\mathbb {F}_q)\) to the group of points of an elliptic curve \(E/\mathbb {F}_q\) (typically obtained from certain algebraic correspondences between E and \(\mathbb {P}^1\)), Farashahi et al. (Math Comput 82(281):491–512, 2013) established that the map \((u,v)\mapsto f(u)+f(v)\) is regular, in the sense that for a uniformly random choice of \((u,v)\in \mathbb {F}_q^2\), the elliptic curve point \(f(u)+f(v)\) is close to uniformly distributed in \(E(\mathbb {F}_q)\). This result has several applications in cryptography, mainly to the construction of elliptic curve-valued hash functions and to the “Elligator Squared” technique by Tibouchi (in: Christin and Safavi-Naini (eds) Financial cryptography. LNCS, vol 8437, pp 139–156. Springer, Heidelberg, 2014) for representating uniform points on elliptic curves as close to uniform bitstrings. In this paper, we improve upon Farashahi et al.’s character sum estimates in two ways: we show that regularity can also be obtained for a function of the form \((u,v)\mapsto f(u)+g(v)\) where g has a much smaller domain than \(\mathbb {F}_q\), and we prove that the functions f considered by Farashahi et al. also satisfy requisite bounds when restricted to large intervals inside \(\mathbb {F}_q\). These improved estimates can be used to obtain more efficient hash function constructions, as well as much shorter “Elligator Squared” bitstring representations.     

Conformally Invariant Elliptic Liouville Equation and Its Symmetry-Preserving Discretization

The symmetry algebra of the real elliptic Liouville equation is an infinite-dimensional loop algebra with the simple Lie algebra o(3, 1) as its maximal finite-dimensional subalgebra. The entire algebra generates the conformal group of the Euclidean plane E₂. This infinite-dimensional algebra distinguishes the elliptic Liouville equation from the hyperbolic one with its symmetry algebra that is the direct sum of two Virasoro algebras. Following a previously developed discretization procedure, we present a difference scheme that is invariant under the group O(3, 1) and has the elliptic Liouville equation in polar coordinates as its continuous limit. The lattice is a solution of an equation invariant under O(3, 1) and is itself invariant under a subgroup of O(3, 1), namely, the O(2) rotations of the Euclidean plane.     

Harnack inequalities on weighted graphs and some applications to the random conductance model

We establish elliptic and parabolic Harnack inequalities on graphs with unbounded weights. As an application we prove a local limit theorem for a continuous time random walk \(X\) in an environment of ergodic random conductances taking values in \((0, \infty )\) satisfying some moment conditions.     

The local circular law III: general case

In the first part (Bourgade et al., Local circular law for random matrices, preprint, arXiv:1206.1449, 2012) of this article series, Bourgade, Yau and the author of this paper proved a local version of the circular law up to the finest scale \(N^{-1/2+ {\varepsilon }}\) for non-Hermitian random matrices at any point \(z \in \mathbb {C}\) with \(||z| - 1| > c \) for any constant \(c>0\) independent of the size of the matrix. In the second part (Bourgade et al., The local circular law II: the edge case, preprint, arXiv:1206.3187, 2012), they extended this result to include the edge case \( |z|-1={{\mathrm{o}}}(1)\) , under the main assumption that the third moments of the matrix elements vanish. (Without the vanishing third moment assumption, they proved that the circular law is valid near the spectral edge \( |z|-1={{\mathrm{o}}}(1)\) up to scale \(N^{-1/4+ {\varepsilon }}\) .) In this paper, we will remove this assumption, i.e. we prove a local version of the circular law up to the finest scale \(N^{-1/2+ {\varepsilon }}\) for non-Hermitian random matrices at any point \(z \in \mathbb {C}\) .