Calendar

jump to: Current Year / 2006 / 2005 / 2004
2003 / 2002 / 2001 / 2000 / 1999 / 1998

This is an archive of past PACM Colloquiums.
You can jump to a specific year from the list on the right.

2006-2007 Collapse/Expand

Date: September 18
Speaker: J. Nathan Kutz, Applied Mathematics, University of Washington
Title: Soliton Lasers
Abstract: A comprehensive treatment is given for the formation of mode-locked soliton pulses in optical fiber and solid state lasers. The pulse dynamics is dominated by the interaction of the cubic Kerr nonlinearity and chromatic dispersion with an intensity dependent perturbation provided by the mode-locking element in the laser cavity. The intensity dependent perturbation preferentially attenuates low intensity electromagnetic radiation which makes the mode-locked pulses attractors of the laser cavity. A review of the broad spectrum of mode-locked laser models, both qualitative and quantitative, are considered with the basic pulse formation phenomena highlighted. Although the numerous mode-locking models are considerably different, they are unified by the fact that stable solitons are exhibited in each case due to the intensity discrimination perturbation in the laser cavity.

return to top
Date: September 25
Speaker: Peter Winkler, Mathematics, Dartmouth College
Title: Maximum Overharng
Abstract: How far can a stack of n bricks hang over the edge of a table? It took 5 mathematicians (Mike Paterson, Yuval Peres, Mikkel Thorup, Uri Zwick and the speaker) to solve this classic problem---and the answer is not what most people thought.

return to top
Date: October 9
Speaker: C. Richard Johnson, Jr., Electrical and Computer Engineering, Cornell University
Title: Vincent Van Gogh and Imitators in Greyscale: An Experiment in Cross-Disciplinary Stimulation
Abstract: This seminar describes a recently initiated project intended to accelerate the interaction of art historians and image processors in artist identification. The collection of digital images of artwork has been underway for over twenty years. Subsequently, in the last ten years image processors have initiated projects to process digitized images of paintings and drawings to assist art historians in artist identification. A key issue in the advance of this emerging technology, which is poised to expand rapidly over the next ten years, is bridging the gap between the two cultures of image processor system developers and art historian users. Four teams presently creating image processing schemes to assist the art historian in artist identification have agreed to prepare a daylong program for art historians to introduce them to the potential of this technology. The Van Gogh Museum in Amsterdam and the Kr¨oller-M¨uller Museum in Otterloo have agreed to provide these four teams access to a common database of digitized paintings by Vincent Van Gogh and his imitators. The Van Gogh Museum plans to host a workshop on May 18, 2007, to be attended by art historians to whom the four teams will make presentations on brushstroke analysis in assistance of artist identification. The genesis of this pioneering experiment in cross-disciplinary stimulation raises a number of interesting issues about research between one field suffused with mathematics, models, and algorithms and another where such intellectual tools are practically absent and conceivably considered intellectually inappropriate.

return to top
Date: October 16
Speaker: Anna Gilbert, Mathematics, University of Michigan
Title: One sketch for all: a sublinear approximation scheme for heavy hitters
Abstract: The heavy hitters problem elicits a list of the m largest-magnitude components in a signal of length d. Although this problem is easy when the signal is presented explicitly, it becomes much more challenging in the setting of streaming data, where the signal is presented implicitly as a sequence of additive updates. One approach maintains a small sketch of the data that can be used to approximate the heavy hitters quickly. In previous work, this sketch is essentially a random linear projection of the data that fails with small probability for each signal. It is often desirable that the sketch succeed simultaneously for ALL signals from a given class, a requirement that may be called uniform heavy hitters. It arises, for example, when the signal is queried a large number of times or when the signal updates are stochastically dependent.
This talk describes a random linear sketch for uniform heavy hitters that succeeds with high probability. The recovery algorithm produces a list of heavy hitters that approximates the input signal with an l2 error that is optimal, except for an additive term that depends on the optimal l1 error and a controllable parameter e. The recovery algorithm requires space m*poly(log(d)/e) and time m2*poly(log(d)/e) to produce the list of heavy hitters. Up to logarithmic factors, the performance of this algorithm is the best possible with respect to several resources.
Joint work with Martin Strauss, Joel Tropp, and Roman Vershynin.

return to top
Date: October 23
Speaker: Margaret Wright, Computer Science Department, CIMS, New York University
Title: Solving Nasty Optimization Problems in Science and Engineering
Abstract: Many important optimization problems in science and engineering involve functions that can fairly be described as "nasty", which can mean any or all of wildly nonlinear, nonsmooth, noisy, and defined through complex black-box simulation or error-prone experimental data. Because it is often impossible or impractical to calculate derivatives of these functions, non-derivative methods are the only feasible choice. These methods are in the midst of a renaissance involving research on their theoretical and computational properties, as well as investigation of which methods are best suited for which applications. This talk will include examples of challenging problems along with the speaker's assessment of the state of the art in non-derivative optimization methods.

return to top
Date: November 6
Speaker: Alon Orlitsky, ECE and CSE, University of California, San Diego
Title: Information Theory and Probability Estimation: From Shannon to Shakespeare via Laplace, Good, Turing, Hardy, Ramanujan, and Fisher
Abstract: Standard information-theoretic results show that data over small, typically binary, alphabets can be compressed to Shannon's entropy limit. Yet most practical sources, such as text, audio, or video, have essentially infinite support. Compressing such sources requires estimating probabilities of unlikely, even unseen, events, a problem considered by Laplace. Of existing estimators, an ingenious if cryptic one derived by Good and Turing while deciphering the Enigma code works best yet not optimally. Hardy and Ramanujan's celebrated results on the number of integer partitions yield an asymptotically optimal estimator that compresses arbitrary-alphabet data patterns to their entropy. The same approach generalizes Fisher's seminal work estimating the number of butterfly species and its extension authenticating a poem purportedly written by The Bard. The talk covers these topics and is self contained.
Joint work with Prasad Santhanam, Krishna Viswanathan, and Junan Zhang

return to top
Date: November 13
Speaker: Yang Wang, Mathematics, Georgia Institute of Technology
Title: Denoising Color Images
Abstract: Natural color images captured by digital cameras often exhibit noticeable noise, particularly when the pictures are taken under low lighting or artificial lighting conditions. Traditional denoising techniques, which are often tested for removing artificial noise in monochromatic images, often do not work well for noisy color images.
In this talk, we present an overview of some of the traditional methods for denoising. We discuss a new strategy, which we call the cross-channel principle, that can be applied for very effective denoising of color images. In particular we show how this principle can be applied to the total variation denoising scheme and an ENO type denoising scheme.

return to top
Date: November 20
Speaker: Massimo Fornasier, PACM, Princeton University
Title: Faithful recovery of vectorr valued functions from incomplete data. Recolorization and art restoration
Abstract: On March 11, 1944, the famous Eremitani's Church in Padua (Italy) was destroyed in an Allied bombing together with the inestimable frescoes by Andrea Mantegna et al. contained in the Ovetari Chapel. In the last 60 years, several attempts have been made to restore the fresco fragments by traditional methods, but without much success. We have developed a fast, robust, and efficient pattern recognition algorithm in order to map the original position and orientation of the fragments, based on comparisons with an old gray level image of the fresco prior to the damage. This innovative technique allowed for the partial reconstruction of the frescoes. Unfortunately, the surface covered by the fragments is only 77 m^2, while the original area was of several hundreds. This means that we can currently reconstruct only a fraction (less than 8%) of this inestimable artwork. In particular the original color of the blanks is not known. This begs the question of whether it is possible to estimate mathematically the original colors of the frescoes by making use of the potential information given by the available fragments and the gray level of the pictures taken before the damage. Can one estimate how faithful such restoration is?
In this talk we retrace the development of the recovery of the frescoes as an inspiring and challenging real-life problem for the development of new mathematical methods. We introduce two models for the recovery of vector valued functions from incomplete data, with applications to the fresco recolorization problem. The models are based on the minimization of a functional which is formed by the discrepancy with respect to the data and additional regularization constraints. The latter refer to joint sparsity measures with respect to frame expansions for the first functional and functional total variation for the second. We establish the relations between these two models. As a byproduct we develop the basis of a theory of fidelity in color recovery, which is a crucial issue in art restoration.

