# Seminars & Events for PACM/Applied Mathematics Colloquium

##### Understanding 3D Shapes Jointly

The use of 3D models in our economy and life is becoming more prevalent, in applications ranging from design and custom manufacturing, to prosthetics and rehabilitation, to games and entertainment. Although the large-scale creation of 3D content remains a challenging problem, there has been much recent progress in design software tools, like Google SketchUp for buildings or Spore for creatures, or in low cost 3D acquisition hardware, like the Microsoft Kinect scanner. As a result, large commercial 3D shape libraries, such as the Google 3D Warehouse, already contain millions of models. These libraries, however, can be unwieldy, when the need arises to efficiently incorporate models into various workflows.

##### Complexity theory applied to voting theory

As it will be shown with results and examples, the paradoxes associated with standard voting rules are surprisingly likely and are so complex that one must worry about the legitimacy of election outcomes. To extract an understanding of what can happen and why, it is shown how lessons from complexity theory, where complicated behavior is due to a combination of simple interactions, explain many mysteries both in this area and for related topics such as nonparametric statistics, etc. Indeed, all paradoxes of standard rules, including Arrow's seminal "Impossibility Theorem," reflect simple but hidden symmetry structures connecting the preferences of voters.

##### A new model for self-organized dynamics: From particle to hydrodynamic descriptions

Self-organized dynamics is driven by "rules of engagement" which describe how each agent interacts with its neighbors. They consist of long-term attraction, mid-range alignment and short-range repulsion. Many self-propelled models are driven by the balance between these three forces, which yield emerging structures of interest. Examples range from consensus of voters and traffic flows to the formation of flocks of birds or school of fish, tumor growth etc. We introduce a new particle-based model, driven by self-alignment, which addresses several drawbacks of existing models for self-organized dynamics. The model is independent of the number of agents: only their geometry in phase space is involved.

##### Optimization of Polynomial Roots, Eigenvalues and Pseudospectra

The root radius and root abscissa of a monic polynomial are respectively the maximum modulus and the maximum real part of its roots; both these functions are nonconvex and are non-Lipschitz near polynomials with multiple roots. We begin the talk by giving constructive methods for efficiently minimizing these nonconvex functions in the case that there is just one affine constraint on the polynomial's coefficients. We then turn to the spectral radius and spectral abscissa functions of a matrix, which are analogously defined in terms of eigenvalues. We explain how to use nonsmooth optimization methods to find local minimizers and how to use nonsmooth analysis to study local optimality conditions for these nonconvex, non-Lipschitz functions.

##### On queues and numbers

We will show that certain symmetries which have traditionally played an important role in number theory are also important for analyzing certain simple queueing systems. This connection between number theory and queueing theory leads to some interesting questions in number theory and also helps understand results from several queueing theory papers. We will demonstrate the connection by examining the problem of managing a mini-market with an express line queue. If time permits we will explain how the management problem in a supermarket setting relates to space-time geometry. The talk will be self contained, in particular, no experience in managing mini-markets will be assumed.

##### Existence and regularity for a class of degenerate diffusions arising in population genetics

Joint PACM Colloquium and Analysis Seminar

##### The mathematics of desertification: searching for early warning signals

The process of desertification can be modeled by systems of reaction-diffusion equations. Numerical simulations of these models agree remarkably well with field observations: both show that 'vegetation patterns'—i.e. regions in which the vegetation only survives in localized 'patches'—naturally appear as the transition between a healthy homogeneously vegetated state and the (non-vegetated) desert state. Desertification is a catastrophic and non-reversible event during which huge patterned vegetation areas 'collapse' into the desert state at a fast time scale—for instance as a consequence of a slow decrease of yearly rainfall, or through an increased grazing pressure.

##### Prolates on the sphere, Extensions and Applications: Slepian functions for geophysical and cosmological signal estimation and spectral analysis

