FoCM 2014 conference

Session B6 - Random Matrices

Organizers: Alan Edelman (MIT, USA) - Raj Rao (University of Michigan, USA)

Workshop website

View session abstracts PDF



December 16, 17:00 ~ 17:25 - Room B22

A Rice method proof of the NSP property for a Random matrix

Jean-Marc Azais

Université de Toulouse, France   -

We define the Compressed Sensing condition for exact reconstruction in a linear model with no noise under sparsity condition. We show that it is equivalent to the Null Space property: NSP. Best constructions are obtained for random matrices. For a random design matrix we show the property using random field method an obtain an explicit transition diagram.

View abstract PDF

December 16, 15:35 ~ 16:25 - Room B22

Non-backtracking spectrum of random graphs

Charles Bordenave

University of Toulouse & CNRS, France   -

The non-backtracking matrix of a graph is a non-symmetric matrix on the oriented edge of a graph which has interesting algebraic properties and appears notably in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. It has also been used recently in the context of community detection. In this talk, we will study the largest eigenvalues of this matrix for the Erdos-Renyi graph G(n,c/n) and for simple inhomogeneous random graphs (stochastic block model).

Joint work with Marc Lelarge (INRIA) and Laurent Massoulié (Microsoft & INRIA)..

View abstract PDF

December 17, 17:05 ~ 17:55 - Room B12

New Formulae Relating Finite GOE and LUE --- from Numerical Experiments to Proofs

Folkmar Bornemann

TU München, Germany   -

Gap probabilities of finite-dimensional GOE can be expressed as Pfaffians of single integrals with jump discontinuities that severely bound the effectiveness of quadrature-based numerical methods. Starting from recursive relations with LUE that are either valid in the large matrix limit (due to Metha and Cloizeaux) or hold for every second gap at even dimensions (due to Forrester), we have systematically explored candidates for the "missing" formulae through numerical experiments guided by heuristic arguments. While some of those candidates seem to be exact, other are still surprisingly accurate (and, therefore, probably useful) already for small dimensions even though they are only asymptotically exact. Proving the observed facts is ongoing work.

View abstract PDF

December 17, 15:30 ~ 15:55 - Room B12

Random Matrix Laws and Jacobi Operators

Alan Edelman

MIT, USA   -

The four big asymptotic level density laws of Random Matrix Theory are the semicircle, the Marchenko-Pastur, the McKay, and the Wachter Laws. They correspond to the equilibrium measures for Hermite, Laguerre, Gegenbauer, and Jacobi Polynomials. The associated Jacobi matrix is Toeplitz except for first row and first column. We explore properties of these big laws, and apply the Toeplitz nature in an algorithm for the moment problem. In the second part of this talk, we consider multivariate polynomials orthogonal with respect to the product of scalar weights with the Vandermonde to the beta repulsion term.

Joint work with Alex Dubbs (MIT) and Praveen Venkataramana (MIT).

View abstract PDF

December 15, 15:35 ~ 16:25 - Room B12

Random Matrices and the Melting Polar Ice Caps

Kenneth M. Golden

Department of Mathematics, University of Utah, USA   -

The precipitous loss of Arctic sea ice has far outpaced expert predictions. In this lecture we will delve into the mathematical underpinnings of this mystery, and discuss how we are using the mathematics of multiscale composites and statistical physics to study key sea ice properties. In particular, we will explore how random matrices arise in these problems, and show how the onset of connectedness in composite microstructures gives rise to striking transitional behavior in the long and short range correlations of the eigenvalues of the associated random matrices. This work is helping to improve projections of the fate of Earth's ice packs, and the response of polar ecosystems. We will conclude with a short video from a 2012 Antarctic expedition where sea ice properties were measured.

Joint work with N. Benjamin Murphy (Department of Mathematics, UC Irvine, USA).

View abstract PDF

December 17, 15:00 ~ 15:25 - Room B12

Gap probabilities and applications to geometry and random topology

Antonio Lerario

Institut Camille Jordan, Lyon, France   -