return to top
Date: November 27
Speaker: Charles Epstein, Mathematics, University of Pennsylvania
Title: Inverse scattering in nuclear magnetic resonance
Abstract: Selective excitation is an essential ingredient of any application of nuclear magnetic resonance, e.g. MR-imaging or spectroscopy. I will explain how the problem of selective excitation of 2-level quantum systems leads directly to the classical inverse scattering problem for the 2x2 AKNS system. We discuss the analysis of the inverse scattering transform and the role of non-linearity. I then show how a viable numerical algorithm, based on the hard pulse approximation, allows for the practical and accurate solution of this problem.

return to top
Date: December 1, 8pm, A02 McDonnell Hall
Speaker: Distinguished Lecture Series Eric S. Lander, Broad Institute, Massachusetts Institute of Technology
Title: Genomic Information: Biology and Medicine in the 21st Century
Abstract: The Human Genome Project was just an early step in a decades-long scientific program aimed at achieving a systematic and comprehensive view of biology and medicine. This program involves deep collaboration among biologists, chemists, physicians, engineers and – importantly – mathematicians and computer scientists. The lecture will describe current projects in genomic medicine, including comparative genomics, human genetics, cancer genetics and chemical biology. Along the way, it will highlight analytical issues that arise from the massive amounts of genomic information that are rapidly becoming available.

return to top
Date: December 4
Speaker: Graduate Student Short Talks:
Title: An Overview of Research in PACM

return to top
Date: February 5
Speaker: Philip Holmes, PACM & MAE, Princeton University
Title: 122+ Years of Nonlinear Dynamics: More is Different and Less is More
Abstract: As I was completing my PhD in Engineering in the early 1970's, dynamical systems theory was reapproaching earth after a 70-year sojourn in the mathematical stratosphere. Catastrophe theory was hot (if controversial), complexity was yet to come, and some prominent mechanicians and applied mathematicians told me that chaos didn't exist, or would be irrelevant if it did.
I will review some developments in nonlinear dynamics since that time, traveling back to check its origins in the works of Poincare, Birkhoff, Cartwright, Littlewood, Kolmogorov, Arnold, Moser and Smale, and returning to current frontiers in hybrid systems and stochastic models. These will illustrate the first subtitle, drawn from an article by Philip Anderson (Science 177: 393, 1972). I will also emphasize the central ideas of dimension reduction via invariant manifolds, normal forms, and the role of simple canonical examples such as Smale's horseshoe, thus justifying the second subtitle (due to Mies van der Rohe). I will close by speculating on future directions, and, in doing so, probably repeat the lack of foresight to which I alluded at the beginning.

return to top
Date: February 12, 4:30pm
Speaker: Ron Weiss, Electrical Engineering, Princeton University
Title: Synthetic Biology: from Bacteria to Stem Cells
Abstract: With recent advances in our understanding of cellular processes and improvements in DNA synthesis methods, we can now regard cells as "programmable matter." Through genetic engineering, we are equipping cells with new sophisticated capabilities for gene regulation, information processing, and communication. These new capabilities serve as catalysts for Synthetic Biology, an emerging engineering discipline to program cell behaviors as easily as we program computers. Synthetic biology will improve our quantitative understanding of natural biological processes and will also have biotechnology applications in areas such as biosensing, synthesis of pharmaceutical products, molecular fabrication of biomaterials and nanostructures, and tissue engineering.
In this talk, I will describe the use of computer engineering principles of abstraction, composition, and interface specifications to program cells with sensors and actuators precisely controlled by analog and digital logic circuitry. I will present theoretical and experimental results from synthetic systems implemented in bacteria and higher order organisms. I will begin by describing how information flows through synthetic transcriptional cascades in single cells by examining noise propagation, ultrasensitivity, and impedance matching. Understanding these issues is critical for the analysis and de novo engineering of complex gene networks. I will then discuss several synthetic multicellular systems that were programmed to exhibit unique coordinated cell behavior. These are the pulse generator, band detector, and Conway’s Game of Life. These systems allow us to explore programmed pattern formation and observe how complex global behavior emerges from localized interactions between cells. I will also discuss the implementation of artificial cell-cell communication and quorum sensing behavior in higher level organisms such as yeast. Finally, I will discuss preliminary results in mouse embryonic stem cells of implementing synthetic gene networks that regulate gene expression, direct differentiation, and orchestrate artificial cell-cell communication with the ultimate goal of programmed tissue engineering.

return to top
Date: February 19
Speaker: Zvi Artstein, Mathematics and Computer Science, The Weizmann Institute of Science
Title: Averaging of ordinary differential equations revisited
Abstract: The Averaging Method replaces a time-varying perturbation of a differential equation by a time-invariant one, while introducing only a relatively small error. The origin of the method goes back to calculations of stellar orbits; it has many modern applications in both modeling and numerical issues. A variety of mathematical tools have been developed in order to derive accurate estimates of the resulting errors. A new estimation criterion will be offered, which is based on rather "soft" estimates, namely, carrying out a comparison of integrals on a fast time scale. If, in addition, Young measures are employed, the method allows a natural extension to control systems, and carrying out the averaging in an environment with slowly moving averages.

return to top
Date: February 26
Speaker: Ron DeVore, Courant Institute, New York University
Title: A Taste of Compressed Sensing
Abstract: The usual paradigm for encoding signals is based on the Shannon sampling theorem. If the signal is broad-banded then this requires a high sampling rate even though the information content in the signal may be small. Compressed Sensing is an attempt to get out of this dilemma and sample at close to the information rate. The fact that this may be possible is embedded in some old mathematical results in functional analysis, geometry and approximation. This talk will be an excursion into these topics which will focus on the relation between the number of samples we take of a signal and how well we can approximate the signal. It will take place in the discrete setting for vectors in Euclidean space. The talk should be understandable to graduate students and non specialists.

return to top
Date: March 5
Speaker: Robert Vanderbei, ORFE & PACM, Princeton University
Title: Linear Stability of Ring Systems
Abstract: (Co-author: Egemen Kolemen) We give a self-contained modern linear stability analysis of a system of n equal mass bodies in circular orbit about a single more massive body. Starting with the mathematical description of the dynamics of the system, we form the linear approximation, compute all of the eigenvalues of the linear stability matrix, and finally derive inequalities that guarantee that none of these eigenvalues have positive real part. In the end, we rederive the result that J.C. Maxwell found for large n in his seminal paper on the nature and stability of Saturn’s rings, which was published 150 years ago. In addition, we identify the exact matrix that defines the linearized system even when n is not large. This matrix is then investigated numerically (by computer) to find stability inequalities. Furthermore, using properties of circulant matrices, the eigenvalues of the large 4n×4n matrix can be computed by solving n quartic equations, which further facilitates the investigation of stability. Finally, we have implemented an n-body simulator and we verify that the threshold mass ratios that we derived mathematically or numerically do indeed identify the threshold between stability and instability. Throughout the paper we consider only the planar n-body problem so that the analysis can be carried out purely in complex notation, which makes the equations and derivations more compact, more elegant and therefore, we hope, more transparent. The result is a fresh analysis that shows that these systems are always unstable for 2 <= n <= 6 and for n > 6 they are stable provided that the central mass is massive enough. We give an explicit formula for this mass-ratio threshold.

return to top
Date: March 12
Speaker: Dwight Barkley, Mathematics, University of Warwick
Title: Patterns of Turbulence
Abstract: Plane Couette flow -- the flow between two infinite parallel plates moving in opposite directions -- undergoes a discontinuous transition from laminar flow to turbulence as the Reynolds number is increased. Due to its simplicity, this flow has long served as one of the canonical examples for understanding shear turbulence and the subcritical transition process typical of channel and pipe flows. Only recently was it discovered in very large aspect ratio experiments that this flow also exhibits remarkable pattern formation near transition. Steady, spatially periodic patterns of distinct regions of turbulent and laminar flow emerges spontaneously from uniform turbulence as the Reynolds number is decreased. The length scale of these patterns is more than an order of magnitude larger than the plate separation. It now appears that turbulent-laminar patterns are inevitable intermediate states on the route from turbulent to laminar flow in many shear flows. I will explain how we have overcome the difficulty of simulating these large scale patterns and show results from studies of three types of patterns: periodic, localized, and intermittent.

