Calendar











Mondays      214 Fine Hall      4:30 pm
jump to:  Archive

Fall 2011 Collapse/Expand/Print

-->
ate: September 26
Speaker: Leonidas Guibas, Stanford University
Title: Understanding 3D Shapes Jointly
Abstract: 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. Mathematical formulations, efficient algorithms, and software tools are required to support navigation and search over 3D model repositories. In this talk we examine the problem of facilitating these navigation and search tasks by automatically extracting relationships between shapes in a collection and understanding their common or shared structure. By effectively organizing the collection into (possibly overlapping) groups of related shapes, by separating what is common from what is variable within each group and across groups, and by understanding the main axes of variability, we can facilitate a whole slew of operations that make large 3D repositories much more navigable, searchable, compressible, and visualizable. We will present a quick summary of tools for efficiently computing informative shape descriptors as well as structure preserving maps between shapes at different levels of resolution. The main part of the talk, however, is aimed beyond pairwise relationships, to the study and analysis of many shapes jointly, looking at networks of maps between shapes in order to extract joint structure, derive consistent segmentations, infer phenotypic relationships, etc. This is preliminary work on what we believe to be a large open area for research -- the joint understanding of collections of related geometric data sets.

return to top
Date: October 3
Speaker: Don Saari, University of California - Irvine
Title: Complexity theory applied to voting theory
Abstract: 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.

return to top
Date: October 10
Speaker: Eitan Tadmor, University of Maryland
Title: A new model for self-organized dynamics: From particle to hydrodynamic descriptions
Abstract: 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. We will explain the emerging flocking behavior of the proposed model in the presence of non-symmetric interactions which decay sufficiently slow, and discuss the difficulties of tracing graph connectivity otherwise. The methodology is based on the new notion of active sets, which carries over from particle to kinetic and hydrodynamic descriptions, and we discuss the unconditional flocking at the level of hydrodynamic description.

return to top
Date: October 17
Speaker: Michael L. Overton, Courant Institute of Mathematical Sciences, NYU
Title: Optimization of Polynomial Roots, Eigenvalues and Pseudospectra
Abstract: 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. Finally, the pseudospectral radius and abscissa of a matrix $A$ are respectively the maximum modulus or maximum real part of elements of its pseudospectrum (the union of eigenvalues of all matrices within a specified distance of $A$). These functions are also nonconvex but, it turns out, locally Lipschitz, although the pseudospectrum itself is not a Lipschitz set-valued map. We discuss applications from control and from Markov chain Monte Carlo as examples throughout the talk. Coauthors of relevant papers include Vincent Blondel, Jim Burke, Kranthi Gade, Mert Gurbuzbalaban, Adrian Lewis and Alexandre Megretski.

return to top
Date: October 24
Speaker: Charles Epstein, UPenn
Title: Existence and regularity for a class of degenerate diffusions arising in population genetics
Abstract: Infinite population limits of standard Markov chain models lead to Markov processes on polyhedral domains that are formally generated by degenerate elliptic operators. These operators are characterized, in part, by the first order vanishing, along the boundary, of the coefficient of the second normal derivative term. This fact places these operators beyond those which have thus far been successfully analyzed using methods of geometric analysis. I will present an approach to these operators, which I have been pursuing with Rafe Mazzeo, based on an-isotropic Holder spaces, which leads to a rather complete existence, uniqueness and regularity theory.

