Solving Symmetric Diagonally Dominant Linear Systems

By Richard Peng (Carnegie Mellon University)

Monday, November 22

Richard PengAbstract: Solving linear systems, Ax=b, is a classical problem that has been well-studied. The problem where A is symmetric diagonally dominant (SDD) occurs ubiquitously in combinatorial optimization, computer vision, computer graphics and machine learning. In the first half of this talk we will give a brief overview of these applications, including a few problems arising from image segmentation in a bit more detail. In the past decade, a multitude of specialized solvers have been developed using preconditioned iterative methods. Most of the recent work focuses on algorithms that efficiently find ultra-sparse 'equivalents' of graphs, where equivalence is defined through spectral condition numbers. In the second half of the talk we present an algorithm that takes a graph G with n vertices, n-1+m edges and a value k, produces an incremental sparsifier with n-1 + m/k edges such that the condition number is bounded by O(klog^2n) (ignoring loglog factors). This in turn gives an algorithm that solves SDD linear systems with m non-zero entries at a cost of roughly O(mlog^2n). This is joint work with Yiannis Koutis and Gary Miller.

Online Stochastic Ad Serving: Theory and Practice

By Vahab Mirrokni (Google Research)

Monday, November 1

Vahab MirrokniAbstract: As an important part of any ad system, online ad serving is a rich source of challenging algorithmic and stochastic optimization problems. In this talk, I will survey recent algorithmic results known in the context of online ad serving in various ad systems with a main focus on graphical (or display) ads. In particular, we will discuss both adversarial and stochastic iid and random-order models and present:

1) a 0.67 - approximation for online stochastic matching problem in the iid model with known distributions, improving the approximation factor of 1-1/e http://arxiv.org/abs/0905.4100

2) a training-based (1-epsilon)-approximation for a general class of packing-covering linear programs in the random-order model under some assumptions http://arxiv.org/abs/1001.5076, and

3) a (1-1/e)-approximation algorithm for a general class of stochastic assignment problems in the adversarial model with free disposal http://www.springerlink.com/content/1865xx2g70044623/

Throughout the talk, we will discuss both theoretical ideas and experimental results comparing the performance of different algorithms.

Bankers, Bonuses and Busts

By Peter Forsyth (University of Waterloo)

Thursday, October 7

Peter ForsythAbstract: It is commonly believed that the current problems in the capital markets are a result of the financial models developed by academic mathematicians and industry practitioners. In fact, many of us have been pointing out for years that banks were involved in very risky activities, which produced illusory short-term profits. In this talk, I will give a short introduction to the theory behind pricing and hedging derivative contracts (options). A derivative contract is based on an underlying asset. The standard model for the underlying asset price movement assumes that prices evolve according to a random walk with a drift. It is possible for an option seller to set up a hedging portfolio, which is then dynamically rebalanced in response to changes in the underlying asset price. Then, regardless of the random movement of the asset price, the seller of the option is able to pay out the value of the contract at expiry
There is strong evidence that the normal market behavior assumed by standard models is punctuated by occasional large jumps or drops in prices (e.g. subprime mortgages). These processes are called "jump diffusion" models. A simulation of a trading strategy which exploits these market characteristics shows that bankers can produce apparent profits for many years, followed by enormous losses. The compensation system widely used in the financial sector encourages these sorts of activities. In essence, this bonus system allows executives and traders to be rewarded for apparent short-term profits, and to walk away unscathed after producing staggering losses.

Automatic recognition and modeling of astronomical images

By Dustin Lang (Princeton University)

Tuesday, October 5

Dustin LangAbstract: Astronomical images are a great domain for testing ideas in computer vision and machine learning. First I will talk about Astrometry.net, software that can recognize astronomical images -- that is, put a new image in the right place on the sky among millions of existing images. This work combines some classic ideas in computer vision, fast data structures, and Bayesian decision theory. Next, I'll present a little project on searching the web for astronomical images and trying to learn things about the objects in the images. Finally, I'll show some recent work on forward-modeling astronomical images in order to measure the properties of the objects in the images.

Computability and Complexity of Julia Sets

By Mark Braverman (University of Toronto)

Monday, September 20

Mark BravermanAbstract: 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. I will present both positive and negative results on the computability and computational complexity of Julia sets.

A Balanced-Force Volume Tracking Algorithm for Modeling Interfacial Flows with Mass Transfer

By Marianne Francois (Los Alamos National Laboratory)

Thursday, August 5

Abstract: None

Computation of time-periodic solutions of fluid interface problems

By Dr. Jon Wilkening (University of California, Berkeley)

Monday, July 26