return to top
Date: March 26
Speaker: David Blei, Computer Science, Princeton University
Title: Modeling Science: Topic models of Scientific Journals and Other Large Text Databases
Abstract: A surge of recent research in machine learning and statistics has developed new techniques for finding patterns of words in document collections using hierarchical probabilistic models. These models are called "topic models" because the word patterns often reflect the underlying topics that are combined to form the documents; however topic models also naturally apply also such data as images and biological sequences.
After reviewing the basics of topic modeling, I will describe two related lines of research in this field, which extend the current state of the art.
First, I will describe probabilistic models designed to capture the dynamics of topics as they evolve over time. Many document collections change over time: scientific articles, emails, and search queries reflect evolving content, and it is important to model the corresponding evolution of the underlying topics.
Second, I will describe a probabilistic topic model which can capture correlations between the hidden topics. Previous models assume that the occurrence of the different topics are independent. In many document collections, however, the presence of a topic may be correlated with the presence of another. For example, a document about sports is more likely to also be about health than international finance. In addition to giving quantitative, predictive models of a corpus, topic models provide a qualitative window into the structure of a large document collection. This allows a user to explore a corpus in a topic-guided fashion. I will demonstrate the capabilities of these new models on the archives of the journal Science, founded in 1880 by Thomas Edison. The models are built on the noisy text from JSTOR, an online scholarly journal archive, resulting from an optical character recognition engine run over the original bound journals.
(joint work with M. Jordan, A. Ng, and J. Lafferty)

return to top
Date: April 2
Speaker: Frans Pretorius, Physics, Princeton University
Title: Simulation of Black Hole Collisions
Abstract: The collision of two black holes is thought to be one of the most energetic events in the universe, emitting in gravitational waves as much as 5-10% of the rest mass energy of the black holes. An international effort is presently underway to detect gravitational waves from black hole collisions and other cataclysmic events in the universe. The early success of the detectors will rely on the matched filtering technique to extract what are, by the time the waves reach earth, very weak distortions in the local geometry of space and time. In the case of binary black hole mergers, obtaining the predicted waveforms for use in the matched filters requires numerical solution of the merger process during the final stages of the collision. In this talk I will describe the computational challenges and techniques required to simulate black holes within the framework of Einstein's theory of general relativity, and present results form recent successful simulations of black hole coalescence.

return to top
Date: April 9
Speaker: Jason W. Fleischer, Electrical Engineering, Princeton University
Title: Dispersive shock waves in homogeneous and periodic systems
Abstract: Dispersive shock waves (DSW) are a fundamental type of nonlinear wave and appear in many hydrodynamic settings, including fluids, superfluids, plasma, and optics. Their basic existence conditions are a dispersive medium with positive pressure (e.g. repulsive interactions or defocusing nonlinearity) and a high density/intensity region atop a low-level background. In the ensuing dynamics, different components of the initial hump couple to the background and walk off from each other. Unlike ordinary shock waves, which have a well-defined front due to viscosity, DSWs are characterized by an oscillating front. Here, an overview of DSWs is given in both homogeneous and periodic media. In homogeneous media, particular attention is paid to shock wave interactions and the dynamics of mode coupling, in both one and two dimensions. In periodic media, the focus is on modified dynamics due to the underlying Floquet-Bloch mode structure and the momentum-dependent dispersion profile. The results show enhanced energy transport among modes and bands and represent the opposite nonlinear regime from lattice (gap) solitons. In all cases, theory is compared to recent experiments in nonlinear optical systems, Bose-Einstein condensates, and plasma.

return to top
Date: April 16
Speaker: Daniel Rockmore, Mathematics, Dartmouth College
Title: Fast Fourier Transforms for Semigroups
Abstract: A general version of the Fast Fourier Transform is as an algorithm for the efficient calculation of a change of basis, where the target basis is one that reflects some sort of group invariance. The implicit group action reflects a globabl symmetry of the underlying domain for the data. In this talk we revisit this idea with the goal of extending these notions to the case of semigroups, where the invariance can be local in nature. We discuss in some detail the case of the "rook monoid" and its potential application to the analysis of partial ranking data. This is joint work with Martin Malandro.

return to top
Date: April 23
Speaker: Mikko Haataja, MAE, Princeton University
Title: Heterogeneous Lipid Bilayers: Evolving Microstructures in Biology
Abstract: The design and processing of materials with novel physical and mechanical properties requires a fundamental understanding of the connections between processing, microstructure, and properties. For example, mechanical properties in pure metals and alloys can be varied by manipulating the polycrystalline grain size or the size of the compositional domains through heat treatment, while elastic strain provides a way to tune the optical properties of self-assembled quantum dots during growth. In an analogous manner, the biological function of cell membranes is strongly affected by the details of the local "microstructure".
Typically, microstructural evolution takes place across multiple length and time scales, ranging from atomistic to mesoscopic ones. In this talk I will describe our recent efforts in developing physically-based, coarse-grained continuum models, which bridge the atomistic and mesoscopic scales, to elucidate lateral organization and non-equilibrium dynamics of heterogeneous lipid bilayers. In particular, I will focus on spatially organized, dynamic heterogeneities in the local lipid composition ("lipid rafts") which have been implicated in many important cellular processes including signal transduction, membrane trafficking, cytoskeleton organization, and pathogen entry.

return to top

2005-2006 Collapse/Expand

Date: September 19
Speaker: Naomi Leonard, Mechanical & Aerospace Engineering, Princeton University
Title: Collective Motion in Engineered and Natural Multi-Agent Systems
Abstract: The collective control of mobile, multi-agent systems is motivated by a range of engineering applications that require the coordination of a group of individually controlled systems. A closely related problem focuses on the role of feedback and interconnection in the collective motion of animal groups. Tools from control and dynamical systems can be used to study both engineered and natural mobile networks in a systematic and scalable way. One goal is to prove stability and robustness of designed patterns or emergent behaviors. In this talk I will describe recent collaborative work on models for collective motion based on a planar group of self-propelled particles with steering control. We extend phase models of coupled oscillators to include spatial dynamics and use these models to stabilize and control collective motion patterns. The patterns can be parametrized, in part, by the extent of oscillator synchrony. I will conclude the talk with some discussion of open problems in the area of cooperative control.

return to top
Date: October 10
Speaker: Clancy Rowley, Mechanical & Aerospace Engineering, Princeton University
Title: Low-order models for control of fluids
Abstract: The ability to effectively control a fluid would enable many exciting technological advances, including the design of quieter, more efficient aircraft. Most of the flow control strategies tried so far have been largely ad hoc, and have not used many of the available tools from control theory and dynamical systems, which can guide controller design as well as placement of sensors and actuators. These tools require knowledge of a model of the system in terms of a system of differential equations, and the equations governing a fluid, though known, are too complex for these tools to apply. This talk addresses model reduction techniques, which are used to simplify existing models, to obtain low-order models tractable enough to be used for analysis and control, while retaining the essential physics. These techniques provide a bridge between complex problems and the mathematical tools useful for their analysis.
Specifically, the talk will focus on recent developments of two techniques, Proper Orthogonal Decomposition (POD) and balanced truncation. Each of these techniques has strengths and weaknesses, and we show how ideas from both techniques may be combined, to exploit their strengths. We illustrate the methods by obtaining reduced-order models for a compressible flow past a cavity, and an incompressible channel flow.

return to top
Date: October 17
Speaker: Gunnar Carlsson, Mathematics, Stanford University
Title: Algebraic topology and the statistics of natural images
Abstract: Natural images taken with a digital camera can be viewed as vectors in a high-dimensional vector space whose dimension is the number of pixels. To understand the set of natural images within this vector space is a very interesting problem, but as stated it is very difficult and likely intractable. A. Lee, D. Mumford, and K. Pedersen have created a data set consisting of small (3 by 3) patches, and one can then ask questions about this set. We (V. de Silva, T. Ishkanov, and myself) have used algebraic topological techniques to obtain information about this set, and I will discuss this application of topological methods in this talk. I will also discuss potential applications in compression and in the neuroscience of vision.

