In the In the 2018-2019 AY, the Random Matrix and Probability Theory Seminar will take place on Thursdays from 4:30 – 5:30pm in CMSA, room G10. As the seminar will not occur on a regular weekly basis, the list below will reflect the dates of the scheduled talks. Room numbers and times will be announced as the details are confirmed.
The schedule will be updated as details are confirmed.
|Yash Deshpande (MIT)||Title: Estimating low-rank matrices in noise: phase transitions from spin glass theory
Abstract: Estimating low-rank matrices from noisy observations is a common task in statistical and engineering applications. Following the seminal work of Johnstone, Baik, Ben-Arous and Peche, versions of this problem have been extensively studied using random matrix theory. In this talk, we will consider an alternative viewpoint based on tools from mean field spin glasses. We will present two examples that illustrate how these tools yield information beyond those from classical random matrix theory. The first example is the two-groups stochastic block model (SBM), where we will obtain a full information-theoretic understanding of the estimation phase transition. In the second example, we will augment the SBM with covariate information at nodes, and obtain results on the altered phase transition.
This is based on joint works with Emmanuel Abbe, Andrea Montanari, Elchanan Mossel and Subhabrata Sen.
|10/3/2018||Ian Jauslin (IAS)||Title: Liquid Crystals and the Heilmann-Lieb model
Abstract: In 1979, O.Heilmann and E.H. Lieb introduced an interacting dimer model with the goal of proving the emergence of a nematic liquid crystal phase in it. In such a phase, dimers spontaneously align, but there is no long range translational order. Heilmann and Lieb proved that dimers do, indeed, align, and conjectured that there is no translational order. I will discuss a recent proof of this conjecture. This is joint work with Elliott H. Lieb.
|10/10/2018||Afonso Bandeira (NYU||Title: Statistical estimation under group actions: The Sample Complexity of Multi-Reference Alignment
Abstract: Many problems in signal/image processing, and computer vision amount to estimating a signal, image, or tri-dimensional structure/scene from corrupted measurements. A particularly challenging form of measurement corruption are latent transformations of the underlying signal to be recovered. Many such transformations can be described as a group acting on the object to be recovered. Examples include the Simulatenous Localization and Mapping (SLaM) problem in Robotics and Computer Vision, where pictures of a scene are obtained from different positions and orientations; Cryo-Electron Microscopy (Cryo-EM) imaging where projections of a molecule density are taken from unknown rotations, and several others.
One fundamental example of this type of problems is Multi-Reference Alignment: Given a group acting in a space, the goal is to estimate an orbit of the group action from noisy samples. For example, in one of its simplest forms, one is tasked with estimating a signal from noisy cyclically shifted copies. We will show that the number of observations needed by any method has a surprising dependency on the signal-to-noise ratio (SNR), and algebraic properties of the underlying group action. Remarkably, in some important cases, this sample complexity is achieved with computationally efficient methods based on computing invariants under the group of transformations.
|Thomas Chen (UT Austin)||Title: Dynamics of a heavy quantum tracer particle in a Bose gas
Abstract: We consider the dynamics of a heavy quantum tracer particle coupled to a non-relativistic boson field in R^3. The pair interactions of the bosons are of mean-field type, with coupling strength proportional to 1/N where N is the expected particle number. Assuming that the mass of the tracer particle is proportional to N, we derive generalized Hartree equations in the limit where N tends to infinity. Moreover, we prove the global well-posedness of the associated Cauchy problem for sufficiently weak interaction potentials. This is joint work with Avy Soffer (Rutgers University).
|Tselil Schramm (Harvard/MIT)||Title: (Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs
Abstract: The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. We study a popular average-case variant; we deviate from the common heuristic strategy and give the first quasi-polynomial time algorithm, where previously only sub-exponential time algorithms were known.
Based on joint work with Boaz Barak, Chi-Ning Chou, Zhixian Lei, and Yueqi Sheng.
|Lauren Williams (Harvard)||Title: Introduction to the asymmetric simple exclusion process (from a combinatorialist’s point of view)
Abstract: The asymmetric simple exclusion process (ASEP) is a model of particles hopping on a one-dimensional lattice, subject to the condition that there is at most one particle per site. This model was introduced in 1970 by biologists (as a model for translation in protein synthesis) but has since been shown to display a rich mathematical structure. There are many variants of the model — e.g. the lattice could be a ring, or a line with open boundaries. One can also allow multiple species of particles with different “weights.” I will explain how one can give combinatorial formulas for the stationary distribution using various kinds of tableaux. I will also explain how the ASEP is related to interesting families of orthogonal polynomials, including Askey-Wilson polynomials, Koornwinder polynomials, and Macdonald polynomials.
|11/7/2018||Willhelm Schlag (Yale)||Title: on the Bourgain-Dyatlov fractal uncertainty principle
Abstract: We will present the Bourgain-Dyatlov theorem on the line, it’s connection with other uncertainty principles in harmonic analysis, and my recent partial progress with Rui Han on the problem of higher dimensions.
|11/14/2018||David Gamarnik (MIT)||Title: Two Algorithmic Hardness Results in Spin Glasses and Compressive Sensing.
Abstract: I will discuss two computational problems in the area of random combinatorial structures. The first one is the problem of computing the partition function of a Sherrington-Kirkpatrick spin glass model. While the the problem of computing the partition functions associated with arbitrary instances is known to belong to the #P complexity class, the complexity of the problem for random instances is open. We show that the problem of computing the partition function exactly (in an appropriate sense) for the case of instances involving Gaussian couplings is #P-hard on average. The proof uses Lipton’s trick of computation modulo large prime number, reduction of the average case to the worst case instances, and the near uniformity of the ”stretched” log-normal distribution.
In the second part we will discuss the problem of explicit construction of matrices satisfying the Restricted Isometry Property (RIP). This challenge arises in the field of compressive sensing. While random matrices are known to satisfy the RIP with high probability, the problem of explicit (deterministic) construction of RIP matrices eluded efforts and hits the so-called ”square root” barrier which I will discuss in the talk. Overcoming this barrier is an open problem explored widely in the literature. We essentially resolve this problem by showing that an explicit construction of RIP matrices implies an explicit construction of graphs satisfying a very strong form of Ramsey property, which has been open since the seminal work of Erdos in 1947.
|11/28/2018||Sean O’ Rourke (UC Boulder)||Title: Universality and least singular values of random matrix products
Abstract: We consider the product of m independent iid random matrices as m is fixed and the sizes of the matrices tend to infinity. In the case when the factor matrices are drawn from the complex Ginibre ensemble, Akemann and Burda computed the limiting microscopic correlation functions. In particular, away from the origin, they showed that the limiting correlation functions do not depend on m, the number of factor matrices. We show that this behavior is universal for products of iid random matrices under a moment matching hypothesis. In addition, we establish universality results for the linear statistics for these product models, which show that the limiting variance does not depend on the number of factor matrices either. The proofs of these universality results require a near-optimal lower bound on the least singular value for these product ensembles.
|Omer Angel (UBC)||Title: balanced excited random walks
Abstract: I will present results on the scaling limit and asymptotics of the balanced excited random walk and related processes. This is a walk the that moves vertically on the first visit to a vertex, and horizontally on every subsequent visit. We also analyze certain versions of “clairvoyant scheduling” of random walks.
Joint work with Mark Holmes and Alejandro Ramirez.
Science Center 530
|Ramis Movassagh (IMB Research)||Title: Generic Gaplessness, and Hamiltonian density of states from free probability theory
Abstract: Quantum many-body systems usually reside in their lowest energy states. This among other things, motives understanding the gap, which is generally an undecidable problem. Nevertheless, we prove that generically local quantum Hamiltonians are gapless in any dimension and on any graph with bounded maximum degree.
We then provide an applied and approximate answer to an old problem in pure mathematics. Suppose the eigenvalue distributions of two matrices M_1 and M_2 are known. What is the eigenvalue distribution of the sum M_1+M_2? This problem has a rich pure mathematics history dating back to H. Weyl (1912) with many applications in various fields. Free probability theory (FPT) answers this question under certain conditions. We will describe FPT and show examples of its powers for approximating physical quantities such as the density of states of the Anderson model, quantum spin chains, and gapped vs. gapless phases of some Floquet systems. These physical quantities are often hard to compute exactly (provably NP-hard). Nevertheless, using FPT and other ideas from random matrix theory excellent approximations can be obtained. Besides the applications presented, we believe the techniques will find new applications in fresh new contexts.
|2/14/2019||Nike Sun (MIT)|| Title: Capacity lower bound for the Ising perceptron
Abstract: The perceptron is a toy model of a simple neural network that stores a collection of given patterns. Its analysis reduces to a simple problem in high-dimensional geometry, namely, understanding the intersection of the cube (or sphere) with a collection of random half-spaces. Despite the simplicity of this model, its high-dimensional asymptotics are not well understood. I will describe what is known and present recent results.
|2/21/2019||Michael Loss (Georgia Tech)||Title: Some results for functionals of Aharonov-Bohm type
Abstract: In this talk I present some variational problems of Aharonov-Bohm type, i.e., they include a magnetic flux that is entirely concentrated at a point. This is maybe the simplest example of a variational problems for systems, the wave function being necessarily complex. The functional is rotationally invariant and the issue to be discussed is whether the optimizer have this symmetry or whether it is broken.
Science Center 232
|Anna Vershynina (University of Houston)||TBA|
|3/27-29/2019||Xuwen Chen (University of Rochester)||TBA|
|4/4/2019||Paul Bourgade (NYU)||TBA|
|4/10-12/2019||Rui Han (Georgia Tech)||TBA|
|5/2/2019||Jian Ding (UPenn)||TBA|
For information on previous seminars, click here.