Lecture notes

Notes from my course "Concentration of Measure on the Compact Classical Matrix Groups" at Women and Mathematics at the Institute for Advanced Study, 2014. These are still a little rough and in particular are still lacking a lot of references and attributions. Comments/corrections/suggestions are welcome!

Selected talks

Video of my talk "Concentration of Spectral Measures of Random Matrices" at the IMA workshop Information Theory and Concentration Phenomena in April 2015.

Here are the slides from "Uniformity of Eigenvalues of Some Random Matrices" at the 2014 Northeast Probability Seminar (held at Columbia University).

Here are the slides from a four-part mini-course "Randomness in geometry and topology: finding order in the chaos" at the 2013 – 2014 Low-dimensional Structure in High-dimensional Systems (LDHD) Summer School at SAMSI:

Linear Projections of High-Dimensional Data
Random Unitary Matrices and Friends
The Topology of Random Spaces
Stein's Method: The last gadget under the hood

Here are the slides from "The spectra of powers of random unitary matrices" at the Workshop on the Interplay of Banach Space Theory and Convex Geometry and the Banff International Research Station. You can watch a video of the talk!

Here are the slides from "Projections of Probability Distributions: A measure-theoretic Dvoretzky theorem" at the 2012 Midwest Probability Colloquium (held at Northwestern University).

When I was barely out of diapers, I was asked to give a talk on "How to prove a central limit theorem" at the Conference on Number Theory and Random Phenomena at the University of Bristol (March 2007). Here are scans of the slides. There's rather an overemphasis on Stein's method at the end (hey, I said I was barely out of diapers), but they're not bad as a quick and dirty introduction to some of the basic techniques.


The titles below are links to arXiv versions; the bibliographic entries are links to the published versions.

Rates of convergence for empirical spectral measures: a soft approach (with Mark Meckes) — preprint.

Abstract: Understanding the limiting behavior of eigenvalues of random matrices is the central problem of random matrix theory. Classical limit results are known for many models, and there has been significant recent progress in obtaining more quantitative, non-asymptotic results. In this paper, we describe a systematic approach to bounding rates of convergence and proving tail inequalities for the empirical spectral measures of a wide variety of random matrix ensembles. We illustrate the approach by proving asymptotically almost sure rates of convergence of the empirical spectral measure in the following ensembles: Wigner matrices, Wishart matrices, Haar-distributed matrices from the compact classical groups, powers of Haar matrices, randomized sums and random compressions of Hermitian matrices, a random matrix model for the Hamiltonians of quantum spin glasses, and finally the complex Ginibre ensemble. Many of the results appeared previously and are being collected and described here as illustrations of the general method; however, some details (particularly in the Wigner and Wishart cases) are new. Our approach makes use of techniques from probability in Banach spaces, in particular concentration of measure and bounds for suprema of stochastic processes, in combination with more classical tools from matrix analysis, approximation theory, and Fourier analysis. It is highly flexible, as evidenced by the broad list of examples. It is moreover based largely on "soft" methods, and involves little hard analysis.

Almost sure convergence in quantum spin glasses (with David Buzinski) — preprint.

Abstract:Recently, Keating, Linden, and Wells showed that the density of states measure of a nearest-neighbor quantum spin glass model is approximately Gaussian when the number of particles is large. The density of states measure is the ensemble average of the empirical spectral measure of a random matrix; in this paper, we use concentration of measure and entropy techniques together with the result of Keating—Linden—Wells to show that in fact, the empirical spectral measure of such a random matrix is almost surely approximately Gaussian itself, with no ensemble averaging. We also extend this result to a spherical quantum spin glass model and to the more general coupling geometries investigated by Erdős and Schröder.

Self-similarity in the circular unitary ensemble (with Mark Meckes) — preprint.

Abstract: This paper gives a rigorous proof of a conjectured statistical self-similarity property of the eigenvalues random matrices from the Circular Unitary Ensemble. We consider on the one hand the eigenvalues of an \(n \times n\) CUE matrix, and on the other hand those eigenvalues \(e^{i\phi}\) of an \(mn \times mn\) CUE matrix with \(|\phi| \le \pi / m\), rescaled to fill the unit circle. We show that for a large range of mesoscopic scales, these collections of points are statistically indistinguishable for large \(n\). The proof is based on a comparison theorem for determinantal point processes which may be of independent interest.