Functions that are timelimited (or spacelimited) cannot be simultaneously bandlimited (in frequency). Yet the finite precision of measurement and computation unavoidably bandlimits our observation and modeling scientific data, and we often only have access to, or are only interested in, a study area that is temporally or spatially bounded. In the geosciences we may be interested in spectrally modeling a time series defined only on a certain interval, or we may want to characterize a specific geographical area observed using an effectively bandlimited measurement device. In cosmology we may wish to compute the power spectral density of the cosmic microwave background radiation without the contaminating effect of the galactic plane.

##### Sharp Thresholds in Statistical Estimation

Sharp thresholds are ubiquitous high-dimensional combinatorial structures. The oldest example is probably the sudden emergence of the giant component in random graphs, first discovered by Erdos an Renyi. More recently, threshold phenomena have started to play an important role in some statistical learning and statistical signal processing problems, in part because of the interest in 'compressed sensing'. The basic setting is one in which a large number of noisy observations of a high-dimensional object are made. As the ratio of the number of observations to the number of `hidden dimensions' crosses a threshold, our ability to reconstruct the object increases dramatically. I will discuss several examples of this phenomenon, and some algorithmic and mathematical ideas that allow to characterize these threshold phenomena.

##### Nonlocal Evolution Equations

Nonlocal evolution equations have been around for a long time, but in recent years there have been some nice new developments. The presence of nonlocal terms might originate from modeling physical, biological or social phenomena (incompressibility, Ekman pumping, chemotaxis, micro-micro interactions in complex fluids, collective behavior in social aggregation) or simply from inverting local operators in the analysis of systems of PDE. I will brifly present some regularity results for hydrodynamic models with singular constitutive laws. The main part of the talk will present a nonlinear maximum principle for linear nonlocal dissipative operators and applications.

##### Graph Gauge Theory and Vector Diffusion Maps

We consider a generalization of graph Laplacian which acts on the space of functions which assign to each vertex a point in $d$-dimensional space. The eigenvalues of such connection Laplacian are useful for examining vibrational spectra of molecules as well as vector diffusion maps for analyzing high dimensional data. We will discuss algebraic, probabilistic and algorithmic methods in the study of the connection spectra. For example, if the graph is highly symmetric and the connection Laplacian is invariant under the symmetry of the graph, then its eigenvalues can be deduced by using irreducible representations. In addition, by using matrix concentration inequalities, the eigenvalues of random connection Laplacians can be approximated by the eigenvalues of the expected matrices under appropriate conditions.

##### Computability and Complexity of Julia Sets

Studying dynamical systems is key to understanding a wide range of phenomena ranging from planetary movement to climate patterns to market dynamics. Various computational and numerical tools have been developed to address specific questions about dynamical systems, such as predicting the weather or planning the trajectory of a satellite. However, the theory of computation behind these problems appears to be very difficult to develop. In fact, little is known about computability of even the most natural problems arising from dynamical systems. In this talk I will survey the recent study of the computational properties of dynamical systems that arise from iterating quadratic polynomials on the complex plane. These give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set.

##### A Random Walk on Image Patches

Algorithms that analyze patches extracted from time series or images have led to state-of-the art techniques for classification, denoising, and the study of nonlinear dynamics. In the first part of the talk we describe two examples of such algorithms: a novel method to estimate the arrival-times of seismic waves from a seismogram, and a new patch-based method to denoise images. Both approaches combines the following two ingredients: the signals (times series or images) are first lifted into a high-dimensional space using time/space-delay embedding; the resulting phase space is then parametrized using a nonlinear method based on the eigenvectors of the graph Laplacian. Both algorithms outperform existing gold standards.

##### Dimension Reduction, Coarse-Graining and Data Assimilation in High-Dimensional Dynamical Systems

Modern computing technologies, such as massively parallel simulation, special-purpose high-performance computers, and high-performance GPUs permit to simulate complex high-dimensional dynamical systems and generate time-series in amounts too large to be grasped by traditional “look and see” analyses. This calls for robust and automated methods to extract the essential structural and dynamical properties from these data in a manner that is little or not depending on human subjectivity. To this end, a decade of work has led to the development of analysis techniques which rely on the partitioning of the conformation space into discrete substates and reduce the dynamics to transitions between these states.

##### Topological Landscape of Networks

We will discuss how one can endow a network with a landscape in a very simple and natural way. Critical point analysis is introduced for functions defined on networks. The concept of local minima/maxima and saddle points of different indices are defined, by extending the notion of gradient flows and minimum energy path to the network setting. Persistent homology is used to design efficient numerical algorithms for performing such analysis. Applications to some examples of social and biological networks (LAO protein binding network) are demonstrated. These examples show that the critical nodes play important roles in the structure and dynamics of such networks. This is a joint work with Weinan E and Jianfeng Lu.

##### Geometry and Topology in Dimension Reduction

In the first part of the talk we describe how learning the gradient of a regression function can be used for supervised dimension reduction (SDR). We provide an algorithm for learning gradients in high-dimensional data, provide theoretical guarantees for the algorithm, and provide a statistical interpretation. Comparisons to other methods on real and simulated data are presented. In the second part of the talk we present preliminary results on using the Laplacian on forms for dimension reduction. This involves understanding higher-order versions of the isoperimetric inequality for both manfifolds and abstract simplicial complexes.

##### Mathematics of the Human Brain Connectome

The human brain connectome is an ambitious project to provide a complete map of neural connectivity and a recent source of excitement in the neuroscience community. Just as the human genome is a triumph of marrying technology (high throughput sequencers) with theory (dynamic programming for sequence alignment), the human connectome is a result of a similar union. The technology in question is that of diffusion magnetic resonance imaging (dMRI) while the requisite theory, we shall argue, comes from three areas: PDE, harmonic analysis, and algebraic geometry. The underlying mathematical model in dMRI is the Bloch-Torrey PDE but we will approach the 3-dimensional imaging problem directly.

##### Optimal Phase Transitions in Compressed Sensing

"Compressed Sensing" is an active research area which touches on harmonic analysis, geometric functional analysis, applied mathematics, computer science electrical engineering and information theory. Concrete achievements, such as speeding up pediatric MRI acquistion times from several minutes to under a minute, are now entering daily use. In my talk I will discuss the notion of phase transitions in combinatorial geometry, describe how they precisely demarcate the situations where a popular algorithm in compressed sensing -- ell_1 minimization -- can succeed. Then I will discuss the issue: what is the best possible phase transition of any algorithm? We get different answers depending on the assumptions we make.

##### Special PACM Student Colloquium!

**Dustin Mixon** - "Phaseless recovery with polarization": In many applications, an unknown vector is measured according to the magnitude of its inner product with some known vector. It is desirable to design an ensemble of vectors for which any unknown vector can be recovered from such measurements (up to a global phase factor). In 2006, Balan et al. demonstrated that this measurement process is injective for generic M-dimensional vector ensembles of size at least 4M-2. Recently, Candes et al. used semidefinite programming to stably reconstruct from measurements with random ensembles of size O(MlogM). In this talk, we use the polarization identity and expander graphs to efficiently recover from measurements with specific deterministic ensembles of size O(M).

##### Super-resolution via sparse recovery: progress and challenges

From the knowledge of a function in a frequency band, super-resolution consists in detecting or estimating sharp features which are less than the inverse of a bandwidth apart from one another. Sparse recovery is one way to extend this Shannon-Nyquist scaling, but "by how much" and "in which setting" it is not yet clearly understood. This work attempts to start the classification of singularity layout vs. noise level for proper identification by ell-1 minimization. When a condition of constructive interference is met, ell1-minimization performs optimally: it only breaks down in the unrecoverable regime where no other method would work either. As a corollary, we obtain a novel noise-dependent scaling which replaces the inverse bandwidth rule for super-resolution.