Jon WilkeningAbstract:Periodic orbits are fundamental in the study of dynamical systems and partial differential equations. In fluid mechanics, they are important in understanding vortex shedding, ocean waves, the onset of turbulence in a pipe, and many other interesting phenomena. In this talk, I will present a general framework for solving two point boundary value problems governed by nonlinear PDE. The key idea is that shooting methods can be made very efficient by posing them as minimization problems and using adjoint-based optimal control techniques to compute the gradient of the objective function with respect to the unknown initial conditions. We use our method to compute families of time-periodic solutions of the gravity-driven water wave and the vortex sheet with surface tension. Nonlinear resonances lead to surprising results.

Seeing is Believing: Statistical Visualization for Teaching Data Analysis

By Dr. Andreas Buja (University of Pennsylvania)

Monday, May 17

Andreas BujaAbstract:This talk is a tour of four statistical applications where visualization proves useful, maybe even essential. Two applications are about teaching certain abstract concepts, and two more applications involve discovery in data analysis.

The teaching applications are about:

  1. explaining "regression to the mean" to Statistics 101 students, and
  2. illustrating "proper scoring rules" to machine learning researchers.

The data analytic applications show:

  1. space-time aspects of commercial ocean fishing data, and
  2. associations among more than 1,000 variables in autism data.

The last example raises some interesting issues of statistical inference.

Quadratic {-1,01} Optimization

By Andrea Lodi (University of Bologna)

Thursday, May 13

Andrea LodiAbstract: Motivated by an application on Signal Processing, we present a fast branch-and-bound algorithm for the minimization of a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, after some variables have been already decided, a simple lower approximation is given by the continuous minimum of the restricted objective function. We improve this approximation by considering certain lattice-free ellipsoids that are centered in the continuous minimum and determined by a reduced lattice basis. This yields an improved lower approximation for each considered ellipsoid.

The main reason for the high performance of our algorithm in practice is that all expensive calculations can be done in a preprocessing phase, while the running time for a single node in the enumeration tree is at most quadratic in the problem dimension. Experiments show that our approach is fast on both unconstrained problems and problems with box constraints. However, it can handle arbitrary convex constraints by defining the pruning in an appropriate way. (Joint work with Christoph Buchheim and Alberto Caprara).

The Derivative of a Set: Normal Cones and Optimization

By Dr. Warren Hare (University of British Columbia, Okanagan)

Monday, March 15

Warren HareAbstract: In calculus we are taught that to find a minimum of a function we start by finding the roots of its derivative. In this talk we explore how this idea extends to finding the minimum of a smooth function over a constraint set: $$\min \{ f(x) : x \in S\}$$
To do this we develop the Normal Cone. By understanding this geometric object we can extend the notions and algorithms of unconstrained optimization ($\min\{f(x)\}$) into a constrained setting ($\min\{f(x) : x \in S\}$). In this talk we discuss the basic definition of a normal cone, provide illustrative examples, and demonstrate how normal cones provide the tools necessary to develop constraint identification theory for optimization problems.

A three-level semi-discrete in time finite element approximation of a model for skin patterning

By Marcus Garvie (University of Guelph)

Monday, February 22

Marcus GarvieAbstract: This talk is concerned with a second-order, three level piecewise linear finite element scheme for approximating the stationary (Turing) patterns of a well-known experimental substrate-inhibition reaction-diffusion system (‘Thomas system’). A numerical analysis of the semi-discrete in time approximations leads to semi-discrete a priori bounds and an error estimate. The numerical solutions of the fully-discrete finite element method are illustrated by approximating the Turing patterns over a schematic mammal coat with fixed geometry at various scales. Some comments are also made on the correct procedure for simulating Turing patterns in general reaction-diffusion systems.

Recent Work in Model-Based Clustering & Classification

By Dr. Paul McNicholas (University of Guelph)

Monday, January 25

Paul McNicholasAbstract: Model-based approaches to clustering (unsupervised learning) and classification (supervised classification) are growing in popularity due, in part, to ongoing advances in computing hardware. Recent work on model-base clustering is presented. Specifically, two developments are outlined: (1) a model-based clustering approach to the analysis of very large data sets; and (2) a model-based approach to the problem of clustering gene expression time course data. Approaches utilizing mixtures of multivariate Guassian distributions and others using mixtures of multivariate t-distributions are outlined. In each case, a variant of the expectation - maximazation algorithm is used for parameter estimation. Computational issues, including convergence criteria and a parallelization paradigm, are presented and generalizations to model-based classification are also given. Real bioinformatics data are used to illustrzte these methods.

Return to top