return to top
Date: October 24
Speaker: Terence Tao, Mathematics, University of California, Los Angeles
Title: Sparse recovery
Abstract: Suppose one is given a small number of (possibly noisy) linear measurements of a signal. If the number of measurements is less than the number of degrees of freedom of the signal, then one of course cannot reconstruct the signal from the measurements in general. But if one makes the additional hypothesis that the signal is sparse, or at least compressible, then it does become possible to recover the signal accurately, stably, and quickly. The key is decoherence: the measurement basis has to be very "skew" with respect to the sparsity basis. We will survey a number of recent theoretical developments of this idea by several groups and in several contexts (Fourier reconstruction, linear codes, statistical selection.)

return to top
Date: November 7
Speaker: Sal Torquato, Chemistry, Materials Institute & PACM, Princeton University
Title: Bounds on the Optimal Density of Sphere Packings in High Dimensions
Abstract: Sphere packings in high dimensions are of great interest to mathematicians and physicists, and have direct applications in communications theory. Remarkably, no one has been able to provide exponential improvement on a 100-year-old lower bound on the maximal packing density due to Minkowski in d-dimensional Euclidean space \Re^d. The asymptotic behavior of this bound is controlled by 2^{-d} in high dimensions. Using an optimization procedure that we introduced earlier [1] and a conjecture concerning the existence of disordered sphere packings in \Re^d, we obtain a provisional lower bound on the density whose asymptotic behavior is controlled by 2^{-0.7786…d}, thus providing the putative exponential improvement of Minkowski's bound [2]. The conjecture states that a hard-core nonnegative tempered distribution is a pair correlation function of a translationally invariant disordered sphere packing in \Re^d for asymptotically large d if and only if the Fourier transform of the autocovariance function is nonnegative. The conjecture is supported by two explicit analytically characterized disordered packings, numerical simulations in low dimensions, and known necessary conditions that only have relevance in very low dimensions. A byproduct of our approach is an asymptotic lower bound on the average kissing number whose behavior is controlled by 2^{0.2213…d}, which is to be compared to the best known asymptotic lower bound on the individual kissing number of 2^{0.2075…d}. Interestingly, our optimization procedure is precisely the dual of a primal linear program devised by Cohn and Elkies [3] to obtain upper bounds on the density, and hence has implications for linear programming bounds. [1] S. Torquato and F. H. Stillinger, "Controlling the Short-Range Order and Packing Densities of Many-Particle Systems," Journal of Physical Chemistry B, 106, 8354 (2002); ibid, 106, 11406 (2002). [2] S. Torquato and F. H. Stillinger, "New Provisional Lower Bounds on the Optimal Density of Sphere Packings," http://arxiv.org/abs/math.MG/0508381. [3] H. Cohn and N. Elkies, "New upper bounds on sphere packings I," Annals of Mathematics, 157, 689 (2003); H. Cohn, "New upper bounds on sphere packings II," Geometry and Topology, 6, 329 (2002).

return to top
Date: November 14
Speaker: Robert Ghrist, Mathematics, University of Illinois
Title: Homological Methods for Sensor Networks
Abstract: As sensor engineering and manufacturing evolve to produce smaller devices, we will have the problem of dealing with large numbers of very localized objects. What types of global problems can be solved by a swarm of local sensors? Topologists solved a similar problem nearly a century ago. This talk will demonstrate the surprising effectiveness of homology theory in sensor networks.

return to top
Date: November 21
Speaker: Guust Nolet, Geosciences, Princeton University
Title: Seismic tomography: some mathematical aspects
Abstract: "Seismic tomography" is the term geophysicists use for a collection of methods to use seismic waves to image the interior of the Earth, much like in a CAT scan. Tomographic imaging has led to important discoveries, such as the observation that ocean floor subducts to the bottom of the Earth’s mantle and - more recently - that plumes of hot material rise up from the lower mantle.
In its simplest form, the approximations of geometrical optics are applied to high frequency seismic waves. These waves then follow raypaths and the most useful observable is a travel time along the ray: T = \int ds / v(r). In a typical interpretation, \mathcal O (10^6) data with a signal-to-noise ratio of order 1 are inverted for \mathcal O (10^4-10^5) parameters. The mathematical challenge is mostly that of an adequate regularization of the problem that minimizes artifacts. More accurate travel time measurements can be obtained using cross-correlation on digital seismograms with sensitivity to lower frequency. For such waves a first order perturbation theory is needed to include the effects of wave diffraction around small anomalies. The travel time becomes then frequency dependent, and T is given by a volume integral, with an increase by several orders of magnitude in the numerical effort. Finally, for the lowest frequency waves we use the whole waveform as data. These waveforms can be modeled by summation of normal modes, but the problem is inherently nonlinear and again a ray approximation is needed to render the inverse problem feasible. The challenge is to relax this constraint and take effects of diffraction into account. We shall speculate about the possible role of wavelets in meeting these challenges.

return to top
Date: November 28
Speaker: Maria Reznikoff, Mathematics, Princeton University
Title: Thermally-driven rare events and large deviation theory
Abstract: Thermal or stochastic effects are prevalent in physical, chemical, and biological systems. Particularly in small systems, noise can overpower the deterministic dynamics and lead to "rare events," events which would never be seen in the absence of noise. One example is the thermally-driven switching of the magnetization in small memory elements. Wentzell-Freidlin large deviation theory is a mathematical tool for studying rare events. It estimates their probability and also the "most likely switching pathway," which is the pathway in phase space by which rare events are most likely to occur. We explain how large deviation theory and concepts from stochastic resonance may be applied to analyze thermally-activated magnetization reversal in the context of the spatially uniform Landau-Lifschitz-Gilbert equations. The time-scales of the experiment are critical. One surprising and physically relevant result is that in multiple-pulse experiments, nonconvential "short-time switching pathways" can dominate. The effect is dramatic: the usual pathway (connected with the Arrhenius-law) underestimates the probability of switching by an exponential factor.
An advantage of the method via large deviation theory is that it generalizes to systems with spatial variation. To discuss the complications and richness that emerge when spatial variation is taken into account, we consider the (simpler) Allen-Cahn equation. In this context, the rare event of interest is phase transformation from u =–1 to u=+1, and the most likely switching pathway is a pathway through function space. A natural reduced problem emerges in the "sharp-interface limit." We give a brief overview of some results (rigorous in d = 1, heuristic in d > 1.)
The first part of the talk is joint work with Bob Kohn and Eric Vanden-Eijnden. The second part includes work that is also joint with Felix Otto and Yoshihiro Tonegawa.

return to top
Date: December 5
Speaker: Robert Schapire, Computer Science, Princeton University
Title: The Boosting Approach to Machine Learning
Abstract: Machine learning studies the design of computer algorithms that automatically make predictions about the unknown based on past observations. Often, the goal is to learn to categorize objects into one of a relatively small set of classes. Boosting, one method for solving such learning problems, is a general technique for producing a very accurate classification rule by combining rough and moderately inaccurate "rules of thumb." While rooted in a theoretical framework of machine learning, boosting has been found to perform quite well empirically. After introducing the boosting algorithm AdaBoost, I will explain the underlying theory of boosting, including our explanation of why boosting often does not suffer from overfitting. I also will touch on some of the other theoretical perspectives on boosting, and describe some recent applications and extensions.

return to top
Date: February 13
Speaker: Barbara Terhal, IBM
Title: Fault-Tolerant Quantum Computation
Abstract: I will review the theory of fault-tolerant quantum computation and the use of quantum error-correcting codes in future quantum computers. I will discuss the most recent developments in this area.

return to top
Date: February 20
Speaker: Christopher A. Fuchs, Bell Labs, Lucent Technologies
Title: Math Problems from the Far Side of Quantum Information
Abstract: The field of Quantum Information has recently rightly attracted great interest for the technological fruits it may bear. But there is a sect of its practitioners who think it stands a chance to bring us much more than that---namely, that its theoretical tools will give us a means for exploring what quantum mechanics is really all about and for settling some of the deepest problems in physics. The roots of this optimism come from a very old thought: that a quantum state has more to do with representing its user's information, than any inherent physical property of the system to which it is ascribed. What is new and nice is that quantum information teaches us how to formulate this idea precisely and even check its consistency. Nicer still for the mathematics community is the number of juicy mathematical problems the consistency-checking process poses. In this talk, I will review some of the history of this and then quickly settle on a sample problem that has been annoying me a lot lately: the question of the existence of symmetric informationally complete positive-operator-valued measures for finite dimensional Hilbert spaces. I'm not alone---it turns out to be equivalent to a 30-year-old problem in coding theory---but I will say some things about it that you may not have heard before.

