# Seminars & Events for PACM/Applied Mathematics Colloquium

##### Qianxiao Li: Free-energy-like concepts for nonequilibrium systems; Cheng Tai: Video Super-Resolution via Adaptive Wavelet Frames and Elastic Deformations

Abstract: Qianxiao Li - The extension of the concept of free energy to fully nonequilibrium systems is an important problem in statistical mechanics. I will discuss how a straightforward generalization, using the nonequilibrium steady-state distribution in place of the canonical ensemble, yields a free energy that is not sufficient in capturing the dynamics of general nonequilibrium steady states. One can overcome this problem by defining the "free action", which is like a trajectory-space free energy. Through a representative example, I will discuss the conceptual and practical usefulness of the free action in quantifying the dynamics of nonequilibrium steady states. If time allows, I will also discuss how one can employ similar ideas to treat systems with deterministic dynamics and random initial conditions.

##### Dictionary Learning and Matrix Recovery with Optimal Rate

Let A be an n×n matrix, X be an n×p matrix and Y = AX. A challenging and important problem in data analysis, motived by dictionary learning, is to recover both A and X, given Y. Under normal circumstances, it is clear that the problem is underdetermined. However, as showed by Spielman et. al., one can succeed when X is sufficiently sparse and random. In this talk, we discuss a solution to a conjecture raised by Spielman et. al. concerning the optimal condition which guarantees efficient recovery. The main technical ingredient of our analysis is a novel way to use the ε-net argument in high dimensions for proving matrix concentration, beating the standard union bound. This part is of independent interest. Joint work with K. Luh (Yale).

##### Phase Retrieval, Self-Calibration, Random Matrices, and Convex Optimization

I will demonstrate how two important, but seemingly unrelated, problems, namely Phase Retrieval and Self-Calibration, can be solved by using methods from random matix theory and convex optimization. Phase retrieval is the century-old problem of reconstructing a function, such as a signal or image, from intensity measurements, typically from the modulus of a diffracted wave. Phase retrieval problems -- which arise in numerous areas including X-ray crystallography, astronomy, diffraction imaging, and quantum physics -- are notoriously difficult to solve numerically. They also pervade many areas of mathematics, such as numerical analysis, harmonic analysis, algebraic geometry, combinatorics, and differential geometry.

##### Efficient use of semidefinite programming for selection of rotamers in protein conformations and other applications

In this paper we study a semidefinite programming relaxation of the (NP-hard) side chain positioning problem. We show that the Slater constraint qualification (strict feasibility) fails for the SDP relaxation. We then show the advantages of using facial reduction to regularize the SDP. In fact, after applying facial reduction, we have a smaller problem that is more stable both in theory and in practice. We include a discussion of the background of SDP relaxations and exploiting pecial structure in various applications such as sensor network localization, SNL. Work with: Forbes Burkowski (University of Waterloo) Yuen-Lam Cheung Voronin (University of Colorado, Boulder)

##### Fast algorithms for electronic structure analysis

Kohn-Sham density functional theory (KSDFT) is the most widely used electronic structure theory for molecules and condensed matter systems. For a system with N electrons, the standard method for solving KSDFT requires solving N eigenvectors for an O(N) * O(N) Kohn-Sham Hamiltonian matrix. The computational cost for such procedure is expensive and scales as O(N^3), and limits routine KSDFT calculations to hundreds of atoms. In recent years, we have developed an alternative procedure called the pole expansion and selected inversion (PEXSI) method [1-2]. The PEXSI method solves KSDFT without solving any eigenvalue and eigenvector, and directly evaluates physical quantities including electron density, energy, atomic force, density of states, and local density of states.

##### Polynomial Bounds for the Grid-Minor Theorem

**THIS IS A SPECIAL PACM COLLOQUIUM. **One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains H as a minor. This theorem has found many applications in graph theory and algorithms. Let f(k) denote the largest value, such that every graph of treewidth k contains a grid minor of size f(k).