What is the volume of the set of singular symmetric matrices of norm one? What is the probability that a random plane misses this set? What is the expected "topology" of the intersection of random quadric hypersurfaces? In this talk I will combine classical techniques form algebraic topology ("spectral sequences") with ideas from Random Matrix Theory and show how these problems can be solved using a local analysis of the "gap probability" at zero (the probability that a random matrix has a gap in its spectrum close to zero).

Joint work with Erik Lundberg (Florida Atlantic University).

View abstract PDF

December 15, 17:05 ~ 17:30 - Room B12

Hypergeometric Functions of Matrix Arguments and Linear Statistics of Multi-Spiked Hermitian Matrix Models

Matthew McKay

Hong Kong University of Science and Technology, Hong Kong   -

This talk will present central limit theorems (CLTs) for linear statistics of three related “multi-spiked” Hermitian random matrix ensembles: (i) a spiked central Wishart ensemble; (ii) a non-central Wishart ensemble with fixed-rank non-centrality parameter; and (iii) a similarly defined non-central F ensemble. The analysis in each case is non-trivial, with the underlying joint eigenvalue densities involving hypergeometric functions of matrix arguments. For such functions, we first generalize a recent result of Onatski to present new exact multiple contour integral representations. Based on these, explicit CLT formulas are derived for each of the three spiked models of interest by employing Dyson’s Coulomb Fluid method along with saddlepoint techniques. We find that for each model, the individual spikes contribute additively to yield a O(1) correction term to the asymptotic mean of the linear statistic, whilst having no effect on the leading order terms of the mean or variance.

Joint work with Damien Passemier (Hong Kong University of Science and Technology, Hong Kong), Yang Chen (University of Macau, Macau).

View abstract PDF

December 17, 16:00 ~ 16:25 - Room B12

New applications of random matrices

Raj Rao Nadakuditi

University of Michigan, USA   -

We describe some new success stories where random matrix theory has enabled new applications: these include new theory and algorithms for transmitting light perfectly through highly scattering media and for separating foreground and background of videos in highly cluttered scenes. We conclude by highlighting some newly discovered random matrix universality phenomena emerging from scattering theory and semidefinite optimization.

View abstract PDF

December 15, 17:30 ~ 17:55 - Room B12

Large Complex Correlated Wishart Matrices: Fluctuations and Asymptotic Independence at the Edges

Jamal Najim

CNRS and Université Paris Est, France   -

We study the asymptotic behavior of eigenvalues of large complex correlated Wishart matrices at the edges of the limiting spectrum. For this matrix model, the support of the limiting eigenvalue distribution may have several connected components. Under mild conditions, we will show that the extremal eigenvalue which converge almost surely towards the edges of the support fluctuate according to the Tracy-Widom law at the scale $N^{2/3}$. Moreover, given several generic positive edges, we establish that the associated extremal eigenvalue fluctuations are asymptotically independent. Finally, when the leftmost edge is the origin, we prove that the smallest eigenvalue fluctuates according to the hard-edge Tracy-Widom law at the scale $N^2$ (Bessel kernel). As an application, an asymptotic study of the condition number of large correlated Wishart matrices is provided.

Joint work with Walid Hachem (Telecom Paristech and CNRS, France) and Adrien Hardy (KTH - Royal Institute of Technology, Sweden).

View abstract PDF

December 16, 14:30 ~ 14:55 - Room B22

Dysonian dynamics of the Ginibre ensemble

Maciej Nowak

Jagiellonian University, Poland   -

We study the time evolution of Ginibre matrices whose elements undergo Brownian motion. The non- Hermitian character of the Ginibre ensemble binds the dynamics of eigenvalues to the evolution of eigenvectors in a nontrivial way, leading to a system of coupled nonlinear equations resembling those for turbulent systems. We formulate a mathematical framework allowing simultaneous description of the flow of eigenvalues and eigenvectors, and we unravel a hidden dynamics as a function of a new complex variable, which in the standard description is treated as a regulator only. We solve the evolution equations for large matrices and demonstrate that the nonanalytic behavior of the Green’s functions is associated with a shock wave stemming from a Burgers-like equation describing correlations of eigenvectors. We conjecture that the hidden dynamics that we observe for the Ginibre ensemble is a general feature of non-Hermitian random matrix models and is relevant to related physical applications.

