Monday, February 04, 2013

LaTeX template for NSF-style Biographical Sketch

On large multi-university NSF grant proposals, NSF requires that senior personnel submit a 2-page biographical sketch ("biosketch") that is formatting according to certain rules in their Grant Proposal Guide (GPG). The format is pretty simple, and so there does not seem to be much demand for a solid LaTeX template for one. Nevertheless, I thought some people might find one helpful. I've posted a PDF of my NSF-style biosketch below along with the TeX source used to generate it. On a related note, you can also find my curriculum vitae (CV) tailored for faculty searches (PDF, TeX) as well as for industry searches (PDF, TeX).

Thursday, January 24, 2013

Discrete-time Phase Portraits?

I was contacted recently by e-mail asking how to produce a phase portrait of a discrete-time system. In my initial response, I explained that a true "phase portrait" wasn't defined for discrete-time systems because the technical notion of a phase portrait depends on a special structure that comes along with ordinary differential equations. The original poster needed some additional clarification, and so I sent a second e-mail that I have posted below. It touches a little bit on the original poster's question, it comments on differences between discrete-time and continuous-time systems, it talks a bit about chaos, and it gives a brief description of Poincaré/return maps that are often used in the study of approximately periodic systems.

My point is that a discrete-time system really cannot be interpreted within a field-theoretic framework. A "phase portrait" captures both position and momentum of a continuous-time system described by an ordinary differential equation. These momentum variables setup the "field" that gives structure to the phase portrait. In a discrete-time system, we don't have the same kind of momentum.

     For a continuous-time system, I can plot a point at an individual position, and I can also then draw a vector pointing away from that point representing the velocity at that instant of time. It is these velocity vectors that are put together to make a phase portrait of the system.

     For a discrete-time system, there is no point-based velocity. In order for me to calculate the approximate "velocity" at a point, I need to know the position at the next point. Then I can draw a line between those two points and approximate the "velocity" of the system as going from the first point to the second point. However, if I have to know the next point in future anyway, it's more useful to just draw the second point.

     Now, some discrete-time systems have a more predictable structure. For example, if you have a linear time-invariant discrete-time system like:

x[k+1] = M*x[k]

then the algebraic structure of the "M" matrix gives us insight into how trajectories will evolve. So for these special cases, it is possible to draw a kind of "phase portrait" for the discrete-time system. However, this is primarily because such a discrete-time system can be viewed as a sampled version of a continuous-time linear time-invariant system which does have a phase portrait.

     So, for an arbitrary discrete-time system, the best thing you can do is explore trajectories from different initial conditions. Gradually, as you explore the space more and more, you may find boundaries of attractors (possibly strange attractors). A complication with discrete-time systems is that the "next" point may be very far from the "previous" point. Take, for example:

x[k+1] = -1.1*x[k]

If you start at x[0]=1, the trajectory will bounce from point clustered above 1 to points clustered below -1. In a continuous-time system, you might expect to see initial conditions above 1 stay near 1 and initial conditions below -1 stay near -1. That is, in a continuous-time system, you wouldn't imagine trajectories could cross x=0 (which is an equilibrium/fixed-point of this system). However, the discrete-time system can jump wildly from point to point.

     Take, for example, the Henon map you mention. Wolfram's Mathworld has some nice plots:

http://mathworld.wolfram.com/HenonMap.html

The first pair of side-by-side plots are colored "according to the number of iterations required to escape". That is, the plots were generated by starting at several initial conditions and recording the resulting trajectories. Each "iteration" gives the next point from the previous point. For a while, a trajectory will stay around its initial condition. Eventually, it will escape and move away from the region. The regions are colored based on how many iterations (i.e., how many calculations after the initial condition) it took for the trajectory to leave the region.

     The second pair of side-by-side plots show a SINGLE trajectory started at x[0]=0 and y[0]=0. Each point was recorded and gradually a pattern emerged. Notice how in the left plot the two regions appear to be disconnected. If you saw a phase portrait that looked like this in a continuous-time system, you would conclude that initial conditions within one region would not be able to join the other region for this set of parameters. However, this plot was generated from a SINGLE initial condition. So the plot jumps from points in the top left to points in the bottom right and back.

     So that's how you can explore something like the "phase space" for discrete-time systems. You can probe it with different initial conditions. For chaotic systems, you have to be very careful you don't accidentally jump over an interesting region of initial conditions that may have qualitatively different trajectories that follow from them.

     As an aside, I guess it's also worth mentioning that many popular discrete-time chaotic maps are actually Poincaré maps of continuous-time dynamical systems. Poincaré maps have other names, including "return maps." Consider, for example, the planets as they orbit the sun. The actual orbits of the planets in three dimensions looks like a tangled mess when you consider their histories over several cycles around the sun because each orbit is slightly different than the previous orbit (i.e., they aren't entirely planar). However, if you insert a plane perpendicular to their orbits at a single location, each planet pierces the plane at one point every cycle. The resulting shapes that are poked out of that cross section reveal structure in the orbits.

     I hope that helps! --
     Ted