Seminars and Colloquia by Series

The proxy point method for rank-structured matrices

Series
Dissertation Defense
Time
Friday, October 25, 2019 - 13:30 for 1.5 hours (actually 80 minutes)
Location
Skiles 311
Speaker
Xin XingSchool of Mathematics, Georgia Tech

Rank-structured matrix representations, e.g., H2 and HSS, are commonly used to reduce computation and storage cost for dense matrices defined by interactions between many bodies. The main bottleneck for their applications is the expensive computation required to represent a matrix in a rank-structured matrix format which involves compressing specific matrix blocks into low-rank form.
We focus on the study and application of a class of hybrid analytic-algebraic compression methods, called the proxy point method. We address several critical problems concerning this underutilized method which limit its applicability. A general form of the method is proposed, paving the way for its wider application in the construction of different rank-structured matrices with kernel functions that are more general than those usually used. Further, we extend the applicability of the proxy point method to compress matrices defined by electron repulsion integrals, which accelerates one of the main computational steps in quantum chemistry. 

Committee members: Prof. Edmond Chow (Advisor, School of CSE, Georgia Tech), Prof. David Sherrill (School of Chemistry and Biochemistry, Georgia Tech), Prof. Jianlin Xia (Department of Mathematics, Purdue University), Prof. Yuanzhe Xi (Department of Mathematics, Emory University), and Prof. Haomin Zhou (School of Mathematics, Georgia Tech).

High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm

Series
ACO Student Seminar
Time
Friday, October 25, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Wenlong MouEECS, UC Berkeley

We propose a Markov chain Monte Carlo (MCMC) algorithm based on third-order Langevin dynamics for sampling from distributions with log-concave and smooth densities. The higher-order dynamics allow for more flexible discretization schemes, and we develop a specific method that combines splitting with more accurate integration. For a broad class of d-dimensional distributions arising from generalized linear models, we prove that the resulting third-order algorithm produces samples from a distribution that is at most \varepsilon in Wasserstein distance from the target distribution in O(d^{1/3}/ \varepsilon^{2/3}) steps. This result requires only Lipschitz conditions on the gradient. For general strongly convex potentials with α-th order smoothness, we prove that the mixing time scales as O (d^{1/3} / \varepsilon^{2/3} + d^{1/2} / \varepsilon^{1 / (\alpha - 1)} ). Our high-order Langevin diffusion reduces the problem of log-concave sampling to numerical integration along a fixed deterministic path, which makes it possible for further improvements in high-dimensional MCMC problems. Joint work with Yi-An Ma, Martin J, Wainwright, Peter L. Bartlett and Michael I. Jordan.

Finite time dynamics of chaotic and random systems

Series
Stochastics Seminar
Time
Thursday, October 24, 2019 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Leonid BunimovichGeorgia Institute of Technology

Everybody are convinced that everything is known about the simplest random process of coin tossing. I will show that it is not the case. Particularly not everything was known for the simplest chaotic dynamical systems like the tent map (which is equivalent to coin tossing). This new area of finite time predictions emerged from a natural new question in the theory of open dynamical systems.

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

Series
High Dimensional Seminar
Time
Wednesday, October 23, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Andre WibisonoGeorgia Tech

Sampling is a fundamental algorithmic task. Many modern applications require sampling from complicated probability distributions in high-dimensional spaces. While the setting of logconcave target distribution is well-studied, it is important to understand sampling beyond the logconcavity assumption. We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution on R^n under isoperimetry conditions. We show a convergence guarantee in Kullback-Leibler (KL) divergence assuming the target distribution satisfies log-Sobolev inequality and the log density has bounded Hessian. Notably, we do not assume convexity or bounds on higher derivatives. We also show convergence guarantees in Rényi divergence assuming the limit of ULA satisfies either log-Sobolev or Poincaré inequality. Joint work with Santosh Vempala (arXiv:1903.08568).

Uncertainty principles and Schrodinger operators on fractals

Series
Analysis Seminar
Time
Wednesday, October 23, 2019 - 13:55 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Kasso OkoudjouUniversity of Maryland and M.I.T.

In the first part of this talk, I will give an overview of a theory of harmonic analysis on a class of fractals that includes the Sierpinski gasket. The starting point of the theory is the introduction by J. Kigami of a Laplacian operator on these fractals. After reviewing the construction of this fractal Laplacian, I will survey some of the properties of its spectrum. In the second part of the talk, I will discuss the fractal analogs of the Heisenberg uncertainty principle, and the spectral properties a class of  Schr\"odinger operators.  

Go with the Flow: a parameterized approach to RNA transcript assembly

Series
Mathematical Biology Seminar
Time
Wednesday, October 23, 2019 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Blair Sullivan School of Computing, University of Utah