A rate of convergence for the circular law for the complex Ginibre ensemble (with Mark Meckes) — Annales de la Faculté des Sciences de Toulouse (6) 24, no. 1 (2015).

Abstract: We prove rates of convergence for the circular law for the complex Ginibre ensemble. Specifically, we bound the Lp-Wasserstein distance between the empirical spectral measure of the normalized complex Ginibre ensemble and the uniform measure on the unit disc, both in expectation and almost surely. For 1 ≤ p ≤ 2, the bounds are of the order n-1/4, up to logarithmic factors.

On the equivalence of modes of convergence for log-concave measures (with Mark Meckes) — Geometric Aspects of Functional Analysis: Papers from the Israel Seminar (GAFA). (Springer Lecture Notes Vol. 2116, 2014).

Abstract:An important theme in recent work in asymptotic geometric analysis is that many classical implications between different types of geometric or functional inequalities can be reversed in the presence of convexity assumptions. In this note, we explore the extent to which different notions of distance between probability measures are comparable for log-concave distributions. Our results imply that weak convergence of isotropic log-concave distributions is equivalent to convergence in total variation, and is further equivalent to convergence in relative entropy when the limit measure is Gaussian.

Spectral measures of powers of random matrices (with Mark Meckes) — Electron. Comm. Probab. 18, no. 78 (2013).

Abstract: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 Lp-Wasserstein distances between this empirical measure and the uniform measure, which show a smooth transition in behavior when the power increases and yield rates on almost sure convergence when the dimension grows. Along the way, we prove the sharp logarithmic Sobolev inequality on the unitary group.

Asymptotics of the mean-field Heisenberg model (with Kay Kirkpatrick) — J. Stat. Phys 152, no. 1 (2013).