return to top
Date: November 7
Speaker: Arjen Doelman, University of Leiden / Lorentz Center
Title: The mathematics of desertification: searching for early warning signals
Abstract: 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. It is crucial to be able to recognize whether a patterned state is close to collapse (or not), ecologists are thus searching for `early warning signals'. In this talk, we will translate the issues raised by the desertification process into mathematical terms and relate these to recent developments in the field of pattern formation. It will be shown that the process of desertification poses fundamental mathematical questions and that it already has led to the development of novel mathematical theory.

return to top
Date: November 14
Speaker: Vladimir Rokhlin, Yale University
Title: Accurate Randomized Algorithms of Numerical Analysis
Abstract: Randomized algorithms are ubiqutous in computer science and computer engineering. Many problems that are intractable when viewed deterministi- cally can be effectively solved with probabilistic techniques. Perhaps the most important aspect of most randomized procedures in current use is the fact that they produce the correct result with (practically speaking) 100% reliabil- ity, and with (essentially) machine precision. Historically, randomized techniques have been less popular in numerical analysis. Most of them trade accuracy for speed, and in many numerical environments one does not want to add yet another source of inaccuracy to the calculation that is already sufficiently inaccurate. One could say that in numerical analysis probabilistic methods are an approach of last resort. I will discuss several probabilistic algorithms of numerical linear algebra that are never less accurate than their deterministic counterparts, and in fact tend to produce better accuracy. In many situations, the new schemes have lower CPU time requirements than existing methods, both asymptotically and in terms of actual timings. I will illustrate the approach with several numerical examples, and discuss possible extensions.

return to top
Date: November 21
Speaker: Frederik Simons, Princeton University
Title: Prolates on the sphere, Extensions and Applications: Slepian functions for geophysical and cosmological signal estimation and spectral analysis
Abstract: 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. Analyzing and representing scientific data of this kind is facilitated in a basis of functions that are spatiospectrally concentrated, i.e. localized in both domains at the same time. Here, we give a theoretical overview of the approach to this concentration problem that was proposed for time series by Slepian and coworkers, in the 1960s. We show how this framework leads to practical algorithms and statistically performant methods for the analysis of signals and their power spectra in one and two dimensions, and on the surface of a sphere. "Spherical Slepian functions" are now widely applied to the study of inverse problems with (potential-field) satellite data, including such problems whose solutions are linear (source estimation), and quadratic (spectral estimation), in the data. Among the applications that I will discuss are the analysis of the time-variable gravity field for the recovery of coseismic gravity perturbations, the sparse analysis and representation of the lithospheric magnetic field, the recovery of the power spectral density of the cosmic microwave background radiation, and so on.

return to top
Date: November 28
Speaker: Andrea Montanari, Stanford University
Title: Sharp Thresholds in Statistical Estimation
Abstract: 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. [based on joint work with Mohsen Bayati, David Donoho, Iain Johnstone, Arian Maleki]

return to top
Date: December 5
Speaker: Peter Constantin, Princeton University
Title: Nonlocal Evolution Equations
Abstract: 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.

return to top

Spring 2012 Collapse/Expand/Print

Date: February 6
Speaker: Fan Chung, University of California, San Diego
Title: Graph gauge theory and vector diffusion maps

Abstract: 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. Furthermore, graph sparsification algorithms can be generalized to approximate and extract the global structure of information networks arising in signal and data processing.

return to top
Date: February 13
Speaker: Mark Braverman, Princeton University, Computer Science
Title: Computability and Complexity of Julia Sets
Abstract: 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. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. The theory behind them is even more fascinating, and the dynamical systems generating them are in many ways archetypal. I will present both positive and negative results on the computability and computational complexity of Julia sets.

return to top
Date: February 20
Speaker: Francois Meyer, University of Colorado Boulder
Title: A Random Walk on Image Patches
Abstract: 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. In the second part of the talk we provide a theoretical explanation for the success of algorithms that organize patches according to graph-based metrics. Our approach relies on a detailed analysis of the commute time on prototypical graph models that epitomize the geometry observed in general patch-graphs.

return to top
Date: February 27
Speaker: Eric Vanden-Eijnden, Courant NYU
Title: Dimension reduction, coarse-graining and data assimilation in high-dimensional dynamical systems
Abstract: 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. A particular successful class of methods of this type are Markov state models (MSMs), in which the transitions between the states in the partition are assumed to be memoryless jumps. The accuracy of these models crucially depends on the choice of these states. In this talk, I will discuss systematic strategies that permit to identify these states and quantify the error of the resulting approximation. These methods will be illustrated on examples arising from molecular dynamics simulations of biomolecules.

return to top
Date: March 5
Speaker: Yuan Yao, Peking University
Title: Topological Landscape of Networks
Abstract: 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.

return to top
Date: March 26
Speaker: Sayan Mukherjee, Duke University
Title: Geometry and Topology in Dimension Reduction
Abstract: 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.

return to top
Date: April 2
Speaker: Lek-Heng Lim, University of Chicago
Title: Mathematics of the Human Brain Connectome
Abstract: 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. The main problems are (i) to reconstruct a homogeneous polynomial representing a real-valued function on a sphere from dMRI data; and (ii) to analyze the homogeneous polynomial via a decomosition into a sum of powers of linear forms. We will discuss the algebraic geometry associated with (ii) and discuss a technique that combines (i) and (ii) for mapping neural fibers. This is joint work with T. Schultz of MPI Tubingen.

return to top
Date: April 9
Speakers: Prof. David Donoho, Stanford
Title: Optimal Phase Transitions in Compressed Sensing
Abstract: "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. If we assume the distribution of the coefficients is known/unknown, we get different answers; in each case I describe novel algorithms precisely achieving the optimal phase transition, converging to the answer at an expoential rate depending only on distance from phase transition. Both algorithms are applications of the Approximate Message Passing algorithm introduced by Maleki, Montanari and myself. This talk surveys joint work with several authors, including Andrea Montanari and Jared Tanner, as well as Adel Javanmard, Iain Johnstone and Arian Maleki.

return to top
Date: April 16
Speakers: Dustin Mixon, Afonso Bandeira

Title: Special PACM Student Colloquium!

Abstracts:
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). We then observe how the theory of synchronization can be leveraged to demonstrate stability in this method.

Afonso Bandeira - "Cheeger Inequality for the Graph Connection Laplacian": The $O(d)$ Synchronization problem consists of estimating a set of unknown orthogonal transformations $O_i$ from noisy measurements of a subset of the pairwise ratios $O_iO_j^{-1}$. We formulate and prove a Cheeger-type inequality that relates a measure of how well it is possible to solve the $O(d)$ synchronization problem with the spectra of an operator, the graph Connection Laplacian. We also show how this inequality provides a worst case performance guarantee for a spectral method to solve this problem. This is joint work with Amit Singer (Princeton) and Daniel Spielman (Yale).

return to top
Date: April 23
Speakers: Laurent Demanet, MIT
Title: Super-resolution via sparse recovery: progress and challenges
Abstract: 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. Algorithmic alternatives to ell-1 minimization are presented to attempt to deal with the harder situation of "destructive interference".

return to top
Date: April 30
Speakers: Shige Peng, Shandong University
Title: Nonlinear Expectation, Nonlinear PDE and Stochastic Calculus under Knightian Uncertainty
Abstract: A. N. Kolmogorov’s “Foundations of the Theory of Probability” published in 1933, has established the modern axiomatic foundations of probability theory. Since then this theory has been profoundly developed and widely applied to situations where uncertainty cannot be neglected. But in 1921 Frank Knight has been already clearly classified two types of uncertainties: the first one is for which the probability is known; the second one, now called Knightian uncertainty, is for cases where the probability itself is also uncertain. The situation with Knightian uncertainty has become one of main concerns in the domain of data processing, economics, statistics, and specially in measuring and controlling financial risks. A long time challenging problem is how to establish a theoretical framework comparable to the Kolmogorov’s one, to treat these more complicated situations with Knightian uncertainties. Tthe objective of the theory of nonlinear expectation rapidly developed in recent years is to solve this problem. This is an important program. Some fundamental results have been established such as law of large numbers, central limit theorem, martingales, G-Brownian motions, G-martingales and the corresponding stochastic calculus of Itˆo’s type, nonlinear Markov processes, as well as the calculation of measures of risk in finance. But still so many deep problems are still to be explored. This new framework of nonlinear expectation is naturally and deeply linked to nonlinear partial differential equations (PDE) of parabolic and elliptic types. These PDEs appear in the law of large numbers, central limit theorem, and nonlinear diffusion processes in the new theory, and inversely, almost all solutions of linear, quasilinear and/or fully nonlinear PDEs can be expressed in term of the nonlinear expectation of a function of the corresponding (nonlinear) diffusion processes. Moreover, a new type of ‘path-dependent partial differential equations’ have been introduced which provide a PDE tool to study a stochastic process under a nonlinear expectation. Numerical calculations of these path dependent PDE will provide the corresponding backward stochastic calculations.

return to top
Date: May 7 - Joint with Analysis
Speakers: Jiahong Wu, Oklahoma State University
Title: The 2D Boussinesq Equation with Partial Dissipation
Abstract: The Boussinesq equations concerned here model geophysical flows such as atmospheric fronts and ocean circulations. Mathematically the 2D Boussinesq equations serve as a lower-dimensional model of the 3D hydrodynamics equations. In fact, the 2D Boussinesq equations retain some key features of the 3D Euler and the Navier-Stokes equations such as the vortex stretching mechanism. The global regularity problem on the 2D Boussinesq equations with partial dissipation has attracted considerable attention in the last few years. In this talk we will summarize recent results on various cases of partial dissipation, present the work of Cao and Wu on the 2D Boussinesq equations with vertical dissipation and vertical thermal diffusion and explain the work of Chae and Wu on the logarithmically supercritical Boussinesq equations.

return to top