return to top
Date: February 27
Speaker: Mung Chiang, Electrical Engineering, Princeton University
Title: Layering As Optimization Decomposition
Abstract: Layered network architecture has traditionally been designed based on engineering heuristics. Recently a mathematically rigorous, practically relevant, and unifying framework has emerged to view the network as a solver of a generalized utility maximization problem, with alternative decompositions of the problem corresponding to different layering schemes, each decomposed subproblem corresponding to a different layer, and functions of variables coordinating the subproblems as the interfaces among the layers. Such decompositions can be carried out both horizontally across geographically disparate network elements and vertically into various functional modules. This talk surveys the recent advances in establishing this framework as a systematic approach to analyze and design protocol stacks in a holistic way that reveals the underlying structures and explores network design alternatives. Connections with distributed subgradient algorithm, convex and nonconvex optimization, stochastic optimization, differential topology, and algebraic geometry will be highlighted.

return to top
Date: March 6
Speaker: Robert Nowak, Electrical and Computer Engineering, University of Wisconsin-Madison
Title: Wireless Sensing, Active Learning and Compressive Sampling
Abstract: Wireless sensor networks promise a fundamentally new approach for gathering information about the physical environment via a distributed network of sensors that can communicate with each other and/or with a (usually distant) fusion center through radio-frequency wireless links. Limited power resources make energy conservation essential in these envisioned sensing systems. Thus, it becomes crucial to strategically decide when, where and how to collect samples and communicate information. Active learning methods adaptively select samples based on previous observations in order to "learn" a target function using as few samples as possible, which could clearly be advantageous in sensor network operations. Compressive sampling refers to taking non-traditional samples in the form of randomized projections of data. Recent results show that compressive sampling can allow one to reconstruct signals from far fewer samples than required by traditional Shannon-Nyquist sampling schemes, again suggesting promising opportunities for wireless sensing. In this talk I will discuss the theory of active learning and compressive sampling, connections to information and coding theory, and some intriguing potential applications to wireless sensing systems.

return to top
Date: March 27
Speaker: Scott Rickard, Electronic and Electrical Engineering, University College Dublin
Title: Sparsity and Source Separation: just DUET
Abstract: Detroit MI, April 2001.
A woman is found stabbed to death in the kitchen of her apartment. The police find that a video recorder in the family room was recording during the murder, but the camera lens cap was on and, as a result, the video portion of the recording reveals nothing. The audio channel of the recording, however, has captured the entire crime. Unfortunately, a stereo was playing loud schmaltzy music during the conversation leading up to the assault, and the speech on the recording cannot be understood. Fortunately, the police have the tape that was playing at the time, but traditional approaches for removing the interfering music from the mixture fail.
Princeton NJ, June 2002.
Murder victim gets the last word - case closed.
In this talk I will discuss the sparse revolution which is occurring in signal processing which is allowing researchers to solve systems of equations with more unknowns than constraints. We've all been taught that if we have 2 unknowns, we require 2 equations to solve for the unknowns. For 3 unknowns, we need 3 equations (and 4 require 4, and so on...). This is not true - as long as you're willing to cheat. For example, we 'cheat' in cocktail parties when we listen to one person while a dozen speak in the background. Mathematically, we would need 13 ears to eliminate the dozen unwanted speakers to allow us to focus on the one speaker of interest. The DUET Blind Source Separation Algorithm mimics this human auditory ability in that it can separate an arbitrary number of sources from just two mixtures (such as those heard by two ears in a cocktail party). I will reveal how we use sparsity to cheat and thus solve the problem of more unknowns than equations. Also, I will discuss various related modifications of DUET, one of which was used to solve the above murder case. This talk will feature a live demonstration of DUET.

return to top
Date: April 10
Speaker: Lisa Fauci, Mathematics, Tulane University
Title: Spirochetes and spermatozoa: Fluid dynamic models of microorganism motility
Abstract: The observed swimming behavior of a motile microorganism is the result of a complex interplay between mechanisms of internal force generation, the passive elastic properties of its structure, and a surrounding viscous fluid. In this talk, we will focus on two very different types of microorganisms: the spirochetes, which are a type of bacteria characterized by an efficient mode of motility that allows them to screw through viscous fluids and mucosal surfaces, and spermatozoa, that undulate as a result of the action of thousands of molecular motors positioned along the flagellum. We will present mathematical and computational models that couple the internal force generating mechanisms of these microorganisms with external fluid mechanics. We will describe our methodology, which includes both the method of regularized Stokeslets and the immersed boundary method. We will discuss recent successes as well as challenges associated with these models.

return to top
Date: April 11, rm 314
Speaker: Christian Van den Broeck, Theoretical Physics, Hasselt University, Belgium
Title: From Maxwell demon to Brownian refrigerator
Abstract: Maxwell was under the impression that it should be possible to violate the second law of thermodynamics provided one could operate on a molecular scale. This comment was the beginning of a discussion stretching over the whole of the 20th century involving outstanding physicists including Smoluchowski, Onsager, Szilard, Feynman and Landauer. The issue has now become of more than academic interest because of recent developments in nanotechnology and molecular biology. We present a simplification of the Feynman ratchet that can be studied in detail by hard disk molecular dynamics and for which an exact microscopic calculation is possible. We will show how this construction can be used as a Brownian motor but also as a Brownian heat pump and refrigerator.

return to top
Date: April 17
Speaker: Geoff Vallis, Geosciences / Atmospheric & Oceanic Sciences, Princeton University
Title: Turbulence and Large-scale Circulation in the Ocean and Atmosphere
Abstract: The large-scale circulation is not only affected but is essentially effected by turbulent flows. This turbulence is not the small-scale turbulence that is (unfortunately) sometimes connoted by the word turbulence, but is turbulence up to the scale of the large-scale flow itself. This is largely two-dimensional, so-called geostrophic turbulence. We will discuss what is known and what is unknown about such flow, the problems of both simulating it and of understanding it, and whether these two are the same.

return to top
Date: April 24
Speaker: Lee Deville, Courant Institute of Mathematical Sciences, New York University
Title: Coherence in stochastic dynamical systems
Abstract: It is known that random perturbations to dynamical systems can be small and irrelevant, or, alternately, so large as to overwhelm the dynamics. More interesting are cases where small random perturbations introduce qualitative changes in a system without introducing significant randomness. In effect, these are generating noise-induced, yet coherent, dynamics. We will show that this phenomenon is present in a large class of dynamical systems and describe several examples in detail. The examples will include stochastically-forced ODEs and PDEs, and Markov chains.

return to top
Date: April 27, 8pm, A02 McDonnell Hall
Speaker: Distinguished Lecture Series Peter Shor, Mathematics, Massachusetts Institute of Technology
Title: Quantum Computers: How physics experiments might solve mathematical problems
Abstract: Quantum computers are hypothetical devices which use the principles of quantum mechanics to perform computations. For some difficult computational problems, including the cryptographically important problems of prime factorization and finding discrete logarithms, the best algorithms known for classical computers are exponentially slower than the algorithms known for quantum computers. Although they have not yet been built, quantum computers do not appear to violate any fundamental principles of physics. I will explain how quantum mechanics provides this extra computational power. One of the main difficulties in building quantum computers is in manipulating coherent quantum states without introducing errors or losing coherence. This problem can be alleviated by the use of quantum error correcting codes; if a quantum computer can be built with only moderately reliable hardware, then software can be used to make it extremely reliable. I will discuss these results as well.

return to top
Date: May 1
Speaker: Eric Vanden-Eijnden, Courant Institute of Mathematical Sciences, New York University
Title: Rare events in complex systems: How to determine their transition pathways and rate?
Abstract: The dynamical behavior of many systems arising in physics, chemistry, biology, etc. is dominated by rare but important transition events between long lived states. Important examples include nucleation events during phase transition, conformational changes of macromolecules, or chemical reactions. Understanding the mechanism and computing the rate of these transitions is a topic that has attracted a lot of attention for many years. In this talk, I will discuss the theoretical background and algorithmic details of the finite-temperature string method, which gives a firm theoretical background to the concept of reaction coordinate to describe these transitions, and allows to determine their pathways and rate. The string method will be illustrated via several examples.