Abstract:We consider the mean-field classical Heisenberg model and obtain detailed information about the magnetization by studying the model on a complete graph and sending the number of vertices to infinity. In particular, we obtain Cram\`er- and Sanov-type large deviations principles for the magnetization and the empirical spin distribution and demonstrate a second-order phase transition in the Gibbs measures. We also study the asymptotics of the magnetization throughout the phase transition using Stein's method, proving central limit theorems in the sub- and supercritical phases and a nonnormal limit theorem at the critical temperature.

Concentration and convergence rates for spectral measures of random matrices (with Mark Meckes) — Probab. Theory Related Fields 156, no. 1-2 (2013).

Abstract: 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 random Hermitian matrices, and the so-called random sum of two independent random matrices. In each case, we estimate the expected Wasserstein distance from the empirical spectral measure to a deterministic reference measure, and prove a concentration result for that distance. As a consequence we obtain almost sure convergence of the empirical spectral measures in all cases.

Personal Note: I think of this paper as being unofficially dedicated to our children: Peter, who stubbornly refused to be born while most of the work in this paper was done; and Juliette, who told me one morning that it would make her happy if I proved a theorem that day (I'm pretty sure it was what became Theorem 3.5).

Projections of probability distributions: A measure-theoretic Dvoretzky theorem — in Geometric Aspects of Functional Analysis: Papers from the Israel Seminar (GAFA) , (Springer Lecture Notes Vol. 2050, 2012).

Abstract:Many authors have studied the phenomenon of typically Gaussian marginals of high-dimensional random vectors; e.g., for a probability measure on Rd, under mild conditions, most one-dimensional marginals are approximately Gaussian if d is large. In earlier work, the author used entropy techniques and Stein's method to show that this phenomenon persists for k-dimensional marginals of d-dimensional distributions, if k=o(√log(d)). In this paper, a somewhat different approach is used to show that this phenomenon persists if k<2log(d)/log(log(d)), and that this estimate is best possible.

Note: This paper was previously titled "Projections of random vectors via the generic chaining". Michel Talagrand has kindly pointed out that in fact the generic chaining is not necessary for the proof and that Dudley's entropy bound suffices to obtain the result. Also, since that version, additional discussion on the parallels with Dvoretzky's theorem has been added; the connection had previously been left for the cognoscenti to notice on their own.

Limit theorems for Betti numbers of random simplicial complexes (with Matthew Kahle) — Homology, Homotopy and Applications 15, no. 1 (2013).

Abstract: There have been several recent articles studying homology of various types of random simplicial complexes. Several theorems have concerned thresholds for vanishing of homology, and in some cases expectations of the Betti numbers. However little seems known so far about limiting distributions of random Betti numbers. In this article we establish Poisson and normal approximation theorems for Betti numbers of different kinds of random simplicial complex: Erdős-Rényi random clique complexes, random Vietoris-Rips complexes, and random Čech complexes. These results may be of practical interest in topological data analysis.

Another observation about operator compressions (with Mark Meckes) — Proc. Amer. Math. Soc. 139 (2011).

Abstract: Let T be a self-adjoint operator on a finite dimensional Hilbert space. It is shown that the distribution of the eigenvalues of a compression of T to a subspace of a given dimension is almost the same for almost all subspaces. This is a coordinate-free analogue of a recent result of Chatterjee and Ledoux on principal submatrices. The proof is based on measure concentration and entropy techniques, and the result improves on some aspects of the result of Chatterjee and Ledoux.

Approximation of projections of random vectorsJ. Theoret. Probab. 25, no. 2 (2012).

Abstract: Let X be a d-dimensional random vector and Xθ its projection onto the span of a set of orthonormal vectors 1,...,θk}. Conditions on the distribution of X are given such that if θ is chosen according to Haar measure on the Stiefel manifold, the bounded-Lipschitz distance from Xθ to a Gaussian distribution is concentrated at its expectation; furthermore, an explicit bound is given for the expected distance, in terms of d, k, and the distribution of X, allowing consideration not just of fixed k but of k growing with d. The results are applied in the setting of projection pursuit, showing that most k-dimensional projections of n data points in Rd are close to Gaussian, when n and d are large and k=c(√log(d)) for a small constant c.

Please note: In the published version of this paper, there is a misprint in the last sentence of the abstract; it says there that k=c(log(d)). The statement above is in fact what follows from the proofs in this paper. For the sharp rate, see the paper "Projections of probability distributions: A measure-theoretic Dvoretzky theorem" above.

On Stein's method for multivariate normal approximation — in High Dimensional Probability V: The Luminy Volume (IMS Collections Vol. 5, 2009).

Abstract: The purpose of this paper is to synthesize the approaches taken by Chatterjee-Meckes and Reinert-Röllin in adapting Stein's method of exchangeable pairs for multivariate normal approximation. The more general linear regression condition of Reinert-Röllin allows for wider applicability of the method, while the method of bounding the solution of the Stein equation due to Chatterjee-Meckes allows for improved convergence rates. Two abstract normal approximation theorems are proved, one for use when the underlying symmetries of the random variables are discrete, and one for use in contexts in which continuous symmetry groups are present. The application to runs on the line from Reinert-Röllin is reworked to demonstrate the improvement in convergence rates, and a new application to joint value distributions of eigenfunctions of the Laplace-Beltrami operator on a compact Riemannian manifold is presented.

Quantitative asymptotics of graphical projection pursuitElectron. Comm. Probab. 14 (2009).

Abstract:There is a result of Diaconis and Freedman which says that, in a limiting sense, for large collections of high-dimensional data most one-dimensional projections of the data are approximately Gaussian. This paper gives quantitative versions of that result. For a set of deterministic vectors {xi}i=1n in Rd with n and d fixed, let θ be a random point of the sphere Sd-1and let μnθ denote the random measure which puts mass 1/n at each of the points {x1· θ,...,xn· θ}. For a fixed bounded Lipschitz test function f, Z a standard Gaussian random variable and σ2 a suitable constant, an explicit bound is derived for the probability that the integral of f with respect to μnθ differs from the expected value of f(σ Z) by more than ε. A bound is also given for the deviations about zero of the bounded Lipschitz distance between μnθ and the law of σ Z, which yields a lower bound on the waiting time to finding a non-Gaussian projection of the {xi} if directions are tried independently and uniformly on Sd-1.

Two multivariate central limit theorems — preprint (one of the two was improved and incorporated into "On Stein's method for multivariate normal approximation" above).

Abstract: In this paper, explicit error bounds are derived in the approximation of rank k projections of certain n-dimensional random vectors by standard k-dimensional Gaussian random vectors. The bounds are given in terms of k, n, and a basis of the k-dimensional space onto which we project. The random vectors considered are two generalizations of the case of a vector with independent, identically distributed components. In the first case, the random vector has components which are independent but need not have the same distribution. The second case deals with finite exchangeable sequences of random variables.

On the approximate normality of eigenfunctions of the LaplacianTrans. Amer. Math. Soc. 361, no. 10 (2009).

Abstract: The main result of this paper is a bound on the distance between the distribution of an eigenfunction of the Laplacian on a compact Riemannian manifold and the Gaussian distribution. If X is a random point on a manifold M and f is an eigenfunction of the Laplacian with L2-norm one and eigenvalue , then the total variation distance between f(X) and a standard Gaussian random variable is bounded by (2/μ)E||∇ f(X)|2-E|∇f(X) |2|. This result is applied to construct specific examples of spherical harmonics of arbitrary (odd) degree which are close to Gaussian in distribution. A second application is given to random linear combinations of eigenfunctions on flat tori.

Multivariate normal approximation using exchangeable pairs (with Sourav Chatterjee) — ALEA 4 (2008).

Abstract: Since the introduction of Stein's method in the early 1970s, much research has been done in extending and strengthening it; however, there does not exist a version of Stein's original method of exchangeable pairs for multivariate normal approximation. The aim of this article is to fill this void. We present three abstract normal approximation theorems using exchangeable pairs in multivariate contexts, one for situations in which the underlying symmetries are discrete, and real and complex versions of a theorem for situations involving continuous symmetry groups. Our main applications are proofs of the approximate normality of rank k projections of Haar measure on the orthogonal and unitary groups, when k=o(n).

Linear functions on the classical matrix groupsTrans. Amer. Math. Soc. 360, no. 10 (2008).

Abstract:Let M be a random matrix in the group of n ×n orthogonal matrices over R, distributed according to Haar measure, and let A be a fixed n× n matrix over R such that Tr(AAt)=n. Then the total variation distance of the random variable Tr(AM) to standard normal is bounded by (2√3)/(n-1), and this rate is sharp up to the constant. Analogous results are obtained for M a random unitary matrix and A a fixed n× n matrix over C. The proofs are applications of a new abstract normal approximation theorem which extends Stein's method of exchangeable pairs to situations in which continuous symmetries are present.

The central limit problem for random vectors with symmetries (with Mark Meckes) — J. Theoret. Probab. 20, no. 4 (2007).

Abstract:Motivated by the central limit problem for convex bodies, we study normal approximation of linear functionals of high-dimensional random vectors with various types of symmetries. In particular, we obtain results for distributions which are coordinatewise symmetric, uniform in a regular simplex, or spherically symmetric. Our proofs are based on Stein's method of exchangeable pairs; as far as we know, this approach has not previously been used in convex geometry and we give a brief introduction to the classical method. The spherically symmetric case is treated by a variation of Stein's method which is adapted for continuous symmetries.

An Infinitesimal Version of Stein's Method of Exchangeable Pairs (Ph.D. thesis under Persi Diaconis, 2006).

Abstract:The central theme of this dissertation is an extension of Stein's method of exchangeable pairs for use in proving the approximate normality of random variables which are invariant under a continuous group of symmetries. A key feature of the technique is that, for univariate approximation, it provides convergence rates in the total variation metric as opposed to the weaker notions of distance obtained via the classical versions of Stein's method. This new technique is applied to projections of Haar measure on the classical matrix groups as well as spherically symmetric distributions on Euclidean space. The technique is also used in studying eigenfunctions of the Laplacian on a large class of Riemannian manifolds. A multivariate version of the method is developed and applied to higher dimensional projections of Haar measure on the classical matrix groups and spherically symmetric distributions on Euclidean space.

Exchangeable pairs and Poisson approximation (with Sourav Chatterjee and Persi Diaconis) — Probab. Surv. 2 (2005).

Abstract:This is a survey paper on Poisson approximation using Stein's method of exchangeable pairs. We illustrate using Poisson-binomial trials and many variations on three classical problems of combinatorial probability: the matching problem, the coupon collector's problem, and the birthday problem. While many details are new, the results are closely related to a body of work developed by Andrew Barbour, Louis Chen, Richard Arratia, Lou Gordon, Larry Goldstein, and their collaborators. Some comparison with these other approaches is offered.