A central pervasive challenge in genomics is that RNA/DNA must be reconstructed from short, often noisy subsequences. In this talk, we describe a new digraph algorithm which enables this "assembly" when analyzing high-throughput transcriptomic sequencing data. Specifically, the Flow Decomposition problem on a directed ayclic graph asks for the smallest set of weighted paths that “cover” a flow (a weight function on the edges where the amount coming into any vertex is equal to the amount leaving). We describe a new linear-time algorithm solving *k*-Flow Decomposition, the variant where exactly *k* paths are used. Further, we discuss how we implemented and engineered a general Flow Decomposition solver based on this algorithm, and describe its performance on RNA-sequence data.  Crucially, our solver finds exact solutions while achieving runtimes competitive with a state-of-the-art heuristic, and we discuss the implications of our results on the original model selection for transcript assembly in this setting.

The seed-to-solution method for the Einstein equations and the asymptotic localization problem

Series
PDE Seminar
Time
Tuesday, October 22, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Philippe G. LeFlochSorbonne University and CNRS

I will present a new method of analysis for Einstein’s
constraint equations, referred to as the Seed-to-Solution Method, which
leads to the existence of asymptotically Euclidean manifolds with
prescribed asymptotic behavior. This method generates a (Riemannian)
Einstein manifold from any seed data set consisting of (1): a Riemannian
metric and a symmetric two-tensor prescribed on a topological manifold
with finitely many asymptotically Euclidean ends, and (2): a density
field and a momentum vector field representing the matter content. By
distinguishing between several classes of seed data referred to as tame
or strongly tame, the method encompasses metrics with the weakest
possible decay (infinite ADM mass) or the strongest possible decay
(Schwarzschild behavior). This analysis is based on a linearization of
the Einstein equations (involving several curvature operators from
Riemannian geometry) around a tame seed data set. It is motivated by
Carlotto and Schoen’s pioneering work on the so-called localization
problem for the Einstein equations. Dealing with manifolds with possibly
very low decay and establishing estimates beyond the critical level of
decay requires significantly new ideas to be presented in this talk. As
an application of our method, we introduce and solve a new problem,
referred to as the asymptotic localization problem, at the critical
level of decay. Collaboration with T. Nguyen. Blog: philippelefloch.org

Some basics of Markov chain mixing times

Series
Lorentzian Polynomials Seminar
Time
Tuesday, October 22, 2019 - 14:50 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Prasad TetaliGeorgia Tech

This is quick tutorial on bounding the mixing time of a finite Markov chain in terms of functional inequalities defining the spectral gap and the entropy constant of a Markov chain. The lecture will include some examples, including bounding the mixing time of the random transposition shuffle and (time permitting) that of the basis-exchange walk on a balanced matroid.

This is intended as a review lecture before Nima Anari’s lectures (during Nov. 4-6) on applications of Lorentzian polynomials, including recent breakthrough analyses of the basis-exchange walk on an arbitrary matroid.

The Mori Dream Space property for blow-ups of projective spaces at points and lines

Series
Algebra Seminar
Time
Tuesday, October 22, 2019 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zhuang HeNortheastern University

Mori Dream Spaces are generalizations of toric varieties and, as the name suggests, Mori's minimal model program can be run for every divisor. It is known that for n5, the blow-up of Pn at r very general points is a Mori Dream Space iff rn+3. In this talk we proceed to blow up points as well as lines, by considering the blow-up X of P3 at 6 points in very general position and all the 15 lines through the 6 points. We find that the unique anticanonical section of X is a Jacobian K3 Kummer surface S of Picard number 17. We prove that there exists an infinite-order pseudo-automorphism of X, whose restriction to S is one of the 192 infinite-order automorphisms constructed by Keum.  A consequence is that there are infinitely many extremal effective divisors on X; in particular, X is not a Mori Dream Space. We show an application to the blow-up of Pn (n3) at (n+3) points and certain lines.  We relate this pseudo-automorphism to the structure of the birational automorphism group of P3. This is a joint work with Lei Yang.

Proof of Kac's conjecture for the hard sphere gas

Series
Math Physics Seminar
Time
Monday, October 21, 2019 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Michael LossGeorgia Tech
This talk will be about the master equation approach to kinetic theory pioneered by Mark Kac. Specifically, the physically realistic case of three dimensional hard spheres will be considered.  This process describes an ensemble of  hard spheres undergoing binary energy and momentum preserving collisions.  One measure for the speed of approach to equilibrium is the gap which was conjectured by Kac to be bounded below by a positive constant independent of the number of particles. In this talk a proof of this conjecture  will be presented. This is joint work with Eric Carlen and Maria Carvalho.

Pages