Carnegie Mellon University

Summer Undergraduate Applied Mathematics Institute

May 29 - July 17, 2012

Projects

► Combinatorics on Words, Hrothgar, Michael Druggan, Archit Kulkarni

Advisor:  Irina Gheorghiciuc
Abstract: According to Irina the main points of the project:

  • Familiarize yourselves with the notion of subword complexity of finite and infinite words and its significance. Read several important papers on the subject.
  • Analyze in detail the Sturmian and de Bruijn words, which are the words with the highest and lowest subword complexity.

The group expanded the known list of necessary conditions for a vector to be a subword complexity sequence of a finite word. They worked on a conjecture about the asymptotic behavior of the number of distinct subword complexity sequences by Matt Green and Arash Enayati. While certain recurrence patterns in the sequence have been observed and proved, this work in still in progress.

► A First look at boundary value problems, Emmalyne Wyatt, Jessica Jennings

Advisor:  Michael Goldman
Abstract:  In this project, E. Wyatt and J. Jennings studied some boundary value problems in one dimension such $ u'' + u = g\;\; u(0) = u(1) = 0\;\;\;\; (1)$ They tried to understand the difference between this kind of problems and ODEs and then studied (1) by two methods. First, they computed explicit solutions using Fourier methods taking as an example the tent function \[ g(x) = \left\{ \begin{array}{ll} x & \mbox{if $0 \leq x \leq \frac{1}{2}$ }\\ 1- x & \mbox{if $ \frac{1}{2} \leq 1$} \end{array} \right. \] After that they proved also existence of solutions using functional analysis. For this they learned about Hilbert spaces with emphasis on weak convergence, Riesz Theorem, orthonor- mal basis (and made the link with the Fourier method).

They also learned about the space of square integrable functions $L^2$ and the Sobolev space $H^1,$ getting familiar with the notion of weak derivatives. They then derived a weak formulation of (1) and solved it using both the Riesz representation Theorem and by proving existence of minimizers of the functional \[ J(u) = \frac{1}{2} \int_0^1 [(u')^2 + u^2] {\mbox dx} - \int_0^1 (gu) {\mbox dx} \] by the Direct Method of the Calculus of Variations. Then they used both the Fourier method and the abstract method to study the convergence when $\epsilon \rightarrow 0$ of the solutions $u_{\epsilon}$ of the problem $ u'' + u = g_{\epsilon}\;\; u(0) = u(1) = 0$ where $ g_{\epsilon}=g(frac{x}{\epsilon}) $ with $g$ a periodic function. They showed that $u_{\epsilon}$ strongly converges to the solution of $ u'' + u = \bar{g}\;\; u(0) = u(1) = 0$ where $\bar{g}= \int_0^1 g\; dx.$

► Using Mathematics to Restore or Correct Images, Jieun Lee, Nathan Scavilla

Advisor:  Michael Goldman
Abstract: In this project, J. Lee and N. Scavilla studied two methods for denoising images. They First concentrated on the Tychonov method where a corrupted image $g$ is denoised by considering the minimization problem \[ {\mbox min}\int_{[0,1]^2} |\bigtriangledown u|^2 +\frac{\lambda}{2}\int_{[0,1]^2} (u-g)^2.\;\;\; (1)\] They derived the Euler Lagrange equation for this problem, which is $-\bigtriangleup u+\lambda(u-g)=0$ and understood the associated (Neumann) boundary conditions. They then solved this equation both using discrete differences and Fourier methods. They studied the effect of the parameter $\lambda$ on the solution and showed that when considering the one dimensional analog with for example $g=\chi_{[\frac{1}{2}]}$ then the denoised signal is always smooth meaning that this model can not capture the edges.

To overcome this problem, they considered the Rudin-Osher-Fatemi model \[ {\mbox min}\int_{[0,1]^2} |\bigtriangledown u|^2 +\frac{\lambda}{2}\int_{[0,1]^2} (u-g)^2.\] involving the total variation. They showed in one dimension that for some values of $\lambda$, no smooth solution can exist and studied the definition and basic properties of functions of bounded variation again in one dimension. They then focused on the discretized problem \[ {\mbox min}\Sigma \sqrt{(u_{i+1,j}-u_{i,j})^2 +(u_{i,j+1}-u_{i,j})^2} +\frac{\lambda}{2}\Sigma (u_{i,j}-g_{i,j})^2.\] Since this is a convex but nonsmooth problem, in order to derive the Euler Lagrange equation of this problem, they studied some convex analysis with particular emphasis on the notions of subgradient and convex conjugate. Using these tools, they were able to rewrite the Euler Lagrange equation as $u= g-\pi_{\lambda K}(g)$ where $\pi_{\lambda K}(g)$ is the projection of $g$ on the convex set $\lambda K=\{{\mbox div}p : |p_{i,j}\leq \lambda.$ They computed this projection by using a semi-implicit gradient descent algorithm proposed by A. Chambolle. They ran a large number of numerical examples comparing the Tychonov and the ROF models.

► Generalized Mersenne Numbers, Christian Rodriguez

Advisor:  Gregory Johnson
Abstract: Large prime numbers are useful in cryptography because of the computational complexity of determining the prime decomposition of products of two large primes.

Current efforts are primarily focused on Mersenne primes which are of the form 2n - 1 as the largest known primes are of this form. In this project we study potential primes of the form 22n ± 2n + 1. We determined properties of such numbers necessary for them to be prime as well as efficient primality tests for those that meet these conditions. In addition, we investigated the question as to whether a potential prime of this form must be square free.

► Modeling Stock Pairs Using Continuous-Time Markov Chains, Caroline Miller, Utkarsh Narayan, Elizabeth Newman, Tamar Oostrom

Advisor:  Chad Schafer
Abstract: This group worked to fit and test a continuous time Markov chain model to the price fluctuations of a pair of equities. Briefly stated, the objective was to use the limiting distribution of the resulting Markov chain to quantify the proportion of the time the two stocks exhibit similar trends. This could be useful for pairs trading strategies which rely upon finding pairs of stocks which are typically in sync with one another. This measure should be more robust than the standard "beta" measure in current use, as it is less sensitive to outliers.

The group made significant progress towards this goal, by developing and testing methods for determining when a stock price process shifts between upward, downward, and stable periods. This required an understanding of fundamental issues of statistical hypothesis testing. The group explored the properties of the continuous time Markov chain, and used these to determine optimal estimators for the parameters of the process; again, this allowed us to discuss fundamental statistical inference issues. The group also used the fit model to estimate the limiting distribution for the Markov chain. All of this work required significant amount of data processing and coding, which was done in R. In this way the project represented a comprehensive exploration of an interesting and challenging data analysis and model fitting problem.

Students

  • Druggan, Michael, Carnegie Mellon University
  • Hrothgar, Rice University
  • Jennings, Jessica, Loyola University
  • Kulkarni, Archit, Carnegie Mellon University
  • Lee, Jieun, Carnegie Mellon University
  • Miller, Caroline, Roger Williams University
  • Narayan, Utkarsh, Carnegie Mellon University
  • Newman, Elizabeth, Haverford College
  • Oostrom, Tamar, Washington & Lee University
  • Rodriguez, Christian, University of Puerto Rico
  • Scavilla, Nathan, University of Maryland
  • Wyatt, Emmalyne, University of Transylvania

Faculty

Handron

Dave Handron, Associate Teaching Professor
Course: Symbolic Programming in Mathematics

E-mail:  handron@andrew.cmu.edu
Wean Hall 6214
412-268-5583

Gheorghiciuc

Irina Gheorghiciuc, Assistant Teaching Professor

Project Director

E-mail:  gheorghi@andrew.cmu.edu
Wean Hall 8126
412-268-3023

Goldman

Michael Goldman, Postdoctoral Associate

Project Director

Gregory Johnson

Gregory Johnson, Assistant Teaching Professor

Project Director

E-mail:  greggo@andrew.cmu.edu
Wean Hall 8122
412-268-1504

Larsen

Kasper Larsen, Associate Professor
Course: Introduction to Mathematical Finance

E-mail:  kasperl@andrew.cmu.edu
Wean Hall 7219
412-268-6380

Chad Schafer

Chad Schafer, Associate Professor

Project Director

E-mail:  cschafer@cmu.edu
Baker Hall 228D
412-268-3967