Madeleine Udell | Academic

Research

Sigmoidal Programming

The problem of maximizing a sum of sigmoidal functions over a convex constraint set arises in many application areas. This objective captures the idea of decreasing marginal returns to investment, and has applications in mathematical marketing, network bandwidth allocation, revenue optimization, optimal bidding, and lottery design. It turns out that the general problem is NP-hard to approximate, but our branch-and-bound algorithm often finds solutions in reasonable time. To illustrate the power of this approach, we compute the optimal positions which might have allowed the candidates in the 2008 United States presidential election to maximize their vote shares. Manuscript available here

Graph Partitioning for Distributed Optimization

Optimization provides a powerful framework for solving problems ranging from machine learning to supply chain optimization. However, convex optimization procedures, whose solutions are computationally efficient and provide guarantees of optimality, are currently limited to problems with fewer than 100,000 variables. In order to solve the large-scale problems that frequently arise in machine learning and statistical applications, a distributed approach is needed.

The alternating directions method of multipliers (ADMM) is one technique for distributed optimization being explored by Professor Stephen Boyd at Stanford. ADMM partitions the variables across different nodes, each of which performs a separate optimization over its variables, while holding the values of the other variables fixed. Between iterations, the nodes compare their answers, update the values of the variables held fixed, and recompute until convergence is reached.

Bipartite Graph
A Graph Partitioning

How should the variables be partitioned in order to converge as quickly as possible? One can think of the variables and constraints in a problem as a bipartite graph, and use ideas from graph theory in order to find the optimal partition. I am currently investigating whether graph clustering and graph coloring heuristics based on the spectrum of the matrices associated with the graph may improve the convergence time of the algorithm.

Manifold learning

The general problem of mapping a data set in a high-dimensional space into a lower-dimensional space occurs frequently in scientific applications. Examples include visualizing high-dimensional data in 3D, finding the path a protein takes as it unfolds, and discovering the shape of a molecule using cryo-electron microscopy. Traditional linear approaches to such problems include regression analysis and PCA. However, in cases where the data are drawn from a manifold that is not isomorphic to Rn, linear techniques are bound to fail: no straight line is a good fit through a circle. Diffusion mapping techniques, of which Laplacian eigenfunctions are an example, present a way to find these nonlinear manifolds in large data sets by setting up a diffusion on the dataset, and using the eigenvectors of this diffusion operator as a basis for a lower-dimensional representation of the space.

With Professor Peter Jones at Yale, I studied a recent proof that helped to explain the empirical robustness of diffusion mapping methods, which rarely come with performance guarantees, by abstracting to a continuous setting, where one can show that diffusion coordinates provide a low-distortion mapping for neighborhoods of arbitrary smooth Riemannian manifolds. I also studied the application of eigenfunction maps to a problem in cryo-electron microscopy, in which the challenge was to recover the shape of the underlying molecule from its projected images taken at random, unknown angles. In this case the underlying manifold is the 2-sphere: the set of angles from which the pictures can be taken. By identifying the neighbors of each radial line in each projected image, we were able to construct a diffusion on the radial lines that allowed the reconstruction of the original 3D density map. My senior essay [.pdf] was awarded the Henry Edward Ellsworth Prize.

Condensed Matter Physics

I began my research career the summer after my freshman year in a computational physics lab, studying the electronic properties of gallium nitride nanowires with Yale Professor Sohrab Ismail-Beigi under a grant from Yale's Perspectives on Science program. Using the tight-binding approximation to the Schrodinger equation, we simulated wires of various different sizes and geometries to understand and predict how the presence of edges and corners changed the electric properties of the nanowire compared with bulk gallium nitride. We hoped to link experimental results in nanowires fabrication with theoretical predictions, advancing understanding of these novel structures. Since computer simulations can run much more quickly than physical experiments can be conducted, we hoped to help guide experimental goals in synthesizing nanowires for use in computers or in light emitting diodes.

I studied the effects of hydrodynamic correlations on particle motion with Yale Professor Eric Dufresne during the spring and summer of 2008. Our research was inspired by the observation that sedimenting particles can create patterns that look highly disordered and chaotic, although their motion is governed by the non-turbulent limit of the Navier-Stokes equation, in which the nonlinear term in the equation is taken to zero. We hoped that by understanding this limit, we might better understand the origins of chaos in the full equation. I simulated the motions of particles sedimenting under gravity to create chaotic trajectories, using the Matlab scripting language. I also performed an experiment using holographic optical tweezers to measure the correlations in the motions of polystyrene particles in aqueous solution.

Cosmology
Gravitational Waves
http://www.ligo.caltech.edu

I spent summer 2007 at Caltech with the Laser Interferometer Gravitational Wave Observatory (LIGO) under an NSF REU. My work at LIGO stimulated much of my interest in statistical techniques for finding a signal in very noisy data. Among other projects, LIGO is trying to capture the stochastic gravitational wave background (SGWB) produced during the earliest moments after the big bang. The data would be a tremendous boon to cosmologists, since the universe was opaque to electromagnetic radiation - but transparent to gravitational waves - until it cooled enough for atoms to form about 300,000 years after the big bang. Theorists describe the SGWB using the spherical harmonics basis, and so at LIGO I worked with the data analysis team to create software to express the signal (and the noise) measured in that basis. I was glad to have the opportunity to present my research at a Caltech summer research colloquium, at the Yale Physics Club, and at the 2008 Conference for Undergraduate Women in Physics.


Papers and Presentations


Teaching


Curriculum vitae