View abstract PDF

December 17, 14:30 ~ 14:55 - Room B12

Sampling unitary ensembles

Sheehan Olver

The University of Sydney, Australia   -

We develop a computationally efficient algorithm for sampling from a broad class of unitary random matrix ensembles that includes but goes well beyond the straightforward to sample Gaussian Unitary Ensemble (GUE). The algorithm exploits the fact that the eigenvalues of unitary ensembles (UEs) can be represented as a determinantal point process whose kernel is given in terms of orthogonal polynomials. Consequently, our algorithm can be used to sample from UEs for which the associated orthogonal polynomials can be numerically computed efficiently. By facilitating high accuracy sampling of non-classical UEs, the algorithm can aid in the experimentation-based formulation (or refutation) of universality conjectures involving eigenvalue statistics that might presently be unamenable to analysis. Examples of such experiments are included.

Joint work with Raj Rao (University of Michigan) and Thomas Trogdon (New York University).

View abstract PDF

December 15, 14:30 ~ 14:55 - Room B12

Asymptotic Degrees of Freedom for Combining Regression with Factor Analysis

Patrick Perry

New York University, USA   -

In multivariate regression problems with multiple responses, there often exist unobserved covariates (features) which are correlated with the responses. It is possible to estimate these covariates via factor analytic (eigenvector) methods, but calculating unbiased error variance estimates after adjusting for latent factors requires assigning appropriate degrees of freedom to the estimated factors. Many ad-hoc solutions to this problem have been proposed without the backup of a careful theoretical analysis. Using recent results from random matrix theory, we derive an expression for degrees of freedom. Our estimate gives a principled alternative to ad-hoc approaches in common use. Extensive simulation results show excellent agreement between the proposed estimator and its theoretical value.

Joint work with Natesh Pillai (Harvard University, USA).

View abstract PDF

December 15, 15:00 ~ 15:25 - Room B12

Deformed smallest singular value laws

Brian Rider

Temple University, US   -

We characterize the limiting smallest eigenvalue distributions for sample covariance type matrices drawn from a spiked population in terms of random integral operators. From here we derive partial differential equations satisfied by the corresponding distribution functions. We also show that, under a natural limit, these spiked "hard edge" laws degenerate to the critically spiked Tracy-Widom laws of basic importance in mathematical statistics. As a final application we derive a dynamic characterization of the Wishart distribution (which can be viewed as a Dufresne identity for matrix processes).

Joint work with Jose Ramirez (Universidad de Costa Rica) and Benedek Valko (University of Wisconsin - Madison).

View abstract PDF

December 16, 15:00 ~ 15:25 - Room B22

Finite N corrections to the Tracy-Widom distribution at the hard edge of the Laguerre-Wishart ensemble of complex random matrices

Grégory Schehr

University of Orsay-Paris Sud, France   -

We study the probability distribution function (PDF) of the smallest eigenvalue of Laguerre-Wishart matrices $W = X^\dagger X$ where $X$ is a random $M \times N$ ($M \geq N$) matrix, with complex Gaussian independent entries. We compute this PDF in terms of semi-classical orthogonal polynomials, which can be viewed as a deformation of Laguerre polynomials. By analyzing these polynomials, and their associated recurrence relations, in the limit of large $N$, large $M$ with $M/N \to 1$ -- i.e. for quasi-square large matrices $X$ -- we show that this PDF can be expressed in terms of the solution of a Painlevé III equation, as found by Tracy and Widom by analyzing a Fredholm determinant built from the Bessel kernel. In addition, our method allows us to compute the first $1/N$ corrections to this limiting Tracy-Widom distribution (at the hard edge). Our computations corroborate a recent conjecture by Edelman, Guionnet and Péché.

Joint work with Anthony Perret (University of Orsay, Paris-Sud).

View abstract PDF