return to top

2004-2005 Collapse/Expand

Date: September 13, 2pm, Joseph Henry Room, Jadwin Hall
Speaker: Alexander Vardy, University of California, San Diego
Title: Old Problems and New Results in Coding Theory
Abstract: Coding theory was born in 1948 with the work of Claude Shannon, who proved that for every information rate R up to channel capacity, there exists a code of rate R that guarantees a vanishing probability of decoding error. Shannon, however, did not tell us how to find such codes nor how to decode them. It was recognized early on that codes with good Hamming distance can correct many errors, while codes endowed with algebraic structure admit efficient algebraic decoding algorithms. This has led to over 50 years of research in algebraic and combinatorial coding theory. We will survey several key problems and new results in this area. In particular, we'll elaborate upon a new asymptotic improvement of the Gilbert-Varshamov bound and upon recent methods for decoding Reed-Solomon codes using bivariate polynomial interpolation.
About 10 years ago, the field of coding theory was transformed by the discovery of codes defined on certain graphs, with no algebraic structure, that perform extremely close to the Shannon capacity under probabilistic message-passing decoding. We will briefly review this exciting development, and point out the challenges that lie ahead in the area of "probabilistic" coding theory.

return to top
Date: September 27
Speaker: Walter Willenger, AT&T Labs Research
Title: Internet Topology Modeling and the Role of Design
Abstract: The assumption that the Internet has become sufficiently large-scale and homogeneous to be amenable to statistical physics-inspired analysis techniques has recently led to the popular "scale-free" models of Internet topology, which are claimed to explain, for example, the structure of the Internet's router-level connectivity graph by simple random processes that are void of any engineering tradeoffs. An alternative perspective, motivated by engineering, suggests that nonrandom design rather than randomness plays a primary role in the construction and evolution of complex systems, and the complex structure of highly engineered technology and of biological systems is viewed as the natural by-product of Highly Optimized Tradeoffs (HOT) between system-specific objectives and constraints.
This talk shows how and why the latter view, when applied to the study of router-level Internet connectivity, results in conclusions that are fully consistent with the real Internet, but are the exact opposite of what the scale-free models claim. The reasons for reaching such divergent conclusions about one and the same system go well beyond the Internet and scale-free models and are endemic in the application of ideas from statistical physics to problems in technology and biology, where it is assumed that the details related to a complex system's design, functionality, constraints, and evolution (i.e., all ingredients that make engineering and biology different from physics) can be safely ignored in favor of random ensembles and their emergent properties.

return to top
Date: October 4
Speaker: Greg Forest, Institute for Advanced Materials, NanoScience and Technology, University of North Carolina, Chapel Hill
Title: What's Applied and Computational Math Got to Do with High-Performance Nano-Composites?
Abstract: Nano-composite materials of interest for this lecture consist of high aspect ratio, spheroidal macromolecules, known as "nematic polymers", in a traditional polymer matrix. Rod-like, tube-like, and platelet molecules are added to traditional polymeric materials to enhance a variety of properties, from thermal or electrical conductivities to barrier and mechanical properties. There is no direct theoretical prediction that begins with the composition of nano-inclusions and matrix, tracks the flow into films, fibers, or molded parts, and then infers the effective properties of the composite. Each stage is a mathematical theory, modeling, and simulation challenge; modeling the entire nano-composite pipeline is a conceivable target. Progress and open problems that remain will be discussed, aimed at the graduate students in the Program.

return to top
Date: October 11
Speaker: Philip Holmes, PACM, MAE and CSBMB, Princeton University
Title: Optimal decisions: From neural spikes, through stochastic differential equations, to behavior
Abstract: There is increasing evidence from in vivo recordings in monkeys trained to respond to stimuli by making left- or rightward eye movements, that firing rates in certain groups of 'visual' neurons mimic drift-diffusion processes, rising to a (fixed) threshold prior to movement initiation. This supplements earlier observations of psychologists, that human reaction time and error rate data can be fitted by random walk and diffusion models, and has renewed interest in optimal decision-making ideas from information theory and statistical decision theory as a clue to neural mechanisms.
I will review some results from decision theory and stochastic ordinary differential equations, and show how they may be extended and applied to derive explicit parameter dependencies in optimal performance that may be tested on human and animal subjects. I will then describe a biophysically-based model of a pool of neurons in a brainstem organ - locus coeruleus - that is implicated in widespread norepinephrine release. This neurotransmitter can effect transient gain and response threshold changes in cortical circuits of the type that the abstract drift-diffusion analysis requires. I will argue that, in spite of many gaps and leaps of faith, a rational account of how neural spikes give rise to simple behaviors is beginning to emerge.
This work is in collaboration with Eric Brown, Rafal Bogacz, Jeff Moehlis and Jonathan Cohen (Princeton University), and Ed Clayton, Janusz Rajkowski and Gary Aston-Jones (University of Pennsylvania). It is supported by the National Institutes of Mental Health.

return to top
Date: October 18
Speaker: Larry Peterson, Computer Science, Princeton University
Title: PlanetLab: A Platform for Introducing Disruptive Technology into the Internet
Abstract: PlanetLab is a geographically distributed overlay network designed to support the deployment and evaluation of planetary-scale network services. Two high-level goals shape its design. First, to enable a large research community to share the infrastructure, PlanetLab provides distributed virtualization, whereby each service runs in an isolated slice of PlanetLab's global resources. Second, to support competition among multiple network services, PlanetLab decouples the operating system running on each node from the network-wide services that define PlanetLab, a principle referred to as unbundled management. This talk describes how PlanetLab realizes these two goals, and highlights several novel network services running on PlanetLab.

return to top
Date: November 1
Speaker: Ioannis Kevrekidis, PACM and Chemical Engineering, Princeton University
Title: Equation-free modeling for complex, multiscale systems
Abstract: In current modeling, the best available descriptions of a system often come at a fine level (atomistic, stochastic, microscopic, individual-based) while the questions asked and the tasks required by the modeler (prediction, parametric analysis, optimization and control) are at a much coarser, averaged, macroscopic level. Traditional modeling approaches start by first deriving macroscopic evolution equations from the microscopic models, and then bringing our arsenal of mathematical and algorithmic tools to bear on these macroscopic descriptions.
Over the last few years, and with several collaborators, we have developed and validated a mathematically inspired, computational enabling technology that allows the modeler to perform macroscopic tasks acting on the microscopic models directly. We call this the "equation-free" approach, since it circumvents the step of obtaining accurate macroscopic descriptions.
I will argue that the backbone of this approach is the design of (computational) experiments. In traditional numerical analysis, the main code "pings" a subroutine containing the model, and uses the returned information (time derivatives, function evaluations, functional derivatives) to perform computer-assisted analysis. In our approach the same main code "pings" a subroutine that sets up a short ensemble of appropriately initialized computational experiments from which the same quantities are estimated (rather than evaluated). Traditional continuum numerical algorithms can thus be viewed as protocols for experimental design (where "experiment" means a computational experiment set up and performed with a model at a different level of description).
Ultimately, what makes it all possible is the ability to initialize computational experiments at will. Short bursts of appropriately initialized computational experimentation -through matrix-free numerical analysis and systems theory tools like variance reduction and estimation- bridges microscopic simulation with macroscopic modeling. Remarkably, if enough control authority exists to initialize laboratory experiments "at will", this computational enabling technology can become a set of experimental protocols for the equation-free exploration of complex system dynamics.

return to top
Date: November 8
Speaker: Ronald Coifman, Mathematics, Yale University
Title: Multiscale Analysis and Diffusion Geometries on Digital Data Sets
Abstract: We will discuss simple methodologies for analyzing and discovering geometric structures in massive data sets. We introduce multiscale Harmonic analysis on graphs and on subsets of Euclidean spaces. The methods augment spectral graph theory, kernel principal component analysis, manifold learning and other methods from machine learning.

