A moment method for invariant ensembles

Speaker: 

Jonathan Novak

Institution: 

UCSD

Time: 

Tuesday, January 8, 2019 - 11:00am

Location: 

RH 306

Conjugation invariant ensembles of random matrices have long formed one of the basic paradigms in Random Matrix Theory. Apart from the Gaussian case, the matrix elements of a conjugation invariant random matrix are highly correlated, and this fact has traditionally been viewed as prohibiting the use of moment methods in the spectral analysis of invariant ensembles. However, it turns out that there is a very natural and appealing version of the moment method available for these ensembles which seems to have been overlooked. I will describe the rudiments of this method, and some of its applications. Based on joint work with Sho Matsumoto.

From number theory to machine learning: hunting for smooth Boolean functions

Speaker: 

Roman Vershynin

Institution: 

UCI

Time: 

Tuesday, May 1, 2018 - 11:00am to 12:00pm

Location: 

RH 306

The most fundamental kind of functions studied in computer science are Boolean functions. They take n bits as an input and return one bit as an output. Most Boolean functions oscillate a lot, which is analogous to the fact that "most" continuous functions on R are nowhere differentiable. If we want to generate a "smooth" Boolean function, we can take the sign of some polynomial of low degree in n variables. Such functions are called polynomial threshold functions, and they are widely used in machine learning as classification devices. Surprisingly, we do not know how many polynomial threshold functions there are with a given degree! Even an approximate answer to this question has been known only for polynomials of degree 1, i.e. for linear functions. In a very recent joint work with Pierre Baldi, we found a way to approximately count polynomial threshold functions of any fixed degree. This solves a problem of M. Saks that goes back to 1993 and earlier. Our argument draws ideas from analytical number theory, additive combinatorics, enumerative combinatorics, probability and discrete geometry. I will describe some of these connections, focusing particularly on a beautiful interplay of zeta and Mobius funcitons in number theory, hyperplane arrangements in enumerative combinatorics and random tensors in probability theory.

Deterministic Random Matrices

Speaker: 

Ilya Soloveychik

Institution: 

Harvard University

Time: 

Tuesday, April 24, 2018 - 12:00pm to 1:00pm

Host: 

Location: 

440 RH

Random matrices have become a very active area of research in the recent years and have found enormous applications in modern mathematics, physics, engineering, biological modeling, and other fields. In this work, we focus on symmetric sign (+/-1) matrices (SSMs) that were originally utilized by Wigner to model the nuclei of heavy atoms in mid-50s. Assuming the entries of the upper triangular part to be independent +/-1 with equal probabilities, Wigner showed in his pioneering works that when the sizes of matrices grow, their empirical spectra converge to a non-random measure having a semicircular shape. Later, this fundamental result was improved and substantially extended to more general families of matrices and finer spectral properties. In many physical phenomena, however, the entries of matrices exhibit significant correlations. At the same time, almost all available analytical tools heavily rely on the independence condition making the study of matrices with structure (dependencies) very challenging. The few existing works in this direction consider very specific setups and are limited by particular techniques, lacking a unified framework and tight information-theoretic bounds that would quantify the exact amount of structure that matrices may possess without affecting the limiting semicircular form of their spectra.

 

From a different perspective, in many applications one needs to simulate random objects. Generation of large random matrices requires very powerful sources of randomness due to the independence condition, the experiments are impossible to reproduce, and atypical or non-random looking outcomes may appear with positive probability. Reliable deterministic construction of SSMs with random-looking spectra and low algorithmic and computational complexity is of particular interest due to the natural correspondence of SSMs and undirected graphs, since the latter are extensively used in combinatorial and CS applications e.g. for the purposes of derandomization. Most of the existing constructions of pseudo-random graphs focus on the extreme eigenvalues and do not provide guaranties on the whole spectrum. In this work, using binary Golomb sequences, we propose a simple completely deterministic construction of circulant SSMs with spectra converging to the semicircular law with the same rate as in the original Wigner ensemble. We show that this construction has close to lowest possible algorithmic complexity and is very explicit. Essentially, the algorithm requires at most 2log(n) bits implying that the real amount of randomness conveyed by the semicircular property is quite small.

Mathematical problems in the physics of proteins

Speaker: 

Stanislav Molchanov

Institution: 

UNCC

Time: 

Tuesday, March 6, 2018 - 3:00pm to 3:50pm

Host: 

Location: 

RH 340P

The talk will present the review of the mathematical models of the phase transitions and diffusion of the proteins.

Content.

  1. Kindergarten biophysics
  2. Physical Brownian motion
  3. Folding – unfolding phase transition
  4. Diffusion coefficient as the function of the temperature
  5. Intermediate asymptotics
  6. Diffusion with aggregation

Random Matrices with Structured or Unstructured Correlations

Speaker: 

Todd Kemp

Institution: 

UCSD

Time: 

Tuesday, April 17, 2018 - 11:00pm to 11:50pm

Host: 

Location: 

306 RH

Random matrix theory began with the study, by Wigner in the 1950s, of high-dimensional matrices with i.i.d. entries (up to symmetry).  The empirical law of eigenvalues demonstrates two key phenomena: bulk universality (the limit empirical law of eigenvalues doesn't depend on the laws of the entries) and concentration (the convergence is robust and fast).

 

Several papers over the last decade (initiated by Bryc, Dembo, and Jiang in 2006) have studied certain special random matrix ensembles with structured correlations between some entries. The limit laws are different from the Wigner i.i.d. case, but each of these models still demonstrates bulk universality and concentration.

 

In this lecture, I will talk about very recent results of mine and my students on these general phenomena:

 

Bulk universality holds true whenever there are constant-width independent bands, regardless of the correlations within each band.  (Interestingly, the same is not true for independent rows or columns, where universality fails.)  I will show several examples of such correlated band matrices generalizing earlier known special cases, demonstrating how the empirical law of eigenvalues depends on the structure of the correlations.

 

At the same time, I will show that concentration is a more general phenomenon, depending not on the the structure of the correlations but only on the sizes of correlated partition blocks. Under  some regularity assumptions, we find that Gaussian concentration occurs in NxN ensembles so long as the correlated blocks have size smaller than N^2/log(N).

Pages

Subscribe to RSS - Probability