Seminars and Colloquia by Series

Geometric inequalities via information theory

Series
High Dimensional Seminar
Time
Wednesday, September 11, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jing HaoGeorgia Tech

Using ideas from information theory, we establish lower bounds on the volume and the surface area of a geometric body using the size of its slices along different directions.  In the first part of the talk, we derive volume bounds for convex bodies using generalized subadditivity properties of entropy combined with entropy bounds for log-concave random variables. In the second part, we investigate a new notion of Fisher information which we call the L1-Fisher information and show that certain superadditivity properties of the L1-Fisher information lead to lower bounds for the surface areas of polyconvex sets in terms of its slices.

On the QQR codes in coding theory

Series
High Dimensional Seminar
Time
Wednesday, September 4, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jing HaoGeorgia Tech

In this talk I will briefly talk about coding theory and introduce a specific family of codes called Quasi-quadratic residue (QQR) codes. These codes have large minimum distances, which means they have good error-correcting capabilities. The weights of their codewords are directly related to the number of points on corresponding hyperelliptic curves. I will show a heuristic model to count the number of points on hyperelliptic curves using a coin-toss model, which in turn casts light on the relation between efficiency and the error-correcting capabilities of QQR codes. I will also show an interesting phenomenon we found about the weight enumerator of QQR codes. Lastly, using the bridge between QQR codes and hyperelliptic curves again, we derive the asymptotic behavior of point distribution of a family of hyperelliptic curves using results from coding theory.

Anti-concentration of random sums with dependent terms, and singularity of sparse Bernoulli matrices

Series
High Dimensional Seminar
Time
Wednesday, August 28, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Konstantin TikhomirovGeorgiaTech

We will consider the problem of estimating the singularity probability of sparse Bernoulli matrices, and a related question of anti-concentration of weighted sums of dependent Bernoulli(p) variables.

Based on joint work with Alexander Litvak.

On maximal perimeters of convex sets with respect to measures

Series
High Dimensional Seminar
Time
Wednesday, April 17, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Galyna LivshytsGeorgia Tech

We discuss the asymptotic value of the maximal perimeter of a convex set in an n-dimensional space with respect to certain classes of measures. Firstly, we derive a lower bound for this quantity for a large class of probability distributions; the lower bound depends on the moments only. This lower bound is sharp in the case of the Gaussian measure (as was shown by Nazarov in 2001), and, more generally, in the case of rotation invariant log-concave measures (as was shown by myself in 2014). We discuss another class of measures for which this bound is sharp. For isotropic log-concave measures, the value of the lower bound is at least n^{1/8}.

In addition, we show a uniform upper bound of Cn||f||^{1/n}_{\infty} for all log-concave measures in a special position, which is attained for the uniform distribution on the cube. We further estimate the maximal perimeter of isotropic log-concave measures by n^2. 

Optimal estimation of smooth functionals of high-dimensional parameters

Series
High Dimensional Seminar
Time
Wednesday, April 10, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Vladimir KoltchinskiiGeorgia Tech

Please Note: We discuss a general approach to a problem of estimation of a smooth function $f(\theta)$ of a high-dimensional parameter $\theta$ of statistical models. In particular, in the case of $n$ i.i.d. Gaussian observations $X_1,\doot, X_n$ with mean $\mu$ and covariance matrix $\Sigma,$ the unknown parameter is $\theta = (\mu, \Sigma)$ and our approach yields an estimator of $f(\theta)$ for a function $f$ of smoothness $s>0$ with mean squared error of the order $(\frac{1}{n} \vee (\frac{d}{n})^s) \wedge 1$ (provided that the Euclidean norm of $\mu$ and operator norms of $\Sigma,\Sigma^{-1}$ are uniformly bounded), with the error rate being minimax optimal up to a log factor (joint result with Mayya Zhilova). The construction of optimal estimators crucially relies on a new bias reduction method in high-dimensional problems and the bounds on the mean squared error are based on controlling finite differences of smooth functions along certain Markov chains in high-dimensional parameter spaces as well as on concentration inequalities.

Random matrix perturbations

Series
High Dimensional Seminar
Time
Wednesday, April 3, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Sean O'RourkeUniversity of Colorado Boulder

Computing the eigenvalues and eigenvectors of a large matrix is a basic task in high dimensional data analysis with many applications in computer science and statistics. In practice, however, data is often perturbed by noise. A natural question is the following: How much does a small perturbation to the matrix change the eigenvalues and eigenvectors? In this talk, I will consider the case where the perturbation is random. I will discuss perturbation results for the eigenvalues and eigenvectors as well as for the singular values and singular vectors.  This talk is based on joint work with Van Vu, Ke Wang, and Philip Matchett Wood.

Iterative linear solvers and random matrices: new bounds for the block Gaussian sketch and project method.

Series
High Dimensional Seminar
Time
Wednesday, March 27, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Liza RebrovaUCLA

Please Note:

One of the most famous methods for solving large-scale over-determined linear systems is Kaczmarz algorithm, which iteratively projects the previous approximation x_k onto the solution spaces of the next equation in the system. An elegant proof of the exponential convergence of this method using correct randomization of the process is due to Strohmer and Vershynin (2009). Many extensions and generalizations of the method were proposed since then, including the works of Needell, Tropp, Ward, Srebro, Tan and many others. An interesting unifying view on a number of iterative solvers (including several versions of the Kaczmarz algorithm) was proposed by Gower and Richtarik in 2016. The main idea of their sketch-and-project framework is the following: one can observe that the random selection of a row (or a row block) can be represented as a sketch, that is, left multiplication by a random vector (or a matrix), thereby pre-processing every iteration of the method, which is represented by a projection onto the image of the sketch.
I will give an overview of some of these methods, and talk about the role that random matrix theory plays in the showing their convergence. I will also discuss our new results with Deanna Needell on the block Gaussian sketch and project method.

 

Estimates for multilinear Schur multipliers

Series
High Dimensional Seminar
Time
Wednesday, February 27, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Anna SkripkaUniversity of New mexico

Linear Schur multipliers, which act on matrices by entrywisemultiplications, as well as their generalizations have been studiedfor over a century and successfully applied in perturbation theory (asdemonstrated in the previous talk). In this talk, we will discussestimates for finite dimensional multilinear Schur multipliersunderlying these applications.

Minimal gaussian partitions with applications

Series
High Dimensional Seminar
Time
Wednesday, February 20, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Steven HeilmanUSC

A single soap bubble has a spherical shape since it minimizes its surface area subject to a fixed enclosed volume of air. When two soap bubbles collide, they form a “double-bubble” composed of three spherical caps. The double-bubble minimizes total surface area among all sets enclosing two fixed volumes. This was proven mathematically in a landmark result by Hutchings-Morgan-Ritore-Ros and Reichardt using the calculus of variations in the early 2000s. The analogous case of three or more Euclidean sets is considered difficult if not impossible. However, if we replace Lebesgue measure in these problems with the Gaussian measure, then recent work of myself (for 3 sets) and of Milman-Neeman (for any number of sets) can actually solve these problems. We also use the calculus of variations. Time permitting, we will discuss an improvement to the Milman-Neeman result and applications to optimal clustering of data and to designing elections that are resilient to hacking. http://arxiv.org/abs/1901.03934

Pages