return to top
Date: November 15
Speaker: Jim Stone, PACM and Astrophysical Sciences, Princeton University
Title: Astrophysical Gas Dynamics
Abstract: Most of the visible matter in the Universe is a plasma, that is a dilute gas of electrons, ions, and neutral particles. In many cases the dynamics of this plasma is described to a good approximation by the equations of compressible hydrodynamics, magneto-hydrodynamics (in the case that magnetic fields are present), or radiation MHD (in the case that photons provide significant energy or momentum transport). Studying multidimensional, time-dependent and/or highly nonlinear processes in astrophysical plasmas usually requires numerical methods, however developing accurate and robust methods for compressible MHD and/or radiation MHD is still an active area of research in applied mathematics. I will describe some problems in astrophysics which motivate the development of such methods, describe recent advance in numerical algorithms for MHD and their implementation on parallel processors, and describe some of what we have learned from application of the methods.

return to top
Date: November 22
Speaker: Eduardo Sontag, Math and BioMaPS Institute for Quantitative Biology, Rutgers University
Title: Qualitative/Quantitative Analysis of a Class of Biological Networks
Abstract: The analysis of signaling networks constitutes one of the central questions in systems biology: there is an pressing need for powerful mathematical tools to help understand, quantify, and conceptualize their information processing and dynamic properties. Approaches based upon detailed modeling and simulation are hampered by the fact that is virtually impossible to experimentally validate the form of the nonlinearities used in reaction terms, or, even when such forms are known, to accurately estimate coefficients (parameters). In this presentation, we show how some signaling systems may be profitably studied by first decomposing them into several subsystems, each of which is endowed with certain "qualitative" mathematical properties. These properties, in conjunction with a relatively small amount of "quantitative" data, allow the behavior of the entire, reconstituted system, to be deduced from the behavior of its parts. This novel approach emerged originally from our study of possible multi-stability or oscillations in feedback loops in cell signal transduction modeling, but turns out to be of more general applicability. (Most of the work reported in this talk was carried out in collaboration with D. Angeli, and parts of it with J. Ferrell, G. Enciso, and P. de Leenheer.)

return to top
Date: November 29
Speaker: Jelena Kovacevic, Center for BioImage Informatics, Carnegie Mellon University
Title: Frames and the Fundamental Inequality
Abstract: In recent years, we have seen an explosion of work on frames, in particular finite frames. We find finite tight frames when the lengths of the frame elements are predetermined. In particular, we derive a "fundamental inequality" which completely characterizes those sequences which arise as the lengths of a tight frame's elements. Furthermore, using concepts from classical physics, we show that this characterization has an intuitive physical interpretation. At the end of the talk, we also examine some recent applications of frames.

return to top
Date: December 6
Speaker: Emily Carter, PACM and Mechanical & Aerospace Engineering, Princeton University
Title: Reduced Scaling Methods for Quantum Electronic Structure
Abstract: The problem of solving the Schroedinger equation in quantum mechanics, in order to describe the behavior of N electrons, is in principle an N! hard problem in an infinite basis. This is due to the need to describe the correlated motion of electrons. Some typical approaches to solving this 3N-dimensional PDE will be introduced, including mean-field and many-body methods. An analysis of their scaling properties will be given. My research group's particular strategies for reducing the prohibitive scaling of these methods while retaining accuracy of the solution will be presented. These schemes are based on simple physical and mathematical principles, for both molecular quantum chemistry and for condensed matter electronic structure. We will end with an outlook of the applied mathematical research challenges that remain for describing large numbers (e.g., thousands) of atoms with quantum mechanics. When these challenges are overcome, we will be able to predict the behavior of complicated molecules and materials with unprecedented fidelity.

return to top
Date: January 31
Speaker: Daryl Pregibon, Google Labs
Title: Graph Mining
Abstract: Transactional data that occurs in telecommunications, financial, and retail applications can be represented as a graph. The size of such graphs can be very large so that mining such data poses significant technical challenges. We discuss our experience in mining large graphs paying special attention to the dynamic nature of the underlying applications, namely that the data presents itself not as a static data set but rather as a continuous data stream. We introduce a definition of a dynamic graph that has served us well in representing telecommunications data. We illustrate the ideas with examples from toll fraud detection.
Joint work with Corinna Cortes and Chris Volinsky

return to top
Date: February 8, Carl Icahn Lab 101
Speaker: Joshua Plotkin, Harvard University
Title: Selection pressures on proteins at the genomic scale: Applications to microbial evolution
Abstract: Joint with the Lewis-Sigler Institute & EEB

return to top
Date: February 14
Speaker: Robert Vanderbei, Operations Research and Financial Engineering, Princeton University
Title: On Fair and Balanced Presentations of Election Data
Abstract: The media has made much of the red-blue divide in America. As is well known, the sparsely populated states are mostly republican whereas the densely populated urban areas are mostly democratic. This creates interesting challenges in data representation which will be discussed.

return to top
Date: February 21
Speaker: Vincent Poor, Electrical Engineering and Applied Mathematics, Princeton University
Title: Signal Processing and Wireless Networks
Abstract: A major issue in today's wireless world is the dramatic increase in demand for new capacity and higher performance of wireless networks. The development of these capabilities is limited severely by the scarcity of two of the principal resources in wireless networks, namely energy and bandwidth. Consequently, the community has turned to a third principal resource, the addition of intelligence throughout the network, in order to exploit increases in processing power afforded by Moore's Law type improvements in microelectronics. This talk will focus on two aspects of this phenomenon: the effects of advanced node-level signal processing on the higher-layer performance of wireless communication networks, including energy efficiency, spectral efficiency, throughput and delay; and the use of advanced signal processing principles, including collaborative beam-forming, sensor scheduling, and distributed learning, in the design, deployment and operation of wireless sensor networks.

return to top
Date: February 28
Speaker: Nigel Boston, University of Wisconsin
Title: Invariant-Based Face Recognition
Abstract: After a brief review of recent striking applications of algebra to engineering and computer science, the currently significant problem of face recognition is addressed. We introduce a new approach to obtaining invariants of Lie groups adapted to this problem and describe its success in implementations.

return to top
Date: March 7
Speaker: Weinan E, Applied Mathematics and Mathematics, Princeton University
Title: Progresses and Challenges in Multiscale Modeling
Abstract: In the last several years, there has been tremendous growth of interest on multiscale modeling from many scientific and engineering disciplines. What are the issues involved? How much progress has been made? What are the challenges that we face in order to realize the full potential of multiscale modeling? This talk presents a personal view on these and related questions. We will begin with a quick discussion of the general issues in multiscale modeling. We then review some of the most successful multiscale methods, including the Car-Parrinello method and the quasicontinuum method for crystalline solids. In the second half of talk, we will focus on the problems from complex fluids and micro-fluidics. We end the talk with a canonical example in multiscale modeling, the contact line problem.

return to top
Date: March 21
Speaker: John Benedetto, University of Maryland
Title: Finite frames and quantum detection
Abstract: We discuss quantum measurement in terms of positive operator-valued measures (POMs). For any tight frame with frame constant 1 for a separable Hilbert space there is an associated POM. Our setup is d-dimensional Hilbert space H and frames for H consisting of N elements. H represents a physical system, and it is known that the state x of the system is in E, a set of N given possible states. The problem is to perform a measurement in order to determine x. This is equivalent to constructing a POM on the subsets of E with a natural probabilistic property. Because of the relationship with frames, the problem reduces to constructing a tight frame with frame constant 1 which minimizes a probability of detection functional defined in terms of E. A compactness argument shows the existence of a solution. We solve the problem using techniques from Lagrangian mechanics and properties of SO(N) with the goal of constructing solutions numerically from the resulting equations. Geometrically uniform and Grassmannian frames are natural background material. This is a collaboration with Andrew Kebo.

return to top
Date: March 28
Speaker: Nick Duffield, AT&T
Title: Challenges for Using Sampled Traffic Measurements
Abstract: Traffic measurements are increasingly sampled due to ever growing line rates and concomitant traffic volumes. On the other hand, measurement-based applications increasingly depend on fine grained traffic characterization. Can these applications work effectively with existing sampled measurements? And if not, can we better match sampling techniques to applications? This talk describes the challenges and limitations for using sampled traffic measurements, and some recent approaches that move beyond traffic sampling methods in predominant use today.

return to top
Date: April 4
Speaker: David Johnson, AT&T
Title: 33 Years of Bin Packing
Abstract: In the bin packing problem, one is given a list of 1-dimensional items and asked to pack them into a minimum number of unit-capacity bins. This was one of the first NP-hard problems to be studied from the "approximation algorithm" point of view, and over the years it has served as a laboratory for the study of new questions about approximation algorithms and the development of new techniques for their analysis. In this talk I present a brief survey of this history, covering worst-case, average-case, and experimental results. The latter have led to many interesting conjectures and theorems, as well as the new "sum-of-squares" algorithm for the problem.

return to top
Date: April 11
Speaker: Pino Martin, Mechanical & Aerospace Engineering, Princeton University
Title: A Parallel Implicit Method for the Direct Numerical Simulation of Compressible Turbulent Flows
Abstract: The detailed simulation of compressible turbulent flows requires solving the conservation of mass, momentum and energy equations. For direct numerical simulations (DNS) all possible length scales and time scales must be resolved by the numerical method. Thus, DNS requires accurate representation of time-dependent wave propagation with high wave number (or high frequency) and small amplitude waves. Thus, numerical methods with minimal dissipation and dispersion properties are necessary to obtain accurate results.
In addition, gathering turbulence statistics requires large amounts of computing time because the simulations must be run on very large grids for many thousands of time steps. Generally, explicit Runge-Kutta methods are used to approximate the time derivative because they have large stability limits and are easy to program. In this seminar, I will present a new implicit method for the time integration that yields significantly reduced computational time of typical DNS of compressible flows while providing an accurate representation of the solution.

return to top
Date: April 13, 8pm, A02 McDonnell Hall
Speaker: Distinguished Lecture Series David Donoho, Department of Statistics, Stanford University
Title: More Unknowns than Equations? Bring it on!
Abstract: Everything you were taught about underdetermined systems of linear equations is wrong... Okay, that's too strong. But you have been taught things in undergraduate linear algebra which, if you are an engineer or scientist, may be holding you back. The main one is that if you have more unknowns than equations, you're lost. Don't believe it. At the moment there are many interesting problems in the information sciences where researchers are currently confounding expectations by turning linear algebra upside down: An imaging system can produce an accurate N-pixel image using only N 1/4 log3 (N) (specially chosen) samples to reconstruct it, far fewer than the N pixel samples you might have naively thought. A Fourier imaging system can observe just the lowest frequencies of a sparse nonnegative signal and perfectly reconstruct all the unmeasured high frequencies of the signal. a communications system can transmit a very weak signal perfectly in the presence of intermittent but arbitrarily powerful jamming. Moreover, in each case the methods are convenient and computationally tractable. Mathematically, what's going on is a recent explosion of interest in finding the sparsest solution to certain systems of underdetermined linear equations. This problem is known to be NP-Hard in general, and hence the problem sounds intractable. Surprisingly, in some particular cases, it has been found that one can find the sparsest solution by l 1 minimization, which is a convex optimization problem and so tractable. Many researchers are now actively working to explain and exploit this phenomenon. It's responsible for the examples given above. In my talk, I'll discuss that this curious behavior of l 1 minimization and connect with some deep mathematics and a broad range of fun applications.

return to top
Date: April 18
Speaker: David Cai, New York University
Title: Modeling of large-scale neuronal network dynamics
Abstract: It has been shown experimentally that spontaneous cortical activity in the absence of sensory inputs modulates stimulus-evoked activity and is correlated with behavior. In the visual cortex, there is a close relationship between ongoing spontaneous activity and the spontaneous firing of a single neuron. There are dynamic switchings amongst these spontaneous cortical states, which may span several hypercolumns spatially and are closely associated to orientation maps. To study theoretically these spatially coherent patterns of spontaneous activity, which emerge in a fluctuation-dominated neuronal network with anisotropic long-range cortical couplings in addition to isotropic short-range interactions, we have developed a coarse-grained representation of neuronal network dynamics in terms of (1+1)-D kinetic equations, which are derived via a novel moment closure, directly from the original large-scale integrate-and-fire (I&F) network. This powerful kinetic theory captures the full dynamic range of neuronal networks — from the mean-driven limit (a limit such as the number of neurons N\rightarrow\infty, in which the fluctuations vanish) to the fluctuation-dominated limit (such as in small N networks or sparsely connected networks). Both analytical insights and scale-up of numerical representation can be achieved via this kinetic approach. We illustrate the power of the theory by studies of the dynamical properties of networks of various architectures, including excitatory and inhibitory neurons of both simple and complex type, which exhibit rich dynamic phenomena, such as, transitions to bistability and hysteresis, even in the presence of large fluctuations. To overcome the loss of detailed spike information in many coarse-grained procedures, we have further developed a hybrid theoretical framework to retain spike information by embedding a sub-network of point neurons within, and fully interacting with, a coarse-grained network of dynamical background. Comparison with full numerical simulations of the original I&F network establishes that our kinetic theory and embedded network approach are dynamically very accurate and numerically extremely efficient.

return to top
Date: April 25
Speaker: Sergio Verdu, Applied Mathematics and Electrical Engineering, Princeton University
Title: Discrete Denoising
Abstract: Finite-alphabet signals corrupted by discrete noisy channels arise naturally in a wide range of applications spanning fields such as statistics, engineering, and computer science. Examples include DNA sequence analysis and processing, text correction, Hidden Markov model state estimation, and image denoising. While the field of filtering or denoising of continuous-alphabet signals has a long history, the field of discrete denoising has seen far less progress.
In many discrete denoising applications, a good model for the randomness of the noisy channel is known, whereas the statistical description of the noiseless signal is either unknown or too complex. It is therefore of considerable interest to pose the problem of discrete universal denoising where no knowledge exists about the statistics of the noiseless signal while the channel statistics are assumed known.
I will present the DUDE algorithm for discrete universal denoising which has linear complexity and attains universal optimality in a stochastic sense as well as a stronger semi-stochastic sense. I will also show several DUDE-based algorithms for channel decoding of systematically encoded redundant data.
Joint work with E. Ordentlich, G. Seroussi, M. Weinberger and T. Weissman.

return to top

2003-2004 Collapse/Expand

Date: September 29
Speaker: Weiqing Ren, Mathematics, Princeton University
Title: Heterogeneous Multiscale Methods for the Modeling of Fluids
Abstract: We apply the framework of the heterogeneous multiscale methods to develop numerical methods for the study of macroscale dynamics of fluids in situations where either the constitutive relation is not explicitly available or the macroscopic model is invalid in part of the computational domain. The methods rely on an efficient coupling between the macroscopic and microscopic models. The continuum hydrodynamics is employed as the macroscopic model while molecular dynamics serves as the microscopic model and is used to supply the necessary data for the macroscopic model. Scale separation is exploited so that macroscopic variables can be evolved in macroscopic spatial/temporal scales using data that are predicted based on molecular dynamics on microscale spatial/temporal domains. Applications to complex fluids and contact line dynamics are presented.

return to top
Date: October 6
Speaker: Cyrill Muratov, NJIT
Title: Signal transmission by autocrine cells in model epithelial layers
Abstract: Autocrine signaling induced by growth factors is crucial in various stages of development and in adult multicellular organisms across species. At the present level of complexity, systematic evaluation of cell communication mechanisms is next to impossible without mathematical modeling of cell signaling networks. In this talk, I will discuss recent results of our mechanistic modeling and analysis of Epidermal Growth Factor Receptor (EGFR)-mediated cell communication. I will first introduce a modeling framework which is relevant to the development and physiology of epithelial layers and to a number of in-vitro experimental formats. Mathematically, this leads to a series of interesting nonlocal/discrete nonlinear problems. I will then concentrate on the mechanism in which autocrine positive feedback loops are established by ligand-activated ligand release regulated by EGFR via a signaling network consisting of an autocrine switch (an intracellular protease) and a messenger (a secreted EGFR ligand). Such autocrine relays are found to be capable of supporting traveling waves with a number of unusual properties, such as a non-monotone dependence of the wave speed on the ligand-receptor binding rate. I will then consider the effect of cell discreteness in a physiologically relevant context and obtain the characteristics of discrete traveling waves and propagation failure. The analysis allows to characterize signal transmission in epithelial layers in terms of the biophysical and geometric parameters of the problem.

return to top
Date: October 13
Speaker: Markos Katsoulakis, University of Massachusetts
Title: Coarse-grained stochastic processes and Monte Carlo simulations in lattice systems
Abstract: In this talk we present a new class of coarse-grained stochastic processes and corresponding Monte Carlo simulation metho